基于出租车轨迹数据的最优路径规划方法

戚 欣，梁伟涛，马 勇

(1.武汉理工大学 计算机科学与技术学院，武汉 430063； 2.武汉理工大学 航运学院，武汉 430063) (*通信作者电子邮箱liangweitao0726@163.com)

基于出租车轨迹数据的最优路径规划方法

戚 欣1，梁伟涛1*，马 勇2

(1.武汉理工大学 计算机科学与技术学院，武汉 430063； 2.武汉理工大学 航运学院，武汉 430063) (*通信作者电子邮箱liangweitao0726@163.com)

针对传统的路径规划算法并不一定能计算得到现实中最优路径的问题，提出一种融合了出租车驾驶经验并以时间为度量的路径规划算法。该算法的实现是将路径规划这个以计算为中心的技术变为以数据为中心的数据驱动挖掘技术。首先，从大量的出租车轨迹数据中提取真实的载人轨迹数据，并将载人轨迹数据匹配到路网数据中；然后，根据地图匹配结果计算路段的访问频次，选取前Top-k个路段作为热点路段；其次，计算热点路段间行车轨迹的相似度，对轨迹进行聚类分析，在路网的基础上构建该k个路段的热点路段图；最后，使用一种改进的A*算法实现路径规划。实验结果表明，与传统的最短路径规划算法和基于驾驶经验路网分层的路径规划算法相比，所提出的基于热点路段图的路径规划方法有效地缩短规划路径的长度及路径行驶时间，提高路径规划的用时效率。

智能交通；出租车驾驶经验；改进A*算法；热点路段图；路径规划

0 引言

随着定位技术和移动计算技术的发展，产生了大量的出租车轨迹数据，这些轨迹数据中包含出租车司机的历史经验以及交通路网的车辆行驶规律等重要信息。如何从出租车历史数据中提取有用的路径信息，并将这些信息用于新路径的计算是相关学者一直研究的热点问题[1]。

传统的路径规划算法并没有将出租车轨迹数据中的经验知识考虑进来，而是在获得城市路网信息后计算车辆行驶时间和车辆行驶距离的最短路径，并将符合时间和距离最短的路径视为最短路径。基于出租车轨迹数据的路径规划算法可以从大量出租车轨迹数据中提取历史经验信息，并从中获取考虑综合信息后的实际行驶中的最优路径。文献[2]在考虑司机驾驶经验的基础上，建立经验路径数据库，并修正不完整和不正常的路径。Yuan等[3-4]在考虑司机驾驶经验的基础上，使用基于方差的熵聚类方法估计行程时间的概率分布，并设计了两步路径算法去计算实际中最快和个性化的路径。唐炉亮等[5]采用平滑方法实现经验道路的等级划分，并结合司机驾驶的经验，提出了基于出租车经验知识建模的路径规划算法。文献[6]中通过获取交通状况和司机驾驶行为的信息建立一个云系统来计算个性化路径和符合实际情况且可以最快到达目的地的路径，该系统可以预测未来一段时间内的交通状况。Vincent等[7]基于用户的轨迹数据和排序的协作张量和矩阵分解模型的方法开发了一个移动推荐系统。当存在大量的比较原始的出租车轨迹数据时，需要解决地图匹配的问题，文献[8]中提出基于相互投票的地图匹配算法(Interactive Voting-based Map Matching, IVMM)，解决了全球定位系统(Global Positioning System, GPS)跟踪数据低采样率的问题。文献[9]中提出使用多跟踪地图匹配的方法同时匹配多个地图集。此外，Li等[10]在基于出租车历史轨迹数据的基础上提出一种分层路径规划算法，并结合Dijkstra算法遍历已生成的分层路网。Hu等[11]利用行程频次和速度信息分割道路，并构建经验分层路网，验证了经验最优路径在不同时间段都可以获得，尤其是在高峰时间段。

本文从大量的出租车轨迹数据中提取真实的载人GPS轨迹数据，并将GPS轨迹数据匹配到路网数据中，然后根据地图匹配的结果统计路段的访问频次，选取前k个路段作为热点路段，在路网的基础上构建k个路段的热点路段图，最后，使用一种改进的A*算法实现路径规划。本文的主要贡献体现在以下两方面，一是挖掘并充分应用轨迹数据中的隐含信息，将传统的以侧重路径计算为中心的路径规划算法变为以数据为中心的数据驱动算法，进一步增加路径规划的合理性。这种数据驱动算法并不像之前的路径规划算法，在城市路网的基础上用相应的最短路径规划算法去计算路网的最短路径，而是借助于众多的历史轨迹数据，从历史轨迹数据中充分提取司机的驾驶经验智慧，并分析城市路网中存在的行车规律，将出租车司机的驾驶经验充分融入到路网中，再结合路径搜索策略进一步规划更符合人们出行路线。二是对经验路网的改进，传统的经验路网仅根据驾驶员的经验获取访问频次较高的路段，而本文不仅根据驾驶经验获取高频路段，而且对连接高频路段的轨迹作了进一步的聚类分析，从而得到更加精简的经验路网，即热点路段图，在热点路段图的基础上，使用改进的A*算法可更高效快速地找到符合人们日常出行的路径。

