基于城市道路网的快速路径寻优算法
第28卷 第12期Vol.28 № 12・ 博士论文・
计 算 机 工 程Computer Engineering
文章编号：1000—3428(2002)12 —0036—03
文献标识码：A
2002年12月 December 2002
中图分类号： TP301.6
基于城市道路网的快速路径寻优算法
毕 军1，付梦印1，周培德2，张宇河1
(1.北京理工大学自动控制系；2.北京理工大学计算机科学与工程系，北京100081）
摘 要：从城市道路网的特点出发，描述了矢量化的城市道路网的存储结构，提出一种求解城市道路网两节点间最短路径的算法。算法基于双向式搜索原理，采用投影法、夹角最小的方法及二叉树理论。和Dijkstra算法相比，算法大大减小搜索空间，提高搜索速度，时间复杂性不超过O(N)，N为网络节点数。实际应用表明算法有很强的实用性和可靠性。关键词：最短路径；路径规划；城市道路网
A Fast Algorithm for Optimum Path Based on a City Road Net
BI Jun1，FU Mengyin1，ZHOU Peide2，ZHANG Yuhe1
(1.Department of Automatic Control, Beijing Institute of Technology；
2.Department of Computer Science and Engineering, Beijing Institute of Technology, Beijing 100081)
【Abstract】According to the characteristics of a city road net, this paper discusses a kind of data structure of road net and proposes an algorithm for seeking the shortest path between two points in the road net. The algorithm takes advantage of the theories of bidirectional search, projection, minimum angle and binary tree. Compared with Dijkstra algorithm, the algorithm can reduce seeking space and can raise seeking speed greatly, and its time complexity can not exceed O(N), while N is the number of road net points. The application results show that the algorithm has good practicability and reliability.【Key words】Shortest path；Path planning；City road net
节点进行编号，采用邻接表的链式存储结构[1]。在邻接表最短路径问题是网络分析中的一个重要问题，求解该问
中，对图中的每个节点建立一个单链表，每个单链表都有表题的方法有很多，目前公认的、较优的求解方法是著名的
Dijkstra算法。该算法是基于图论中的网络模型，在求解时结点和表头结点构成。第i个单链表的w个表结点表示和图中
第i个节点相关联的w条边。链表的表头结点以顺序结构形式有可能并准备搜索所有的网络节点，算法的时间复杂度为
[1]2
O(N)，N为网络节点数。所以在城市道路网节点数较大的存储，以便随机访问图中任一节点的单链表。因此，采用邻情况下，算法求解速度慢，花费时间长，效率低。而实际有接表的链式存储结构，很容易找到和图中任一节点相关联的些系统，如我们研发的基于城市道路网的自主车辆导航系边，便于算法的编程实现。单链表的表头结点和表结点的结统，要求快速地为车辆规划出从起点到终点的最短距离行驶构如下：
表头结点表结点路径，即路径规划的快速性要求较高，显然Dijkstra 算法很
难满足快速要求[2]。NamePositionWeightNextNextWeightPosition
城市道路网一方面包含网络本身的拓扑特征，另一方面Name：节点编号；Position：节点位置坐标；First：指向链表还包含了大量的反映地理位置特征的经纬度数据以及与应用中的第一个表结点；Next: weight:指向链表中的下一个表结点；边有关的数据。所以，快速求解道路网两节点间的最短路径，的权值。
[3]
应考虑道路网本身特点。本文根据道路网的特点，采用双2 算法描述向搜索和投影法，提出一种快速地求解最短路径的算法。该2.1 算法的基本思想算法搜索空间小，求解速度快，算法的时间复杂度不超过 从几何学中知道，两点间直线最短。在道路网图中，如O(N)，在实际自主车辆导航系统中的应用证明了算法的实果两节点间存在一条边，则该边为两节点间的最短路径。若用性和可靠性。不存在一条边，则连接两节点的直线段代表了一个路线的趋
1 矢量化的城市道路网的存储
计算机不可能从位图中寻找路径，因为位图仅保存了点的信息，点与点间的拓扑关系没有体现。计算机存储的是矢量化的城市道路网图，由节点、边及相应的拓扑关系构成的。节点是道路的交叉点或端点，有相对的经度、纬度地理坐标；边是两节点间的一段道路，用于表示分段道路，边的权值定义为道路距离。所有的边都是直线段，对于实际道路网中弯曲较大的路段，可在路段上插入一系列节点，于是该路段由一些弧度较小的路段构成，弧度较小的路段可视为一条边[3]。
道路网图的存储方法是影响算法搜索速度和时间复杂度的一个重要因素。根据算法的特点，对道路网图中的每一个
势，顺着连线方向的某条边是最短路径的可能性较大[3]。
算法采用双向搜索，从起点S进行正向搜索，同时从终点T进行逆向搜索。两个方向在每一步都要搜索和指定的直线段夹角最小的边或搜索和直线段左右两侧各一条夹角最小的边，并利用投影法来判断双向搜索是否能会合。会合后，从搜索到的起点到终点的路径中取距离最短的路径为所求解。若不能会合，则从当前节点继续搜索，直到终点T或起点S，取两个方向搜索到的距离最短的路径为所求解。
—36—
2.2 算法实现
输入：采用邻接表结构存储的矢量化的道路网。起点S、终点T为网络中任意指定的两个节点。
输出：S与T之间的一条最短路径及其长度。
步1：连接S和T成直线段，计算的长度，设长
度值为K，设计数变量i=1。定义起点S为原点，终点T为目标点。
ST步2：如果与之间存在一条边，则该边即为所求路
径，否则，转步3。
步3：分别从S出发(正向搜索)、T出发(逆向搜索)寻找与STTSAi ,Bi()至ST、TS的投影点A'i，B'i，计算SA'i(S始终为原点)，TB'
i
i
步8：在两棵二叉树中，由会合点(或会合边e两端点)开始沿与会合点相关联的两条边(或与e端点相关联的边)依次寻找求解的最短路径的节点，加入路径队列，直至达到S、T，便得到最短路径队列，终止。2.3 算法讨论
整个算法分为两部分，即步1—步5的初始解算法部分和步6—步8的优化解算法部分。在初始解算法中，双向搜索每经过一个节点只选中与两个节点间的直线段夹角最小的边，所以初始解算法搜索空间小，搜索速度快。但如果频繁地在两个相邻时刻选择的边产生左右方向的振荡，则有可能求解的最短路径大于实际最短路径，即得到一个次优解，而不是最优解。初始解只是为优化算法作准备，用于减小二叉树的规模。在优化解算法中，双向搜索在经过每个节点的同时， )的长度，分别设为αi,βi。 i(T
进行节点与T或S间直线段左右两侧各一条夹角最小的边的 将|SA|(S始终为原点)，αi作为活动点A的两个标
为当前节点，对正向搜索得到两条边GA1，搜索，例如，G
GA
2
记；TB'i(T始终为目标点),βi作为活动点Bi的两个标记。即
活动点的第一个标记是原点或目标点至该活动点子路径V上
V的当前边的活动点在ST或TS上的投影点与原点或目标点间的长度。
ii=i+1。步5： 用Ai ,Bi分别代替S,T,然后计数变量自增，
重复步2至步4，但步3中的活动点总是投影到原点、目标点的直线段ST或TS上，直至Au，Bu(称为会合点)或者Au ,B
u
，且
f(GT,GA
1
)=min(
k2
f(GT,GA
k1
))
，
f(GT,GA2)=min(
f(GT,GA
k1
1
))
，
f
(p1，p2)是
为边e的(称为会合边)的两节点,e在ST上的投影设为 e。点列S，A1，...,Au，Bu，...，B1，T组成初始路径。并且会合后
'
'
αi+βi=K，或者αi+βi+=K。若αi+βi>K，表明双G步搜索与GT(正向，T为固定目标点)或GS(逆向，S为固定原点)间夹角最小的边，直到搜索到T或S,得到两条路径P1(正向)，P2(逆向)，取P=min(P1, P2)为所求解初始路径。计算初始路径的长度，设为L。
步6：令S、T分别为两棵二叉树的根节点，分别从S(正向)、T(逆向)出发，进行与直线段ST、TS左右两侧各一条夹角最小的边的搜寻，把搜索到的边加入对应的二叉树，对二叉树的活动节点作步4所述的两个标记。然后，从搜索到的边的活动点出发，进行活动点与止点(正向，止点始终为目标点；逆向，止点始终为原点)之间直线段左右两侧各一条夹角最小的边的搜寻，把搜索到的边加入对应的二叉树，对二叉树的活动节点作两个标记。以此类推，直至 αi+βi=K(会合于点)或(会合于边)，生成两棵特殊的
6-1和步6-2中的方αi+βi+e'=K
步6-1：若当前活动点是相应的方向搜索已访问过的点，则不把活动点加入相应的二叉树。若活动点的第一标记值小于已访问点的第一标记值，则活动点的父节点作为已访问点的父节点，并相应地改变已访问点的所有子节点的第一标记值。
步6-2：如果活动点的第一标记值与活动点至点T(正向)或S(逆向)的直线段距离之和大于L，则在二叉树中删去活动点及其相关联的边。
αi+βi=K时，会合点处两个第一标记的和，步7：当
其最小值(会合点多于2个时)记为路径长度r1。当αi+βi+e'=K时，会合边e两端点的第一标记之和加上|e|,(2条时)记为r2。计算r=min(r1,r2)，r为所求最短路径长度。
p1，p2夹角的函数，∈D，GAk2∈D2，D1为所求直线有和GGT夹角为正的边的集合，D2为所有和G相
GT夹角为负的边的集合。将搜索到的边分别加入关联且与
两棵二叉树，随着二叉树深度的增加，相应地扩大了搜索空间，增大了双向搜索会合的概率。从搜索到的诸多路径中取距离最短的路径，便得到一个最优解。
从理论上讲，若网络节点数很少，则步6中的双向搜索可能不会合，那么从当前活动点分别进行搜索直到S或T。但通常实际城市道路网的节点数很多，因此步6中的双向搜索容易会合。
双向搜索是从起点和终点同时搜索，在中间相遇的可能性较大。和单向搜索展开的节点数相比，双向搜索展开的节
[4]
。因而算法采用双向搜索，能大大点数至少可以减少50%
减小搜索空间，提高搜索速度。
3 算法分析
算法的分析通常以一定的模型为基础，图1所示的道路网模型的特点：(1)结构是正方形；(2)网络节点呈均匀分布，若节点数为N，则和正方形四条边平行的边上的节点数
，图
14。为图1 道路网模型
显然，步1、步4只用常数时间。城市道路网采用邻接表的存储方法，则步2和步3的时间复杂性和节点相关联的边数w成线性关系，根据矢量化的道路网的特点，通常w为常数且w≤4，因此可认为步2和步3 1 只用常数时间。在图所示的道路网模型中，步5中双向搜索会合于点或会合于边后，每个方向搜索的节点数不超过 N，所以步5的时间复杂性不而会合条件α+β=K或α+β+e=K的判断需要两重循环，所以时间复杂度不超过O(N)。步7的时间复杂度和会合
i
i
i
i
N)。在步6超过O(中,每个方向能会合的节点数不超过N,
—37—
东，沿太白中路，经过五交化、百货大厦、济宁宾馆等节点到和浣笔泉路交叉口，然后沿着浣笔泉路向北直到核桃园路口节
点；逆向搜索从终点向西，沿红星中路，经过司法局路口、保险公司路口、报社路口等节点到和浣笔泉路交叉口，然后沿着浣笔泉路向南到核桃园路口节点。再取起点S2为图
图2 部分济宁市道路网图 的最左上角(光河的节点数呈线性关系，所以时间复杂度不超过O()。搜
路和环成西路的交叉口)
，终点T2为图的最右下角(太白路和
索会合后，二叉树的深度不超过N,所以步8的时间复杂度
琵琶山路交叉口)。求解的最短路径为：正向搜索从起点沿
N)。总之整个算法的时间复杂度不超过,O(N)。不超过O(
光河路向东，到浣笔泉路路口向南；逆向搜索从终点沿太白
4 算法检验路向西到浣笔泉路路口向北直到和正向搜索在红星中路路口
表1 起点S1，终点T1的算法比较
节点会合。算法用Vsual C++6.0编制，在PII500，64MB内存
Ns：求解过程中搜索的节点数；T：求解时间，单位为秒；QL：求
的计算机上运行，表1、表2给出本文算法和Dijkstra算法的比
解的最短距离，单位为米；RL：实际最短距离，单位为米。
较，显然本文算法搜索空间小、速度快、求解时间少。
Ns
本文算法Dijkstra算法
107182
T 1.08 1.98
QL 3325 3325
RL3325
5 结论
本文给出的算法适于城市道路网的最短路径寻优，道路网络越规整，算法的适用性越强。和Dijkstra算法相比，算法不仅能得到一个最优解且搜索空间小，速度快，时间复杂度不超过O(N)。算法已经用于我们研发的自主车辆导航系统，表明算法有很高的实用价值和可靠性。
参考文献
严蔚敏，吴伟民数据结构北京：清华大学出版社1 . . ,1997
2 Fawcett J,Robinson P.Adaptive Routing for Road Traffic.IEEE Computers Graphics and Applications,2000,20(3):26-53严寒冰，刘迎春基于的城市道路网最短路径算法探讨. 计算3 . GIS机学报，，23(2)：210~215 2000
陆汝钤人工智能北京：科学出版社，4 . . 1995
表2 起点S2，终点T2的算法比较
算法已用于我们研发的自主车辆导航系统，图2是山东
NS
本文算法Dijkstra算法
141225
T 1.43 2.46
QL 4280 4280
RL4280
省济宁市道路网的一部分。矢量化的道路网的存储，主要考
虑的是车辆行驶通畅的主干路，同时为了节省存储空间，忽略了一些拥挤的小街。该图的存储共有节点253个, S设起点1为电业局(图的最左下角)，终点T1为司法局东侧红星中路路口(图的最右中侧)。求解的最短路径为：正向搜索从起点向