平行四边形限制最短路径算法及其在交通网络中的应用

doi:国家自然科学基金资助项目（60474068）；教

吉林大学学报(工学版)

平行四边形限制最短路径算法及其在交通网络中的应用

王晓丽¹，²，杨兆升¹, 吕旭涛³，赵兵选³

1.吉林大学交通学院, 长春 130022； 2.长春税务学院信息管理系，长春 130021； 3.中国科学技术大学自动化系，

收稿日期:2005-08-05 修回日期:2005-11-08 出版日期:2006-01-01 发布日期:2006-01-01
通讯作者: 王晓丽

Shortest Path Algorithm Based on Limiting Parallelogram and Its Application in Traffic Networks

Wang Xiaoli¹,², Yang Zhaosheng¹ ,Lü Xutao³, Zhao Bingxuan³

1.College of Transportation, Jilin University, Changchun 130022, China; 2. Department of Information Management, Changchun Taxation College, Changchun 130021, China;

Received:2005-08-05 Revised:2005-11-08 Online:2006-01-01 Published:2006-01-01
Contact: Wang Xiaoli

摘要/Abstract

摘要： 现有的最短路径搜索算法如Dijkstra算法或椭圆限制的Dijkstra算法等计算效率较低，有待进一步改进。作者在椭圆限制的Dijkstra算法基础上，通过对椭圆进行线性化处理和对限制用的多边形进行优选，得出一种平行四边形限制的最短路径算法，使搜索效率有了较大程度的提高，通过对各种算法的运行结果进行对比，证明了本算法的有效性和快速性。

关键词: 交通运输系统工程, GPS, 最短路径算法, 电子地图, 交通网络

Abstract: The operating efficiencies of the existing shortest path searching algorithms such as Dijkstra algorithm and Dijkstra algorithm on the limiting ellipse, etc., are low and inconvenient in practical application, so they need to be improved. On the basis of the Dijkstra algorithm on the limiting ellipse, by means of linearizing the ellipse and optimizing the limiting polygon, an optimal path algorithm based on the limiting parallelogram was proposed to improve significantly the searching efficiency. The comparison results of free searching and searching by ellipse method and parallelogram method proved the efficiency and validity of the parallelogram method.

Key words: transportation system engineering, global positioning system, shortest path algorithm, digital map, traffic network

中图分类号:

U491.13

王晓丽，，杨兆升, 吕旭涛，赵兵选. 平行四边形限制最短路径算法及其在交通网络中的应用[J]. 吉林大学学报(工学版), 2006, 36(01): 123-0127.

Wang Xiaoli,, Yang Zhaosheng ,Lü Xutao, Zhao Bingxuan. Shortest Path Algorithm Based on Limiting Parallelogram and Its Application in Traffic Networks[J]. 吉林大学学报(工学版), 2006, 36(01): 123-0127.

参考文献

相关文章 15

[1]	陈永恒,刘芳宏,曹宁博. 信控交叉口行人与提前右转机动车冲突影响因素[J]. 吉林大学学报(工学版), 2018, 48(6): 1669-1676.
[2]	常山,宋瑞,何世伟,黎浩东,殷玮川. 共享单车故障车辆回收模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1677-1684.
[3]	曲大义,杨晶茹,邴其春,王五林,周警春. 基于干线车流排队特性的相位差优化模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1685-1693.
[4]	宗芳, 齐厚成, 唐明, 吕建宇, 于萍. 基于GPS数据的日出行模式-出行目的识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1374-1379.
[5]	刘翔宇, 杨庆芳, 隗海林. 基于随机游走算法的交通诱导小区划分方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1380-1386.
[6]	钟伟, 隽志才, 孙宝凤. 不完全网络的城乡公交一体化枢纽层级选址模型[J]. 吉林大学学报(工学版), 2018, 48(5): 1387-1397.
[7]	刘兆惠, 王超, 吕文红, 管欣. 基于非线性动力学分析的车辆运行状态参数数据特征辨识[J]. 吉林大学学报(工学版), 2018, 48(5): 1405-1410.
[8]	宗芳, 路峰瑞, 唐明, 吕建宇, 吴挺. 习惯和路况对小汽车出行路径选择的影响[J]. 吉林大学学报(工学版), 2018, 48(4): 1023-1028.
[9]	栾鑫, 邓卫, 程琳, 陈新元. 特大城市居民出行方式选择行为的混合Logit模型[J]. 吉林大学学报(工学版), 2018, 48(4): 1029-1036.
[10]	陈永恒, 刘鑫山, 熊帅, 汪昆维, 谌垚, 杨少辉. 冰雪条件下快速路汇流区可变限速控制[J]. 吉林大学学报(工学版), 2018, 48(3): 677-687.
[11]	王占中, 卢月, 刘晓峰, 赵利英. 基于改进和声搜索算法的越库车辆排序[J]. 吉林大学学报(工学版), 2018, 48(3): 688-693.
[12]	李志慧, 胡永利, 赵永华, 马佳磊, 李海涛, 钟涛, 杨少辉. 基于车载的运动行人区域估计方法[J]. 吉林大学学报(工学版), 2018, 48(3): 694-703.
[13]	陈松, 李显生, 任园园. 公交车钩形转弯交叉口自适应信号控制方法[J]. 吉林大学学报(工学版), 2018, 48(2): 423-429.
[14]	苏书杰, 何露. 步行交通规划交叉路口行人瞬时动态拥塞疏散模型[J]. 吉林大学学报(工学版), 2018, 48(2): 440-447.
[15]	孟品超, 李学源, 贾洪飞, 李延忠. 基于滑动平均法的轨道交通短时客流实时预测[J]. 吉林大学学报(工学版), 2018, 48(2): 448-453.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

平行四边形限制最短路径算法及其在交通网络中的应用

Shortest Path Algorithm Based on Limiting Parallelogram and Its Application in Traffic Networks

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0