1 技术路线

城市道路中行驶着大量的出租车，出租车的载人轨迹在一定程度上反映城市道路的行驶规律，也蕴含着司机的驾驶经验智慧。在选择行驶路径时，出租车司机会根据以往驾驶经验，考虑道路等级、红绿灯数量、拥堵程度及周围环境等各种因素。本文通过分析出租车载人轨迹数据进一步了解道路结构，获取驾驶员的经验智慧，将道路结构、出租车司机的驾驶经验与路径搜索策略紧密结合，实现更加合理化的路径规划。

首先，对获取到的出租车轨迹数据进行预处理，从大量的轨迹数据中提取真实的载人轨迹数据，并剔除一些噪声数据，包括时间数据无变化、速度为零且有载客的状态、轨迹数据点较少、载客状态错误显示等。

其次，在现有路网数据的基础上，进一步将获取的出租车载人轨迹数据匹配到相应的路段上，完成出租车载人GPS轨迹到路网数据的地图匹配工作，使得在地图上可直观地显示出租车的行驶轨迹。本文采用的地图匹配算法是IVMM算法[8]，它对低采样率GPS轨迹点到路网的匹配有较高的准确性。

再次，根据地图匹配的结果计算路网中路段被匹配到的次数，选取出租车司机较为倾向的路段，即热点路段，以此构建基于经验道路的基础热点路段图。

然后，统计分析热点路段之间的行驶路径与时间，本文把轨迹间的编辑距离作为轨迹相似性的度量，对热点路段之间的行驶路径进行聚类分析，选取两路段间最为合适的连接路径，进一步完善热点路段图的构建。

最后，在热点路段图的基础上，利用改进的A*算法实现基于出租车经验轨迹的路径规划算法。

主要技术路线流程如图1所示。

图1 技术流程

2 概念定义

针对出租车行为活动轨迹进行数据挖掘的分析研究工作，在数据处理之前作如下定义。

1)路段。路网数据中的一条路段可以是有方向的，它由两个端点组成。例如，一条路段road=rs→re(rs看作从路段的起始端，re看作路段的终点端)。

2)路线。路线是由多个路段连接而成的，例如，路线r1→r2→r3→…→rn。在这里rk+1.s=rk.e，即相邻的两个路段，前一个路段的终点也是下一个路段的起点。

3)路网数据。路网数据是由路段的端点和路线组成的有方向的路网图。

4)GPS位置点。由GPS定位技术记录的位置点，每个GPS位置点由7个字段构成，包含车牌号、采集时间点、纬度、经度、车辆状态、车速和行驶方向基本信息，表示为p=(name,T,Lat,Lng,status,v,angle)，name为车牌号，T为时间戳，Lat为纬度，Lng为经度，status为载人状态，v为行车速度，angle为行车方向。

5)GPS轨迹。由出租车GPS位置随着时间变化按照顺序连接成的空间序列印记。其中Tpi>Tpj(j>i)，Tpi为第i个位置点的时间，Tpj为第j个位置点的时间，这样连续的GPS位置点序列形成的曲线印记即为GPS轨迹。

6)热点路段。路网中的路段被访问频次超过一定阈值时则称该路段为热点路段。

7)热点路段图。热点路段图是由热点路段连接而成的路网。

3 出租车载人轨迹的提取

出租车的GPS轨迹信息中记录了在当前时刻下出租车的行驶状态，每一条轨迹信息中包含车辆的采集时间点、经纬度信息、车辆载客状态、车速、行车方向等信息。总的轨迹数据记录了出租车运营的整体行驶状态，其中有载客行驶和空载行驶两种。轨迹信息中的车辆载客状态用0和1分别表示出租车是空载状态还是载客状态，可选择载客状态为1的轨迹信息作为提取出租车驾驶经验的轨迹数据集。因为当载有乘客时，出租车司机为追求最大化的经济利益会根据自己以往的驾驶经验花费最少的精力和时间把乘客送达他们的目的地，而这种包含经验的行车路径正是所需要获取的数据。

