融合出租车驾驶经验的层次路径规划方法

胡继华，黄 泽，邓 俊，谢海莹

(中山大学工学院智能交通中心，广州 510006)

1 引 言

近几年来，智能交通系统(ITS)快速发展，路径规划算法作为其中的一个关键技术，能够有效地帮助司机规划驾驶路线，避免拥堵、减少出行成本.目前，大部分车辆导航中的路径规划算法具有的一个共同特点是力求通过计算机数据结构和运筹学方法，从理论上减少搜索算法的时间复杂度，而忽略了实际城市道路网络中的道路一般都具有不同的等级，容量限制等特性，得到的是数学意义上的最短路径，不能真正符合驾驶员的行车期望和要求.层次搜索策略则是结合了道路网络的分层特性和经典的最短路径算法所提出的一种新型搜索策略，可以有效地提高搜索效率，更好地符合驾驶员的实际驾驶要求.因此，对于层次搜索策略的研究也得到了越来越多学者的关注.

层次搜索策略，在人工智能领域比较著名，也被称为“抽象”问题解决策略.Plolya首次在道路网络搜索中引入层次概念.此后，这个概念被Sacerdoti［1］，Korf［2］和许多其他研究人员［3-7］进一步探索.国内不少学者对此进行了深入研究，利用层次搜索策略对路径规划算法进行优化［8-11］.在以往大部分研究中，是根据道路属性对路网进行分层，这样的分层方式有两方面不足:一是所得到的分层路网是静态的，不能很好地反映实际的动态路况;二是没有充分考虑驾驶员的驾驶期望.

近几年，在国内外的车辆导航研究中，出租车驾驶员经验的重要性逐渐凸显出来，越来越多的研究学者们将其应用到基于实时交通信息的动态导航中［12，13］.结合出租车驾驶员经验设计的路径规划算法，能够根据历史经验，避开发生拥堵概率高的路段，减少出行时间，计算得到的路径可能不是最短路径，但却是最优路径.因此将出租车驾驶员路径选择经验融入到路径规划算法，可以为公众出行提供一个更加合理、快捷的规划路径.

本文以广州市为研究区域，利用匹配后的广州市出租车浮动车数据，提取出广州市出租车行驶轨迹，并根据各路段行驶频率高低对路网进行合理分层，构建基于出租车经验路径的分层路网.结合经典的Dijkstra算法，本文设计一种融合出租车驾驶经验的路径规划方法.最后，将本文提出方法计算得到的规划路径与经典路径规划算法的结果作比较，从路径长度，行程时间等方面进行对比分析与验证.

2 技术路线

出租汽车驾驶员选择的路径往往综合考虑了拥堵程度、行程时间、道路等级、周边环境及费用等多种因素.因此，本文结合出租车驾驶员经验和层次搜索策略，通过构建经验等级路网的方法对最短路径算法进行优化.

主要技术路线如下:

首先，对采集得到的出租车浮动车数据进行预处理，在地图匹配的基础上，提取基于GPS数据的出租车行驶轨迹.

然后，通过速度阈值的方法从大量的出租汽车行驶轨迹中筛选出经验路径，并且统计每条道路在限定时间内通行的次数，根据次数的高低构建经验道路等级路网.

最后，在等级路网的基础上，实现基于出租车经验路径的层次路径规划算法.

技术流程如图1所示.

图1 技术流程Fig.1 Technical process

3 出租车经验路径提取

出租车在空载和重载的时候其行为特点有较大的不同，因此，在地图匹配的基础上，本文对出租车的行驶轨迹进行分割，分别为空载和重载时的轨迹.通过车辆状态的转变，将出租车的每一次载客或空载的行驶轨迹信息进行分割，通过车辆状态的切换得到出租车的行驶轨迹集，从而可以提取出租车的每一次载客或空载的轨迹.

图2为出租车一次载客轨迹中序列，图中粗线路段为轨迹序列.

图2 出租车一次载客轨迹中的Seq序列Fig.2 Sequence of taxi trajectories

4 经验分层路网下的路径规划

4.1 经验轨迹集筛选

由于出租车在载客和空车时的驾驶行为有所不同，因而我们需要通过轨迹的平均行驶速度进行筛选，将速度低于给定阈值的行驶轨迹排除在外.设vi为轨迹i的平均速度，vT为速度阈值，一般为所有载客路径的平均速度.则符合经验路径筛选条件的轨迹集如下式所示:

由于不同的时段，路段的交通状况不同，出租车驾驶员对道路的选择会不同，对出租车的出行需求也不同，因而有必要将符合经验路径筛选条件的轨迹集限制在某个时间段内.设时间间隔为T，则有在时间区间T内的经验轨迹集为

式中tis为轨迹的开始时间;tim为轨迹的结束时间.

4.2 基于经验轨迹的道路分层

