Corresponding author: LIN Shu-kuan, professor, E-mail: linshukuan@ise.neu.edu.cn
近年来，城市机动车数量增加迅速，道路资源建设相对滞后，导致城市交通拥堵日益严重，拥堵路段预测成为建设智能城市和交通不可缺少的组成部分.越来越多的学者开始关注和研究基于交通数据的拥堵路段预测方法和技术[1, 2, 3, 4].现有的相关研究多基于道路上固定安装的传感器采集的数据，且多集中在交通拥堵路段的识别、挖掘和交通流预测方面[5, 6, 7, 8, 9].
近年来，车载GPS发展迅速，产生大量的时空数据，可用于进行拥堵路段预测.本文基于出租车GPS轨迹数据，提出了一种新颖的考虑路段拥堵时间周期性和时空因果关系的、基于拥堵向量和拥堵转移矩阵的拥堵路段预测方法.
1 拥堵转移矩阵的建立本文同时考虑拥堵路段具有的时间周期性和时空相关性，提出了基于拥堵向量和拥堵转移矩阵的拥堵路段预测方法.为了建立拥堵转移矩阵，需要对历史GPS轨迹数据进行挖掘和训练.车流与路段拥堵情况在工作日(周一至周五)和休息日(周六和周日)呈现不同的规律，为此，本文将工作日和休息日的历史轨迹数据进行训练，并将工作日或休息日中的一天看作一个周期.路段拥堵具有时间周期性，虽然同一周期的不同时间段呈现不同的拥堵状况，但不同周期的相同时间段却具有相似的拥堵情况，因此，本文将每个周期划分为具有固定时间长度的时间段，称为时间框架.历史轨迹数据的训练过程就是通过挖掘各个周期和时间框架内的历史拥堵路段，建立各时间框架的拥堵转移矩阵，为未来时间框架内的拥堵路段预测提供支持.
1.1 拥堵路段挖掘 为了在训练阶段建立拥堵转移矩阵，需要挖掘出每个周期和时间框架内的拥堵路段.由GPS采集的轨迹数据是由轨迹点构成的序列，轨迹模式为tr=(q1,q2,…, qn)，其中每个轨迹点qi(1≤i≤n)是一个二元组，即qi=(pi,ti)，这里pi是位置信息，ti是时间信息.在挖掘拥堵路段之前，需要对历史轨迹数据进行预处理，即从轨迹数据中提取路段集合和经过每条路段的轨迹片段集合.本文基于文献[10]中的方法从轨迹数据中挖掘十字路口，在此基础上，形成由相邻十字路口构成的路段集合以及经过每条路段的轨迹片段集合，具体过程如算法1所示.算法1 路段集合和路段上的轨迹片段集合提取算法.
输入：历史GPS轨迹集合T,十字路口集合I.
输出：路段集合RS,每条路段上的轨迹片段集合TS和后继路段集合Successors.
1. RS=Φ;
2. for 每条轨迹tr∈T do
3. 取轨迹tr的第一个十字路口点q1;
4. for q1之后的邻接轨迹点q2 do
5. if q2∈I then
6. if(由q1和q2构成的路段r∈RS)
then7. r.TS=r.TS∪(q1,q2,tr)；
8. else
9. r.TS=Φ；r.Successors=Φ；
10. RS= RS∪r；
11. if (q1不是tr的首个十字路口点)
then12. r0.Successors = r0.Successors∪r;
13. q2→q1；r→r0.
算法1遍历每条轨迹的每个轨迹点，将相邻十字路口点q1和q2构成的路段r加入路段集合RS，并形成经过每个路段r的轨迹片段集合TS和路段r的后继路段集合Successors，TS中的元素为由(q1,q2,tr)构成的三元组.
在算法1提取的路段集合和路段上的轨迹片段集合的基础上，对各周期和时间框架内的拥堵路段进行挖掘，如算法2所示.首先，提取每个路段上的轨迹片段所属的周期和时间框架，并形成每个路段在各周期和时间框架的轨迹集合(行2~6)；其次，对于每个路段，计算各周期和时间框架内经过路段的轨迹数量，并根据路段饱和度判断路段在相应的周期和时间框架内是否拥堵，从而形成各周期和时间框架的拥堵路段集合(行7~15).
算法2 各周期和时间框架内的拥堵路段挖掘算法.
输入：路段集合RS，每条路段上的轨迹片段集合TS，每个路段饱和度capacity.
输出：各周期和时间框架的拥堵路段集合congestionResult.
1.congestionResult=Φ；
2.for 每个路段r∈RS do
3. for 每个轨迹片段(q1,q2,tr)∈r.TS do
4. 基于q1,q2的时间信息提取轨迹片段所属周期→d;
5. 基于q1,q2的时间信息提取轨迹片段所属时间框架→f;
6. tr→路段r的周期为d、时间框架为f的集合S(r,d,f)中;
7.for 每个周期d do
8. for每个时间框架f do
9. R(f∈d)=Φ;
10. for每条路段r∈RS do
11. 计算集合S(r,d,f)的大小→num(r,d,f);
12. if num(r,d,f)>capacity(r) then
13. r.d.f.isCongestion=true;
14. R(f∈d)=R(f∈d)∪r;
15. else r.d. f.isCongestion=false;
16. congestionResult=congestionResult∪R(f∈d).
1.2 拥堵转移矩阵建立1.1节考虑了路段拥堵的时间周期性，从GPS轨迹数据中挖掘各周期和时间框架内的历史拥堵路段.从日常生活观察中可以发现，路段拥堵不仅具有时间周期性，还具有很强的时空相关性.所谓路段拥堵的时空相关性是指某些拥堵路段在时间、空间上具有一定的关联，一条路段在一个时间框架内拥堵可能造成与它相邻的路段在下一个时间框架内也发生拥堵.本节将基于1.1节得到的拥堵路段集合，挖掘路段之间的时空因果关系，从而建立拥堵转移矩阵.本文假设拥堵路段之间的时空相关性具有一阶马尔科夫性：即当前路段是否拥堵只与和它最相邻的路段相关，并且只与前一个时间框架相关.为了更清楚地描述拥堵转移矩阵的建立过程，先给出相关定义.
定义1 (路段的时空因果关系) 对于时间框架f内的路段ri=(qis,qie)和时间框架f′内的路段rj=(qjs,qje)，若满足：(qie=qjs)且f′=f+1，则称两路段ri和rj关于时间框架f具有时空因果关系，记为ri→(f)rj.
定义1中的qis和qie分别为路段ri的两个端点.
定义2 (路段的拥堵因果关系)对于满足
关系的路段ri,rj，若ri∈R(f∈d)且rj∈R((f+1)∈d)，则称路段ri,rj在周期d关于时间框架f具有拥堵因果关系，记为
；若ri∈R(f∈d)，但rj
R((f+1)∈d)，则称路段ri,rj在周期d关于时间框架f不具有拥堵因果关系，记为
.
定义2中的R(f∈d)为算法2挖掘出的周期d中时间框架f内的拥堵路段集合，ri∈R(f∈d)表示路段ri在周期d中的时间框架f内发生拥堵.
定义3 (路段拥堵因果关系矩阵) 周期d的时间框架f中的拥堵因果关系矩阵是一个n×n矩阵，记为M(f∈d)，n为路段集合RS中的路段总数.矩阵元素Mij(f∈d)(n≥i, j≥1)共有3种取值，即
各周期的每个时间框架内的路段拥堵因果关系矩阵可依据定义3，基于算法2得到的拥堵路段集合生成，具体生成过程如算法3所示.
算法3 路段拥堵因果关系矩阵生成.
输入：各周期和时间框架的拥堵路段集合congestionResult.
输出：所有周期的各时间框架中的路段拥堵因果关系矩阵集合MS.
1. MS=Φ；
2. for 每个周期d do
3. for 每个时间框架f∈d/lasttimeframe do
4. 将矩阵M(f∈d)的所有元素初始化为0;
5. for 每个路段ri∈R(f∈d)
6. for每个路段rj∈ri.Successors do
7. if rj∈R((f+1)∈d)then
8. Mij(f∈d)=1;
9. else
10. Mij(f∈d)=-1;
11. MS = MS∪M(f∈d).
定义4 (拥堵转移概率)路段ri与路段rj之间关于时间框架f的拥堵转移概率pij(f)定义为路段ri在时间框架f内拥堵的情况下路段rj在时间框架f+1内发生拥堵的概率，即
根据定义4，利用算法3生成的路段拥堵因果关系矩阵，路段ri与路段rj之间关于时间框架f的拥堵转移概率可计算如下：
定义5 (拥堵转移矩阵)关于时间框架f的拥堵转移矩阵P(f)是一个n×n矩阵，n为路段集合RS中的路段总数，元素Pij(f)为路段ri与路段rj之间关于时间框架f的拥堵转移概率.
根据定义5，各时间框架所对应的拥堵转移矩阵可基于式(3)计算的拥堵转移概率生成，从而为进行拥堵路段预测提供支持.
2 拥堵路段预测拥堵路段预测包含两部分：第一部分为当前拥堵路段计算，通过统计当前时间框架各路段上的交通流，计算当前时间框架内的拥堵路段，并表示为向量形式；第二部分则对未来时间框架的拥堵路段进行预测.
定义6 (拥堵向量)时间框架f内的拥堵向量V(f)是一个n元向量，即V(f)=(p1(f),p2(f),…,pn(f))，其中，n为路段集合RS中的路段总数，元素pi(f)(1≤i≤n)为路段ri在时间框架f内拥堵的概率，即
当前时间框架的拥堵向量可以基于轨迹数据，统计当前时间框架内各路段的车流量，如果车流量大于饱和度[9]，表示路段发生拥堵，则将路段对应的拥堵向量元素设为1，否则设为0.
在1.2节得出的拥堵转移矩阵和以上得出的拥堵向量的基础上，通过计算未来时间框架的拥堵向量，可以对未来时间框架的拥堵路段进行预测，具体描述见定理1.
定理1 设当前时间框架f内的拥堵向量和拥堵转移矩阵分别为V(f)和P(f)，则时间框架f+1内的路段拥堵向量V(f+1)=V(f)·P(f).
证明 (略).
按照定理1，基于当前时间框架的拥堵向量和拥堵转移矩阵，可以计算未来时间框架的拥堵向量.
给定拥堵概率阈值β，若拥堵向量中的拥堵概率大于阈值，表示相应路段拥堵，从而对拥堵路段进行预测.
3 实验分析实验采用的数据集为真实数据集T-Drive (http://research.microsoft.com/apps/pubs/?id=152883).所有实验程序的开发环境为3.16GHz Intel Core(TM2) Duo CPU，4GB内存，操作系统为Windows XP，编程语言为C++.
实验将本文提出的基于拥堵转移矩阵的预测方法PBTM(prediction based on transferring matrix)与文献[9]中基于交通流转移概率的方法PBP (prediction based on probability)进行比较.实验中涉及到的评价指标(准确率、召回率)如式(9)和式(10)所示：
图 1给出了两种方法的预测准确率随时间框架长度的变化情况.
 | 图 1 时间框架长度对预测准确率的影响 Fig. 1 The effect of length of time frame on precision |
从图 1可以看出，随着时间框架长度的增加，PBTM和PBP的预测准确率都降低.但PBTM的准确率高于PBP，因为PBTM更符合路段拥堵的特点，不仅考虑了路段拥堵的时间周期性，而且考虑了拥堵路段间的时空因果关系.
图 2给出了两种方法的预测准确率随训练数据集大小的变化情况，其中时间框架长度为15min.从图 2可以看出，随着训练数据集的增大，PBTM和PBP的预测准确率都增大，具有较好的扩展性.对于PBTM，训练数据集越大，包含的周期数量就越多，拥堵路段间的时空因果关系挖掘的越完全，拥堵转移矩阵也就越准确.对于相同的拥堵向量，预测得到正确的拥堵路段越多，准确率越高.
 | 图 2 训练数据集大小对预测准确率的影响 Fig. 2 The effect of size of training dataset on precision |
图 3显示了阈值β的变化对预测准确率和召回率的影响.从图 3可以看出，随着阈值β的增大，预测的准确率逐渐增大，而召回率逐渐降低.原因是阈值β越大，基于β过滤出的路段都是拥堵概率大的路段，得出的拥堵路段越有可能是真实拥堵的路段，因此，准确率越高.而阈值β越大，基于β过滤出的路段数量越少，包含真实拥堵的路段也就越少，因此，预测的召回率越低.
 | 图 3 阈值β对准确率和召回率的影响 Fig. 3 The effect of β on precision and recall |
以上基于真实的GPS轨迹数据集，对本文所提出的拥堵路段预测方法的效果进行了验证.从实验中可以看出，随着时间框架长度的增加，预测的准确率呈下降趋势，因此，在实际应用中，设置的时间框架长度不宜过大，以期达到较好的预测效果.同时，应根据实际情况设置合适的阈值β，以获得较高的预测准确率和召回率.
4 结语本文面向GPS轨迹数据，摒弃传统的基于交通流预测和拥堵识别的方法，提出一种基于拥堵向量和拥堵转移矩阵的拥堵路段预测方法.针对路段拥堵具有的时间周期性和时空相关性，对出租车GPS轨迹数据进行挖掘和训练，通过建立拥堵向量和拥堵转移矩阵，实现对拥堵路段的预测.基于真实数据集的实验表明，本文所提方法相比于已有的拥堵路段预测方法，预测的准确率有较大提高，并具有较好的扩展性.
| [1] | Lécué F, Tucker R, Bicer V, et al.Predicting severity of road traffic congestion using semantic web technologies[M].Borlin:Springer International Publishing, 2014:611-627.( 1) |
| [2] | Kwoczek S, di Martino S, Nejdl W.Predicting and visualizing traffic congestion in the presence of planned special events[J].Journal of Visual Languages & Computing, 2014, 25(6):973-980.(1) |
| [3] | Schwenke C, Wagner T, Kabitzsch K.Event based identification and prediction of congestions in manufacturing plants[M].Borlin:Springer Berlin Heidelberg, 2013:376-390.(1) |
| [4] | Pescaru D.Urban traffic congestion prediction based on routes information[C]// IEEE International Symposium on Applied Computational Intelligence and Informatics.New York, 2013:121-126.(1) |
| [5] | 姜桂艳, 冮龙晖, 王江锋.城市快速路交通拥挤识别方法[J].交通运输工程学报, 2006, 6(3):87-91. (Jiang Gui-yan, Gang Long-hui, Wang Jiang-feng.Traffic congestion identification method of urban expressway[J].Journal of Traffic and Transportation Engineering, 2006, 6(3):87-91.)(1) |
| [6] | Chun-Hsin W, Jan-Ming H, Der-Tsai L.Travel-time prediction with support vector regression[J].IEEE Transactions on Intelligent Transportation Systems, 2004, 5(4):276-281.(1) |
| [7] | Sun S L, Zhang C S, Yu G Q.A Bayesian network approach to traffic flow forecasting[J].IEEE Transactions on Intelligent Transportation Systems (TITS), 2006, 7(1):124-132.(1) |
| [8] | Abdulhai B, Porwal H, Recker W.Short term freeway traffic flow prediction using genetically-optimized time-delay-based neural networks[C]//California Partners for Advanced Transit and Highways (PATH).Berkeley, 1999:1-45.(1) |
| [9] | Castro P S, Zhang D, Li S.Urban traffic modelling and prediction using large scale taxi GPS traces[C]// Proceedings of the 10th International Conference on Pervasive Computing.Newcastle:Springer-Verlag, 2012:57-72.(3) |
| [10] | Chen Z, Shen H T, Zhou X.Discovering popular routes from trajectories[C]//2011 IEEE 27th International Conference on Data Engineering (ICDE).Hannover, 2011:900-911.(1) |