在出租车的众多行驶轨迹中，根据车辆载客状态对轨迹进行分割，并提取真实的载人轨迹数据，再对载人GPS轨迹数据进行地图匹配，这在一定程度上降低了地图匹配的工作量。图2为从一条出租车轨迹中提取出的真实载人路段序列。ST表示出租车的载客状态，出租车的载客状态(STATUS,ST)为0表示空载，ST=1表示载客。图中p0，p1，…，,p9分别表示载人轨迹中的10个GPS轨迹采样点，它们的载客状态ST=1。从轨迹点中提取ST=1的GPS点，因为只有真实的载人轨迹才能提取出有价值的驾驶经验。

图2 载人GPS轨迹的提取

图3 候选路段和候选点集合示例图

4 路径规划

4.1 热点路段的选取

根据提取的载人GPS轨迹数据到路网匹配的结果，对城市路网各时段出租车在各路段的出现次数进行统计，并把路段访问次数作为城市道路片段被选取为热点路段的依据，路段访问次数由下式计算:

(1)

(2)

其中：nei(t)为路段i在时间段t内通过的所有载人轨迹的总和，m为载人轨迹总数，n为统计的路段总数，nall为所有路段的统计总数。nei(t)的值越大，表示在该时间段内出租车司机越倾向于选择路段i，也表示路段i为经验上较好的路段。依据nei(t)的统计量，选择出城市道路中的热点路段。

4.2 构建基于经验轨迹的热点路段

相较于基础的经验路网的构建，本文基于前一部分中热点路段的选取工作，对选取的热点路段之间的连接赋予权值与语义，构建更加精简且隐含更多行驶规律信息的热点路段图。现有的轨迹处理方法主要关注的是发现频繁轨迹模式，从历史轨迹数据中挖掘有效的行驶轨迹，并将轨迹数据挖掘的结果运用到相应的研究中。文献[12]基于连续时间贝叶斯网络，提出了一种轨迹预测函数(PutMode)，可预测移动对象的不确定性行驶轨迹，该函数在处理历史轨迹数据过程中选用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚类算法对众多移动轨迹进行聚类分析，进一步移除噪声轨迹，确保轨迹预测的准确性。传统的移动对象的轨迹预测函数仅作用于给定有约束的道路上，当面临不利的环境因素时，如交通拥堵、恶劣天气等，往往表现不佳。文献[13]针对这一问题，提出一种三合一的轨迹预测函数(Traplan),该函数可快速地预测移动对象的运行轨迹，且函数中采用一种基于密度的区域探测算法对轨迹数据模式进行处理，挖掘轨迹运行模式，保证移动对象轨迹预测的准确性。出租车通过两路段之间的轨迹反映了司机对于该行驶路径的喜好程度，这是出租车司机基于以往的经验知识作出的合理选择。热点路段之间的连接存在众多的选择，不同的司机有不同的路径选择，但对于路况通顺、时较少的路径会是大多数司机的选择，因此，本文对众多经过热点路段之间的历史轨迹进行相似度计算，并作相应的轨迹聚类分析，进一步规范热点路段图的行车路线规划。通过聚类分析选取多数司机共同认可的行驶路径作为热点路段之间的较优行驶路径，为之后经过热点路段的出租车提供路径选择，热点路段间的轨迹聚类工作可有效地解决热点路段之间行车路径的选择问题，使路径规划更加符合历史经验规律，而不仅仅是计算得到的理论结果。

针对热点路段间的路径连接问题，本文从出租车载人轨迹中统计经过两个热点路段且其间没有包含其他热点路段的所有轨迹，并截取以该两热点路段为起止点的轨迹片段作为用来统计连接热点路段的轨迹集合。对这类轨迹进行聚类分析，并把轨迹间的编辑距离[14]作为轨迹间的相似性度量。若两个热点路段间的行驶时间远超出租车的平均行驶时间，则认为这两个热点路段之间不存在比较合适的直达路径，可通过其他路径实现热点路段间的连接。

对于轨迹相似度的计算方法中，由于本文的轨迹是由经过地图匹配后获取的路网中的路段连接而成，所以选用轨迹间的编辑距离计算轨迹之间的相似度。为了更加准确地计算轨迹的相似性，本文采用一种改进的实数代价编辑距离[15]作为轨迹间相似性的度量。该编辑距离采用欧几里得距离作为两位置点间的距离，并使用插入和删除操作的代价函数作为操作前后被修改轨迹之间的差异。因为GPS轨迹中的路段连接是按时序建立的,所以用插入和删除操作的代价作为插入或删除的坐标与当前状态前一个坐标的距离,而替换代价就用替换的两个GPS位置之间的距离表示。插入、删除，替换的实数代价编辑距离(Revised Edit distance with Real Penalty):

RERP(Tr1,Tr2)=