城市道路一般分为快速路、主干道、次干道和支路四个等级，但是城市道路等级并不能完全反映实际交通状况的等级.本文根据筛选得到的出租车行驶的经验轨迹集，对城市路网各时段出租车在各道路的出现次数进行统计，作为城市道路经验分级的依据，实现对城市路网各道路的经验分级.设ni(t)为给定时间区间内路段的出租车轨迹通行次数总和，则有

式中ni(t)，Ni为路段i在时间间隔T内的经验轨迹集中的所有浮动车通过路段i的轨迹总和;m为出租汽车总数;n为路段总数.

ni(t)的值越大，说明出租车司机越偏向选择路段i，反之亦然.通过将其值按高到低进行排序对道路进行分级.假设城市路网的所有路段被分成d个等级，gd为第d等级的最小满足通过次数，Hd为属于d等级的道路集，则有

4.3 算法实现

构建好经验道路网络之后，我们可以应用分层路网的路径规划算法进行路径搜索.算法流程如下:

Step1如图3(a)所示，如果起点S、D都在经验路网层，那么直接在经验路网层搜索最短路径.

图3 算法实现Fig.3 Implementation of algorithm

Step2如果起点S不在经验路网层，若设定的矩形区域R2中存在经验路网层道路，则在R2中以最短路径算法搜索离S点最近的经验路网层入口S'，并且记录S-S'，同理，在R2中范围内的基础路网中搜索终点D的出口D'，并记录D-D'，否则转Step4.

Step3以S'，D'在经验路网层搜索最短路径，并且拼接各段局部路径得到完整的路径.

Step4在R2范围内的基础路网上用Dijkstra算法搜索最短路径.

本文算法中，通过限定搜索区域的方法，确定是否需要寻找高层的出入口和在合适的范围内寻找高层的出入口.如图3(b)所示，首先根据S和D的连线为对角线形成一个矩形R1，然后将R1的各边向外扩展一个阈值h，形成矩形R2，R2则为算法中用于判断是否需要搜索经验路网层出入口以及搜索出入口时的范围条件，算法中h的值取0.001度.算法流程图如图4所示.

图4 算法流程Fig.4 Algorithm flow

5 实例计算与结果分析

5.1 数据基础

本文选取广州市交通道路电子地图为基础实验数据，路段数为3 042，节点数为2 112.出租车GPS数据是广州市1.7万多辆出租车在2011年6月18至7月18一个月时间的GPS采样点数据，经过提取得到约2 900多万条有效轨迹.由于路网规模不大，所以在本文中，将路网分为两层，分别为高使用频率路网层与低使用频率路网层，实验中计算路径的行程时间需要的道路速度，是通过广州市主干路网交通状态分析与评价系统中的一个月的以5分钟为间隔的道路平均速度在对应的四个时段计算得到的平均速度.

实验分析的图表中，SP代表最短距离路径算法，EHP代表基于经验道路分层路网的路径规划算法，RHP代表城市路网中以道路等级为5和6的道路形成的高等级路网的道路分层路径规划算法.三种算法均用于计算任意OD对间的最短路径，因此，实验中随机生成了30个OD对，分别用以上三种算法计算其不同的路径.

对于EHP算法，由于城市交通各路段在不同时段交通流量是在时刻变化的，出租车司机在平峰和高峰时段对于道路的选择也会进行相应的调整，根据出租汽车的经验路径构成的道路等级划分也会有所不同，因而对路网道路进行经验分层时需要结合时间进行考虑.本文根据广州城市道路交通的特点与状况，选取了4个具有代表性的时间段分别建立4个经验道路等级及路网，并且用EHP算法分别计算不同时段的路径.具体的时间段划分如表1所示.

表1 时段划分表Table 1 Period division

5.2 不同时段经验路网

由于不同的时段，各道路的交通状态会有所不同，因此经验轨迹集也根据不同的时段进行提取，图5为未经分层处理的广州路网图，图中(a)(b)(c)(d)分别为图中方框部分在不同时段经过分层处理的经验等级道路图，图中黑色粗线的路段为高使用频率道路，即被划分为经验等级道路.从图中可以看出，尽管4个时间的道路层次分布图比较类似，但是还是较为细微的差别，这说明，不同的时间段出租车司机对道路的选择还是有区别的.

图5 不同时段的经验等级道路图Fig.5 Experiential road hierarchy for four time intervals

5.3 路径长度比较

图6显示的是四种算法得到的路径的长度比较，柱体的高度代表的是路径的长度，右手边的垂直轴代表的是RHP，EHP，SP三种算法与最短路径算法的长度之比.在此，本文选取了时间段7:00-9:00和12:00-14:00以作说明.从图6中可以看出，RHP算法的路径长度与SP算法的路径长度的比值幅度变化大，尤其是路径较短时，更为明显.RHP算法由于趋向于走高等级道路，因此容易出现绕路的情况，即使OD之间的距离很近，也会选择走高等级道路，EP算法得到的路径长度与SP算法的路径长度之比相对平稳.

