基于交通约束的高效路径规划算法

交通运输系统工程与信息 ›› 2008, Vol. 8 ›› Issue (2): 64-68 .

基于交通约束的高效路径规划算法

杨东凯^*1,2;陈志宇¹ ;吴今培¹ ;徐爱功²

1北京航空航天大学电子信息工程学院北京 100083 ; 2 辽宁工程技术大学地理空间信息技术及应用重点实验室,辽宁阜新 123000

收稿日期:2007-10-31 修回日期:2008-01-21 出版日期:2008-04-25 发布日期:2008-04-25
通讯作者: 杨东凯
作者简介:杨东凯（1972-），男，山东人，副教授.
基金资助:
辽宁工程技术大学地理空间信息技术及应用重点实验室开放基金（2004007）.

High Efficient Route Planning Algorithm Based on Traffic Constraints

Yang Dong-kai ^1,2 ;Chen Zhi-yu ¹ ;Wu Jin-pei ¹ ;Xu Ai-gong ²

1 School of Electronic and Information Engineering, Beihang University, Beijing 100083, China;
2 Geomatics and applications laboratory, LiaoNing Technological University,Fuxin123000, LiaoningChina

Received:2007-10-31 Revised:2008-01-21 Online:2008-04-25 Published:2008-04-25
Contact: Yang Dong-kai

摘要/Abstract

摘要： 分析了路径规划问题及其在交通约束条件下的特点。从算法改进和模型改进两方面对路径规划算法进行了研究，在详细分析Dijkstra算法步骤和对偶法的基础上，给出了交通约束的数学模型及道路网络的相关定理。基于传统Dijkstra算法，对搜索过程中的节点和边的标记方式和规则进行了改进，提出了一种在交通约束条件下的高效路径规划算法。该算法通过减少搜索节点和标记边的次数而减少搜索过程中的运算量。仿真结果表明，该算法对偶法1/3～1/4的运算量。

关键词: 路径规划, 交通约束, Dijkstra算法

Abstract: This paper analyzes the characteristics of route planning with traffic constraints. It explores the route planning algorithm from both the algorithm modifications and modeling modifications. Meanwhile, based on the elaborate analysis of Dijkstra algorithm steps and dual method, this paper discusses the mathematic model with traffic constraints and the relative theorem on road network. In addition, the traditional Dijkstra algorithm is modified for the node searching and link marking rule during the planning process. Furthermore, a high efficient algorithm is proposed with consideration of traffic constraints. It decreases the computation time through decreasing the searching nodes and link marking times. The simulation result indicates that the computation complexity the presented algorithm is 1/3-1/4 of the dual method.

Key words: route-planning, traffic constraints, Dijkstra algorithm

中图分类号:

U491

杨东凯,陈志宇,吴今培,徐爱功. 基于交通约束的高效路径规划算法[J]. 交通运输系统工程与信息, 2008, 8(2): 64-68 .

Yang Dong-kai,Chen Zhi-yu,Wu Jin-pei,Xu Ai-gong . High Efficient Route Planning Algorithm Based on Traffic Constraints[J]. Journal of Transportation Systems Engineering and Information Technology, 2008, 8(2): 64-68 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17642.shtml

http://www.tseit.org.cn/CN/Y2008/V8/I2/64

参考文献

[1] 陈红英,杨宜民,毛革非. 交通禁则下自主导航节点结构设计及Dijkstra算法的改进[J]. 计算机工程与应用,2005, 41(3): 208-211. [CHEN Hong-ying, YANG Yi-min, MAO Ge-fei. The node structure design of auto-navigation system based on traffic confine rule and the improvement of dijkstra algorithm[J]. Computer Engineering and Application, 2005, 41(3):208-211.]

[2] 段莉琼,雷大伟.车辆自导航系统中加入道路转向限制的最短路径算法[J].海洋测绘,2003,23(5): 12-15.[DUAN Li-qiong, LEI Da-wei.The algorithm of the shortest path for turning restriction in the vehicle navigation system[J].Hydrographic Surveying and Charting,2003,23(5):12-15.]