(3)

该计算公式是一个递归公式，式中:m、n分别为轨迹Tr1与Tr2的长度；ri为Tr1轨迹序列的第i个路段，sj为Tr2轨迹序列的第j个路段；轨迹Rest(Tr1)={r1,r2,…,rm-1}为Tr1中除去当前比较路段以后的剩余部分，Rest(Tr2)为Tr2轨迹剩余的部分。RERP(Tr1,Tr2)表示轨迹Tr1转化为轨迹Tr2的消耗，所有的操作都作用于轨迹Tr1。3种编辑操作即插入操作、删除操作和替换操作的代价公式分别为：

(4)

delete_cost(ri,sj)=

(5)

(6)

symmetricRERP=(RERP(Tr1,Tr2)+RERP(Tr2,Tr1))/2

(7)

利用上述公式可计算得到任意两条轨迹间的对称距离，即作为轨迹间的相似性度量。本文用来计算相似度的轨迹是轨迹中的一个片段，该片段不是出租车的一整条轨迹，而是一条轨迹中经过两热点路段间的一部分轨迹片段，且轨迹片段是用轨迹点的匹配路段编号序列表示，因此轨迹片段包含的路段数量不多，在计算过程中可保证较高的效率。在实际的计算过程中，暂时不考虑轨迹的长度，只需要提取多条轨迹路段中共同经过这两个热点路段间的部分，再通过聚类分析选取连接两热点路段的最佳路径。

本文选用DBSCAN聚类方法，在上述编辑距离的基础上对经过两个热点路段之间的轨迹路径集进行聚类分析，选取热点路段间最为出租车司机认可的行驶路径作为连接路径。

算法描述如下。

假设T代表经过两个热点路段的所有行车轨迹集合。

轨迹ε空间近邻 对于轨迹集合中的任意轨迹Tri，当其他轨迹Trj与Tri的时空距离小于ε时，认为轨迹Trj出现在轨迹Tri的ε空间近邻，称Trj是Tri的ε空间近邻，D为轨迹数据集，Dis(Tri,Trj)表示轨迹Tri与Trj之间的距离，表达式如式(8)所示:

N(Tri)={Trj∈D|Dis(Tri,Trj)≤ε}

(8)

核心轨迹 任意轨迹Tri的ε空间邻域内至少保证最少积累数目为MinLen的轨迹集，那么称该轨迹为核心轨迹，表达式如式(9)所示：

(9)

直接空间可达的轨迹 如果轨迹Trj在轨迹Tri的ε空间邻域内，并且Tri是核心轨迹，那么称轨迹Trj是从轨迹Tri出发直接空间可达的轨迹。

空间可达轨迹 如果轨迹Trj出现在核心轨迹Tri的ε空间邻域内，轨迹Trm出现在核心轨迹Trj的ε空间邻域内且不出现在Tri的空间邻域内，则称轨迹Trm是从轨迹Tri空间可达的。

空间连通的轨迹 如果存在轨迹Trj和Trm都是从轨迹Tri空间可达的，那么称Trj和Trm是空间相连的。

实现基于空间邻域密度的DBSCAN聚类算法时，可以选择从任意路段开始，计算该路段与其他路段间的空间距离；统计满足空间阈值ε范围的路段个数，并将其与最少路段积累数MinLen进行比较；若空间邻域范围内的路段数目大于给定的最少路段积累数时，该路段即为核心路段，形成一个以该路段为核心的聚类簇，其邻域内的直接密度可达线段也将聚到该类中，再对这些线段按照同样的方式依次进行聚类扩展，得到最终的聚类结果，即通过聚类分析出热点路段之间的连接路径。

基于编辑距离的聚类算法描述：

在第1阶段，首先根据编辑距离计算公式轨迹之间的编辑距离，即进行轨迹间的相似度计算，并计算轨迹段的ε-近邻集合(第1)行～第6)行)。第2阶段是对轨迹段进行聚类(第7)行～第19)行)，首先初始化聚类ID和轨迹段聚类标志，接下来遍历轨迹段，并计算轨迹的近邻域中的轨迹数量，若满足聚类阈值则对轨迹进行聚类ID标记，同时扩展聚类(第20)行～第30)行)到结束。

轨迹聚类算法伪代码如下。

算法：Trajectory Clustering based on Edit Distance。

输入：轨迹集合D={Tr1,Tr2,…,Trn}，相关参数：ε(近邻阈值)，σ(近邻数量阈值)。 输出：轨迹聚类集合Clus={ClusTr1,…,ClusTri,…,ClusTrn}；核心轨迹簇CoreST={CoreST1,…,CoreSTi,…,CoreSTn}。 /*第1阶段：轨迹相似度计算*/