图7为三种算法下的30个OD对的路径总长在各个时段的对比图，总体来看SP算法的路径总长最短，RHP算法的路径总长最长，而EHP算法的路径则处于两者之间.

5.4 行程时间比较

图8显示的是四种算法得到的路径的行程时间比较，柱体的高度代表的是行程时间，右手边的垂直轴代表的是RHP，EHP，SP三种算法的行程时间之比.在此，本文选取了时间段7:00-9:00和12:00-14:00以作说明.对于EHP算法而言，算法的结果在大约只有75%左右的结果小于或等于SP算法的结果，而RHP得到的结果只有66%左右的OD对的行程时间等于或小于SP算法得到的行程时间.与EHP算法得到的路径的行程时间相对于路径长度最短SP算法的行程时间的比值而言，ratio(RHP/SP)的值不稳定性较大，在路径长度较短时波动较大.

图9表明在行程时间总体上EHP算法最短，接着为RHP，SP算法的行程时间总和最长.但是RHP与SP的相差不大.

图9 三种算法30个OD对的行程时间总和对比图Fig.9 Total travel time comparison for three algorithms

6 研究结论

本文针对出租车GPS数据的特点，提取出租车行驶轨迹.结合出租车行驶轨迹对不同时段下的出租车在各个路段的通过频次进行统计，提取了基于出租车驾驶员经验选择的等级路网，在此基础上提出融合出租车驾驶经验的层次路径规划方法.相比于经典的最短路径规划算法，该方法具有两方面的优势:一是利用了层次搜索策略，在分层路网的基础上进行遍历，大大减少了计算量;二是融合了驾驶员经验，所得到的分层路网是动态路网，能够反映实时路况，使规划结果更加合理.

最后，本文以广州市路网为计算实例，随机生成30个OD对，从行程时间和路径长度两个方面与传统以长度为准的最短路径算法及自然道路分层的路径规划算法进行了对比与分析.结果显示，相比于其他两种路径规划算法的计算结果，使用本文所提出的方法得到的路径要更加优越，行程时间较短，并且可根据不同的时段进行动态调整.

［1］Sacerdoti E D.Planning in a hierarchy of abstraction spaces［J］.Artificial Intelligence，1974，5(2):115-135.

［2］Korf R E.Planning as search:A quantitative approach［J］.Artificial Intelligence，1987，33(1):65-88.

［3］Jung S，Pramanik S.An efficient path computation model for hierarchically structured topographical road maps［J］.Knowledge and Data Engineering，IEEE Transactions on，2002，14(5):1029-1046.

［4］Jagadeesh G，Srikanthan T，Quek K.Heuristic techniques for accelerating hierarchical routing on road networks［J］. Intelligent Transportation Systems， IEEE Transactions on，2002，3(4):301-309.

［5］Chou Y L，Romeijn H E，Smith R L.Approximating shortest paths in large-scale networks with an application to intelligent transportation systems［J］.INFORMS Journal on Computing，1998，10(2):163-179.

［6］Liu B.Route finding by using knowledge about the road network［J］.Systems，Man and Cybernetics，Part A:Systems and Humans， IEEE Transactions on，1997，27(4):436-448.

［7］Car A，Frank A.General principles of hierarchical spatial reasoning:the case of wayfinding［C］.1994:646-664.

［8］翁敏，毋河海，杜清运，等.基于道路网络知识的启发式层次路径寻找算法［J］.武汉大学学报:信息科学版，2006，31(004):360-363.［WENG M，WU H H，DU Q Y，et al.A heuristic and hierarchical wayfinding algorithm based on the knowledge of road network［J］.Geomatics and Information Science of Wuhan University.2006.31(004):360-363.］

［9］高松，陆锋.一种基于路网等级启发式策略的路径搜索算法［J］.地球信息科学学报，2009，11(2):151-156.［GAO S，LU F.A path finding heuristic algorithm for a road network hierarchy［J］.Geo-Information Science，2009，11(2):151-156.］

［10］武雪玲，李清泉，任福.基于分层分块数据组织的双向A*算法［J］.测绘信息与工程，2006，31(6):1-2.［WU X L，LI Q Q，REN F.Bidirectional A*algorithm based on hierarchicaland block data organization［J］.Journal of Geomatics，2006，31(6):1-2.］

［11］钟慧玲，章梦，石永强，等.基于路网分层策略的高效路径规划算法［J］.西南交通大学学报，2011，46(4):645-650.［ZHONG H L，ZHANG M，SHI Y Q，et al.Efficient route plan algorithm based on multi-level road network strategy［J］. JournalofSouthwest Jiaotong University，2011，46(4):645-650.］

［12］唐炉亮，常晓猛，李清泉.出租车经验知识建模与路径规划算法［J］.测绘学报，2010，39(4):404-409.［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):404-409.］

［13］杨扬.基于实时交通信息的最优路径规划问题的研究［D］.上海交通大学，2009.［YANG Y.Optimal path planning problem under real-time traffic network［D］.Shanghai Jiao Tong University，2009.］