[3] 储理才,郭英雄.含有禁止路线网络中的最短路问题[J].集美大学学报（自然科学版），2002,7(1):86-89. [CHU Li-cai, GUO Ying-xiong. The shortest path problem in a network with forbidden pathes in it[J]. Journal of Jimei University (Natural Science), 2002, 7(1):86-89.]

[4] 王丰元,潘福全等. 基于交通限制的路网最优路径算法[J].2005,5(1):92-95. [WANG Feng-yuan, PA Fu-quan, et al. Optimal path algorithm of road network with traffic restriction[J], Journal of Traffic and Transportation Engineering，2005, 5(1):92-95.]

[5] 李引珍,何瑞春,郭耀煌.结点有约束的交通网络最短路径模型[J]. 运筹与管理, 2005,14(4):40-43. [LI Yin-zhen, HE Rui-chun , GUO Yao-huang. Modeling for shortest path in traffic network with node limits[J]. Operations Research and Management Science, 2005,14(4):40-43.]

[6] Ki-Sung Seo, Gyoo-Seok Choi. The genetic algorithm based route finding method for alternative paths[C]//. IEEE International Conference on. Systems, Man, and Cybernetics, 1998(3):2448 - 2453 .

[7] WANG Qian-yu，XU Lun-hui，QIU Jian-dong. Research and realization of the optimal path algorithm with complex traffic regulations in GIS[C]//. Proceedings of the IEEE International Conference on Automation and Logistics. 2007:516-520.

[1]	李建国, 杨波, 马尚鹏. 基于顾客到达拟合的立体车库搬运器待命位设计策略[J]. 交通运输系统工程与信息, 2021, 21(6): 217-225.
[2]	胡臣杰, 张军. 基于时空等待特征系数的大型活动出行规划研究[J]. 交通运输系统工程与信息, 2021, 21(4): 148-155.
[3]	楚金华, 李俊鹤, 王春娟, 陈超. 排放控制区下集装箱班轮航线路径规划与航速调度集成决策[J]. 交通运输系统工程与信息, 2021, 21(4): 230-238.
[4]	张洪海，李翰，刘皞，许卫卫，邹依原. 城市区域物流无人机路径规划[J]. 交通运输系统工程与信息, 2020, 20(6): 22-29.
[5]	赵琦，曾烨，张立立，王力. 指引路径规划模型的建模与仿真验证[J]. 交通运输系统工程与信息, 2020, 20(6): 184-190.
[6]	马庆禄，冯敏，乔娅. 基于自动寻迹的港湾式公交站台停靠路径研究[J]. 交通运输系统工程与信息, 2019, 19(2): 108-115.
[7]	唐立，郝鹏，张学军. 基于改进蚁群算法的山区无人机路径规划方法[J]. 交通运输系统工程与信息, 2019, 19(1): 158-164.
[8]	安基文，李晓丽，范熙伟，聂高众. 面向地震应急的救援路径规划模型[J]. 交通运输系统工程与信息, 2019, 19(1): 172-178.
[9]	郭保青，郝树运，朱力强，余祖俊. 基于改进蚁群算法的多AGV泊车路径规划[J]. 交通运输系统工程与信息, 2018, 18(6): 55-62.
[10]	徐广宁，王印海，曾自强. 城市路网动态转向建模与优先选择研究[J]. 交通运输系统工程与信息, 2017, 17(4): 132-137.
[11]	宋青，李晓磊，李猛. 基于OpenStreetMap 的城市自行车网建模与多判据路径规划[J]. 交通运输系统工程与信息, 2017, 17(3): 143-149.
[12]	彭理群,吴超仲,黄珍，楚文慧，贺宜. 考虑驾驶意图与动态环境的汽车避碰路径规划[J]. 交通运输系统工程与信息, 2016, 16(6): 81-87.
[13]	刘莎莎，姚恩建，张永生. 轨道交通乘客个性化出行路径规划算法[J]. 交通运输系统工程与信息, 2014, 14(5): 100-104.
[14]	李季涛，王志远，王宇，付佳. 铁路客运站始发列车检票时间算法研究[J]. 交通运输系统工程与信息, 2014, 14(5): 133-139.
[15]	王飞，王红勇. 基于Maklink 图和遗传算法的改航路径规划方法研究[J]. 交通运输系统工程与信息, 2014, 14(5): 154-160.