1)

foreachTri,Trj∈D∧i≠jdo

2)

/*计算基于编辑距离的轨迹相似度*/

3)

CalculateEDIM(Tri,Trj);

4)

ifEDIM(Tri,Trj)≥εthen

5)

Nε(Tri)←Trj;

/*设定Tri的ε-近邻集合*/

6)

End for

/*第2阶段：对轨迹段进行聚类*/

7)

SetclusterId=0;

/*初始化聚类数标号，起初为0*/

8)

Mark all Trajectories as unclassified;

9)

foreachTri∈DandTriisunclassifieddo

10)

ifTriisvisited

/*判断轨迹是否被分类过*/

11)

continuenexttrajectory;

12)

MarkTriasvisited;

13)

Nε(Tri)=regionQuery(Tri,ε);

14)

ifsizeof(Nε(Tri))<σ

15)

MarkTriasNoise

16)

else

17)

IncreaseclusterIdby1;

/*表示聚类数加1*/ /*扩展轨迹的近邻聚类*/

18)

ExpandCluster(Tri,Nε(Tri),clusterId,ε,σ);

19)

End for

/*对可达近邻进行聚类*/

20)

ExpandCluster(Tri,Nε(Tri),clusterId,ε,σ)

21)

addTritoclusterId

22)

for eachTrj∈Nε(Tri)′

/*遍历近邻域中的轨迹*/

23)

if Trjisnotvisited

24)

markTrjasvisited/*计算轨迹Trj的近邻域*/

25)

Nε(Tri)′=regionQuery(Trj,ε)

26)

ifsizeof(Nε(Tri)′)≥σ

27)

Nε(Tri)=Nε(Tri) joined withNε(Tri)′

28)

ifTrjis not yet member of any cluster /*将轨迹Trj添加到类clusterId中*/

29)

AddTrjtoclusterId

30)

End for

基于编辑距离聚类算法的时间复杂度主要分为两部分：第1部分是编辑距离算法的复杂度，其值是O(mn),m为轨迹Tr1的长度，即Tr1的路段个数，n为轨迹Tr2的长度，即Tr2的路段个数。第2部分是DBSCAN聚类算法的时间复杂度，最坏的情况为O(n2)，n为两热点路段间的轨迹片段条数。因为本文中首先进行的工作是地图匹配，将轨迹中的轨迹点匹配到路网中相应的路段上，然后采用路段编号集合代替轨迹点集合来表示一条轨迹，用两热点路段间的轨迹片段集合代替轨迹点集合进行轨迹的聚类分析，因此轨迹片段的个数远远小于轨迹点的数目，所以在进行聚类算法时不存在计算量太大的问题。

4.3 基于热点路段图的路径规划

基于热点路段的查找和路径聚类分析所建立的热点路段图，可应用路径规划算法在基础路网和热点路段图中进行路径检索。在路径规划中引入启发信息能够提高搜索的效率。A*算法是目前最流行的启发式搜索算法，它通过选择合适的估价函数，使其寻找最优路径的搜索范围比原始Dijkstra算法要少很多。本文应用一种改进的A*算法[16]，该算法将当前临时标记节点到原点的最短路径、当前临时标记节点到目标节点的最短路径和当前临时标记节点的前一点到目标节点最短路径的三者之和作为从临时标记节点集合中选取永久标记节点的依据。改进A*算法的当前临时标记节点j的估计函数定义为：

f*(i)=g(i)+h*(i)+h*(j)

(10)

其中：是从起点到当前临时标记节点i的实际路径的量度；是从当前临时标记节点i到终点的最短路径的估计；i，j为邻近节点，且j为i的前一节点，i为j的后续节点。路径寻优算法采用的是改进的A*算法，在式(10)的基础上构造的一个时变启发函数：

F(i,T0)=λD[FD(i)+FDE(i)+FDE(j)]+λT[FT(i,T0)+FTE(i)+FTE(j)]+λS[FS(i,T0)+FSE(i)+FSE(j)]

(11)

其中：FD是车辆的行程指标；FT是车辆行驶的时间指标；FS是车辆行驶的威胁度指标；λD、λT和λS分别是行程加权系数、时间加权系数和威胁加权系数，综合指标最优的情况下，λD=3.5，λT=1和λS=1[14]；T0是车辆出发时刻；FDE(i)和FDE(j)分别是当前节点和其父节点到终点的曼哈顿距离；FTE(i)和FSE(i)是当前节点(xi,yi)到终点(xd,yd)的估价函数；FTE(j)和FSE(j)是父节点(xj,yj)到终点(xd,yd)的估价函数。根据该启发函数的优化结果，本文选取T0=0时，进行最优路径的计算。

依据城市电子地图路网数据以及热点路段图的信息，对于给定的起始位置数据，采用改进的A*分层算法，本文利用3段寻径的路径查找策略实现车辆的最短路径规划计算。基本步骤如下：

1)首先根据给定的始末位置S、D两点的GPS数据，并计算它们到热点路段图中最近热点路段的距离，若距离小于一定的距离阈值，认为起始位置位于热点路段图中，则应用改进A*算法在已建立的热点路段图中计算起始位置间的最优路径。

2)若起点S和终点D不在热点路段图中，设定以起点S和终点D为对角线形成的矩形区域R中存在热点路段，则在R中以最短路径算法搜索离S点最近的热点路段图入口S′路段，并且记录S-S′，同理，在R中范围内的热点路段图中搜索终点D的出口D′，并记录D-D′。应用路径规划算法分别计算热点路段图外S至S′的最优路径P1、热点路段图内S′至D′的最优路径P2和热点路段图外D′至D的最优路径P3。P1、P2和P3依次连接即是始末位置间的最优路径。

3)若起点S不属于热点路段图中或终点D不属于热点路段图，则应用路径规划方法计算热点路段图外S至S′的最优路径L1或热点路段图外D′至D的最优路径L2,以及热点路段图内S′至D′的最优路径P。L1和P的连接或L2和P的连接即是始末位置间的最优路径。

5 实验分析与比较

5.1 基础数据

本文构造的热点路段图所需要的实验数据主要包括基础路网数据和出租车真实载人轨迹两部分，其中基础路网数据选取深圳市交通道路电子地图数据，出租车GPS数据是深圳市1.3万多辆出租车在2011年4月18日至4月26日内的GPS采样点数据，经过提取得到约19万条有效轨迹数据。每天不同的时间段内，城市路网中的交通流会有所不同，且处于时刻变化中，出租车司机根据自己的驾驶经验相应地调整自己的行车路线适应交通流的变化，以达到较快行驶的目的，因而对于路径的规划需要将时间这一重要因素考虑在内。本文根据深圳市道路交通的特征与状况，选择4个具有代表性的时间段作为实验分析的依据，分别构造不同时间段内的热点路段图，并计算不同时间段内的最优行驶路径。

当前的路径规划算法一般分为基于路网数据的最短路径规划算法或在此基础上改进的最短路径算法以及基于出租车驾驶经验对路网进行分层的最短路径规划算法，本文分别选取最短路径(Shortest Path, SP)算法以及基于驾驶经验路网分层的路径(Experience Path, EP)规划算法与本文的基于热点路段图的路径(Hot-section Path, HP)规划算法进行对比。选取任意的20对起始-终止节点(Origin-Destination, OD)，利用这3种算法分别计算不同时间段内起点和终点间的最优路径，并统计规划路径的长度与所用时间来进行相应的比较。T表示时间段，每天不同时间段的划分如表1所示。

5.2 路径长度对比

如图4所示为4个不同时段内的规划路径长度对比。

利用SP、EP、HP这3种路径规划算法对随机选择的20个起止OD对进行路径规划，并统计分析规划路径的长度，结果如图4所示。柱状图的高度表示路径规划算法规划的每条路径总长度。根据柱体的高度可以得出，在距离上，相对EP和HP算法来说，由SP算法规划得到的路线距离较短，而EP和HP算法在计算路径时由于趋向于所选取的经验路段，因此容易发生绕路的现象。若OD对之间隔得很近，因为OD对之间可能存在经验路段，EP和HP算法会将相应的经验路段计入其中，但相较于EP算法，本文的HP算法计算得到的路径距离略优。对于EP算法和本文的HP算法，对比柱状体高度可以得出，两者计算得到的路径在距离上相差较小。综合比较4个时间段内规划的路径总长度，如图5所示，可以看出处于高峰期时，OD对之间规划的路径长度大于平峰期的路径长度。晚高峰时的规划路径长度大于早高峰期的路径长度，夜间的平峰期的规划路径长度大于日间的平峰期的规划路径长度。

表1 时间段划分

图4 不同时间段的路径长度比

图5 3种算法不同时间段的总路径长度对比

如图6所示为4个不同时段内的规划路径行程时间对比。

如图6所示，分别对应4个时间段内3种算法规划路径的耗时时长走向，3种不同类型的曲线代表3种路径规划算法。4个时间段表示城市中的4种交通流状况，对比折线图的变化可以发现，当路程距离增加时，OD对路程较近的EP算法与本文的HP算法的耗时相对可能会高于最短路径用时。路径长度超过10 km时，EP算法与HP算法趋向于花费更少的时间，且用时相近。对比EP算法与HP算法，两种算法在图中走向近似且时间长度也相近，但本文的HP算法优于EP算法，统计结果如表2所示。表2中给出的路径总规划用时表示在经过DBSACN聚类算法得到的热点路段图的基础上使用改进的A*算法进行路径规划所用的时间，SP和EP算法分别是基于基础路网和经验路网实现的路径规划算法。相比这两种算法，本文的算法是在对经验路网的进一步改进后得到的热点路段图的基础上实现的，首先根据出租车司机的经验获取经验路段，并把经验路段看作热点路段，再对热点路段之间的连接作聚类分析的工作，包括对经过热点路段之间的轨迹片段进行相似度的计算实现轨迹的聚类分析，以及将聚类得到的轨迹作为连接两个热点路段的路径，进一步提炼经验路网得到热点路段图，并把热点路段图作为路径规划的依据。HP算法是在热点路段图的基础上实现的路径规划算法，相较于SP和EP算法所使用的基础路网和经验路网，用HP算法规划路径时考虑的路段更少，因此计算得到的规划时间少于SP和EP算法的规划用时。本文选取的20个OD对在4个时间段内的测量结果中，HP算法相较于EP算法，实际路径总长度缩幅约为18.73%,总的用时缩幅约为11.64%。对比3种算法的计算用时，运算时间在150 s～380 s，本文的算法计算用时为152 s，在规划路径用时上效率较高，有较大的计算优势。在柱状图7中显示了4个时间段以及每个时间段内的总耗时，对比4个时间段的柱状体高度可以得出，早、晚高峰期的用时高于平峰期的用时，且晚高峰用时相对低于早高峰期。对比3种算法总的路径耗时柱状图的高度可得出本文的HP算法规划的路径在行程时间上优于EP算法和SP算法所规划的路径行程用时。

图6 不同时间段的路径行驶耗时对比

图7 不同时间段3种算法的路径总耗时对比

6 结语

本文通过分析出租车GPS轨迹数据的特点，提取真实的载人GPS轨迹数据，并实现轨迹数据到路网数据的地图匹配。根据地图匹配的结果，分析出租车行驶路线规律，并统计路网中路段的访问频次，据此选取访问频次较高的路段为热点路段，进而对连接热点路段间的行车轨迹实现轨迹相似度的计算，完成路段之间真实载人轨迹的聚类分析。充分利用驾驶员的行车经验实现热点路段间的连接，并完善热点路段图的建立，且在此基础上提出融合出租车驾驶经验的路径规划方法。相比之前的路径规划算法，本文提出的方法在经验分析和数据统计两方面作了进一步的研究：一是将传统的以侧重路径计算为中心的路径规划方法变为以数据为中心的数据驱动方法，充分利用了轨迹数据中的隐含信息；二是对经验路网的改进，传统的经验路网仅根据驾驶员的经验获取访问频次较高的路段，以此构建基础的经验路网，本文首先根据驾驶经验获取高频路段，即热点路段，然后对连接两个热点路段的轨迹进行相似度的计算并作进一步的聚类分析，以实现热点路段图中两热点路段的连接，从而得到更加精简的热点路段图，热点路段图的建立是对出租车司机经验智能最大化的体现，在计算最短路径时可更加注重轨迹数据挖掘所得到的知识，减少了常规的路径计算，提高了路径规划的效率，最后在热点路段图的基础上，使用改进的A*算法可更高效快速地找到符合人们日常出行的路径。

表2 路径搜索相关参数

最后本文选取深圳市的路网数据与出租车载人轨迹数据，对路径规划的结果进行比较分析，结果显示本文提出的基于热点路段图的路径规划方法在行车时间上更优，更具有出行指导意义。

References)

[1] ZHENG Y. Trajectory data mining: an overview [J].ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 29-70.

[2] ZHUANG L J, GONG J F, HE Z C, et al. Framework of experienced route planning based on taxis’ GPS data [C]// Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems. Piscataway, NJ: IEEE, 2012: 1026-1031.

[3] YUAN J, XIE X, ZHENG Y, et al. T-Drive: enhancing driving directions with taxi drivers’ intelligence [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 220-233.

[4] YUAN J, ZHENG Y, ZHANG C Y, et al. T-Drive: driving directions based on taxi trajectories [C]// Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2010: 99-108.

[5] 唐炉亮,常晓猛,李清泉.出租车经验知识建模与路径规划[J].测绘学报,2010,39(4):406-412.(TANG L L, CHANG X M, LI Q Q. The knowledge modeling and route planning based on taxi’ experience [J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 406-412.)

[6] YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world [C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York: ACM, 2011: 316-324.

[7] VINCENT W Z, ZHENG Y, XIE X, et al. Towards mobile intelligence: learning from GPS history data for collaborative recommendation [J].Artificial Intelligence, 2012, 184(1): 17-37.

[8] YUAN J, ZHENG Y, ZHANG C Y. An interactive-voting based map matching algorithm [C]// Proceedings of the 11th International Conference on Mobile Data Management. Washington, DC: IEEE Computer Society, 2010: 43-52.

[9] LI Y, HUANG Q X, KERBER M, et al. Large-scale joint map matching of GPS traces [C]// Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 214-223.

[10] LI Q Q, ZENG Z, ZHANG T, et al. Path-finding through flexible hierarchical road networks: an experiential approach using taxi trajectory data [J]. International Journal of Applied Earth, Observation & Geoinformation, 2011, 13(1): 110-119.

[11] HU J H, HUANG Z, DENG J. A hierarchical path planning method using the experience of taxi drivers [C]// Proceedings of the 13th COTA International Conference of Transportation Professionals. Amsterdam: Elsevier, 2013: 1898-1909.

[12] QIAO S J, HAN N, ZHU W, et al. TraPlan: an effective three-in-one trajectory prediction model in transportation networks [J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3): 1188-1198.

[13] QIAO S J, TANG C J, JIN H D, et al. PutMode: prediction of uncertain trajectories in moving objects databases [J]. Applied Intelligence, 2010, 33(3): 370-386

[14] LEVENSHTEIN V I. Binary codes capable of correcting deletions, insertions and reversals [J]. Soviet Physics Doklady, 1966, 10(8): 707-710.

[15] 刘坤,杨杰.基于编辑距离的轨迹相似性度量[J].上海交通大学学报,2009,43(11):1725-1729.(LIU K,YANG J. Trajectory distance metric based on edit distance[J]. Journal of Shanghai Jiao Tong University, 2009, 43(11): 1725-1729.)

[16] 张翼,唐国金,陈磊.时相关车辆路径规划问题的改进A*算法[J].控制工程，2012,19(5):750-756.(ZHANG Y, TANG G J, CHEN L. Improved A*algorithm for time-dependent vehicle routing problem [J]. Control Engineering, 2012, 19(5): 750-756.)

This work is partially supported by the National Natural Science Foundation of China (51579202), the China Postdoctoral Foundation (2015T80848).

QIXin, born in 1978, Ph. D., associate professor. His research interests include Web data mining, intelligent Web system.

LIANGWeitao, born in 1990, M. S. candidate. His research interests include Web data mining, intelligent transportation.

MAYong, born in 1983, Ph. D., associate professor. His research interests include intelligent maritime security technology, unmanned craft path planning.

Optimalpathplanningmethodbasedontaxitrajectorydata

QI Xin1, LIANG Weitao1*, MA Yong2

(1.SchoolofComputerScienceandTechnology,WuhanUniversityofTechnology,WuhanHubei430063,China;2.SchoolofNavigation,WuhanUniversityofTechnology,WuhanHubei430063,China)

Focusing on the issue that the path calculated by traditional path planning algorithm is not necessarily the optimal path in reality, a path planning algorithm which combined the experience of taxi driving and took time as a measure was proposed. The implementation of this algorithm was to transform the path planning technology which took calculation as the center into data-driven mining technology which regarded data as the center. Firstly, the real manned trajectory data were extracted from a large number of taxi trajectory data and matched to the road network data. Then, the access frequency of the road segments were calculated according to the calculation results of map-matching, and Top-kroad sections were selected as hot sections; Secondly, the similarity of road tracks between hot sections was calculated, and the trajectories were clustered to buildksections of hot road map based on the road network. Finally, an improved A*algorithm was used to calculate the optimal path. The experimental results show that compared with the traditional shortest path planning algorithm and the path planning algorithm based on hierarchical road network, the path planning method based on hot section map can shorten the length of the planning path and the travel time and improve the time efficiency of path planning.

intelligent transportation; taxi driving experience; improved A*algorithm; hot section map; path planning

TP393.027; TP391

:A

2017- 01- 13;

:2017- 02- 25。

国家自然科学基金资助项目(51579202)；中国博士后基金资助项目(2015T80848)。

戚欣(1978—)，男，湖北武汉人，副教授，博士，主要研究方向：Web数据挖掘、智能Web系统； 梁伟涛(1990—)，男，山东临沂人，硕士研究生，主要研究方向：Web数据挖掘、智能交通； 马勇(1983—)，男，湖北枣阳人，副教授，博士，主要研究方向：智能海事保障技术、无人艇路径规划。

1001- 9081(2017)07- 2106- 08

10.11772/j.issn.1001- 9081.2017.07.2106