智能交通混合动态路径优化算法

doi:10.13229/j.cnki.jdxbgxb20170132

吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (4): 1214-1223.doi: 10.13229/j.cnki.jdxbgxb20170132

智能交通混合动态路径优化算法

赵宏伟^1,2, 刘宇琦^1,2, 董立岩^1,2, 王玉^1,3, 刘陪^1,2

1.吉林大学计算机科学与技术学院,长春130012;
2.吉林大学符号计算与知识工程教育部重点实验室,长春130012;
3.吉林大学应用技术学院,长春130012

收稿日期:2017-03-02 出版日期:2018-07-01 发布日期:2018-07-01
通讯作者: 董立岩(1966-),男,教授,博士.研究方向:数据库与智能网络.E-mail:dongly@jlu.edu.cn
作者简介:赵宏伟(1962-),男,教授,博士生导师.研究方向:智能信息系统.E-mail:zhaohw@jlu.edu.cn
基金资助:
国家自然科学基金青年项目(61101155); 吉林省发展和改革委员会产业创新专项项目(2016C035); 应用光学国家重点实验室项目; 吉林省优秀青年人才基金项目(20180520020JH).

Dynamic route optimization algorithm based on hybrid in ITS

ZHAO Hong-wei^1,2, LIU Yu-qi^1,2, DONG Li-yan^1,2, WANG Yu^1,3, LIU Pei^1,2

1.College of Computer Science and Technology, Jilin University, Changchun 130012,China;
2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;
3.Applied Technology College,Jilin University,Changchun 130012, China

Received:2017-03-02 Online:2018-07-01 Published:2018-07-01

摘要/Abstract

摘要： 针对实时环境下交通信息实时、动态的特性,提出了实时环境下基于混合的动态路径优化算法。该算法在广义自适应A^*算法的基础上,结合剪枝算法,同时引入了粒子群算法局部最优及全局最优智能存储、模糊时间窗等优化策略。剪枝算法以当前局部最优为阈值,从而能够有效控制阈值的大小;模糊时间窗约束算法优化时间以及控制仿真时间,从而使算法更好地适应实时环境。实验数据采用纽约地图数据,并在仿真实验环境下,分别验证了优化策略的有效性,同时,将优化算法与A^*算法进行了对比实验。实验证明:优化策略在动态路径优化算法中是有效且合理的,可适应于动态路径诱导系统。

关键词: 计算机应用, 智能交通系统, 动态路径诱导系统, 路径优化算法, 广义自适应A^*, 算法, 剪枝算法

Abstract: In real-time environment, the traffic information is dynamic. This paper proposes a hybrid dynamic path optimization algorithm in real-time environment, which is based on A^* algorithm and combined with pruning algorithm. This paper also puts forward the optimization strategy by introducing the local optimal and global optimal intelligent storage of particle swarm optimization and fuzzy time window into the hybrid dynamic path optimization algorithm. The pruning threshold based on the local optimum is an effective way to control the size of the threshold. The fuzzy time window is applied to algorithm optimization time constraints and the control of the simulation time so that the algorithm can better adapt to the real-time environment. In order to verify the optimized strategy, simulation with the hybrid dynamic path optimization algorithm is conducted in which data is based on the New York map. Simulation results verify the effectiveness of the optimization strategy. Also the performance of the proposed algorithm is compared with the A^* algorithm, which demonstrate that the optimization strategy has certain adaptability and can be applied to Dynamic Route Guidance System (DRGS).

Key words: computer application, intelligent transportation system, dynamic route guidance system, route optimization algorithm, generalized adaptive A^* algorithm, pruning algorithm

中图分类号:

TP399

赵宏伟, 刘宇琦, 董立岩, 王玉, 刘陪. 智能交通混合动态路径优化算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.

ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS[J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.

参考文献

[1] Liu M F, Xiong S W, Li B X.Dynamic route guidance strategy in a two-route pedestrian-vehicle mixed traffic flow system[J]. International Journal of Modern Physics C, 2016, 27(9):1650099.
[2] Kim G, Ong Y S, Chen K H, et al.City vehicle routing problem (city VRP): a review[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4):1654-1666.
[3] Lin J, Yu W, Yang X, et al.A real-time en-route route guidance decision scheme for transportation-based cyberphysical systems[J]. IEEE Transactions on Vehicular Technology, 2017, 66(3):2551-2566.
[4] Wahle J, Annen O, Schuster C, et al.A dynamic route guidance system based on real traffic data[J]. European Journal of Operational Research, 2001, 131(2):302-308.
[5] Wei M J, Meng Y.Research on the optimal route choice based on improved Dijkstra[C]∥Advanced Research and Technology in Industry Applications, IEEE, 2014:303-306.
[6] Fu L, Sun D, Rilett L R.Heuristic shortest path algorithms for transportation applications: state of the art[J]. Computers & Operations Research, 2006, 33(11):3324-3343.
[7] Rivera N, Baier J A, Hernández C.Incorporating weights into real-time heuristic search[J]. Artificial Intelligence, 2015, 225:1-23.
[8] 李雄飞, 张海龙, 刘兆军,等. 用启发式算法求解最短路径问题[J]. 吉林大学学报:工学版, 2011, 41(1):182-187.
Li Xiong-fei, Zhang Hai-long, Liu Zhao-jun,et al.Problem for shortest path problem based on heuristic algorithm[J].Journal of Jilin University(Engineering and Technology Edition),2011, 41(1):182-187.
[9] Sun X X, Koenig S, Yeoh W.Generalized adaptive A*[C]∥International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril,Portugal, 2008:469-476.
[10] Hernández C, Asín R, Baier J A.Reusing previously found a* paths for fast goal-directed navigation in dynamic terrain[C]∥Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, Texas, USA, 2015:1158-1164.
[11] Desrochers M, Soumis F.A reoptimization algorithm for the shortest path problem with time windows[J]. European Journal of Operational Research, 1988, 35(2):242-254.
[12] Wen L, Eglese R.Minimum cost VRP with time-dependent speed data and congestion charge[J]. Computers & Operations Research, 2015, 56:41-50.
[13] 温涛, 李迎秋, 盛国军,等. 不确定信息下基于改进粒子群算法的Web服务选择[J]. 吉林大学学报:工学版, 2014, 44(1):129-136.
Wen Tao, Li Ying-qiu, Sheng Guo-jun, et al.Improved PSO-based Web service selection under uncertain information[J]. Journal of Jilin University(Engineering and Technology Edition), 2014, 44(1):129-136.
[14] 沈林成, 霍霄华, 牛轶峰. 离散粒子群优化算法研究现状综述[J]. 系统工程与电子技术, 2008, 30(10):1986-1990.
Shen Lin-cheng,Huo Xiao-hua,Niu Yi-feng.Survey of discrete particle swarm optimization algorithm[J].Systems Engineering and Electronics, 2008, 30(10):1986-1990.
[15] Goksal F P, Karaoglan I, Altiparmak F.A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery[J]. Computers & Industrial Engineering, 2013, 65(1):39-53.
[16] 陈新. 城市交通网络布局与优化策略研究[D]. 武汉:华中科技大学土木工程与力学学院, 2005.
Chen Xin.The strategy of optimization and planning for urban traffic network[D]. Wuhan: College of Civil Engineering & Mechanics, Huazhong University of Science and Technology,2005.

相关文章 15

[1]	刘富,宗宇轩,康冰,张益萌,林彩霞,赵宏伟. 基于优化纹理特征的手背静脉识别系统[J]. 吉林大学学报(工学版), 2018, 48(6): 1844-1850.
[2]	王利民,刘洋,孙铭会,李美慧. 基于Markov blanket的无约束型K阶贝叶斯集成分类模型[J]. 吉林大学学报(工学版), 2018, 48(6): 1851-1858.
[3]	金顺福,王宝帅,郝闪闪,贾晓光,霍占强. 基于备用虚拟机同步休眠的云数据中心节能策略及性能[J]. 吉林大学学报(工学版), 2018, 48(6): 1859-1866.
[4]	赵东,孙明玉,朱金龙,于繁华,刘光洁,陈慧灵. 结合粒子群和单纯形的改进飞蛾优化算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1867-1872.
[5]	刘恩泽,吴文福. 基于机器视觉的农作物表面多特征决策融合病变判断算法[J]. 吉林大学学报(工学版), 2018, 48(6): 1873-1878.
[6]	欧阳丹彤, 范琪. 子句级别语境感知的开放信息抽取方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1563-1570.
[7]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[8]	车翔玖, 王利, 郭晓新. 基于多尺度特征融合的边界检测算法[J]. 吉林大学学报(工学版), 2018, 48(5): 1621-1628.
[9]	桂春, 黄旺星. 基于改进的标签传播算法的网络聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1600-1605.
[10]	刘元宁, 刘帅, 朱晓冬, 陈一浩, 郑少阁, 沈椿壮. 基于高斯拉普拉斯算子与自适应优化伽柏滤波的虹膜识别[J]. 吉林大学学报(工学版), 2018, 48(5): 1606-1613.
[11]	曹洁, 苏哲, 李晓旭. 基于Corr-LDA模型的图像标注方法[J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[12]	黄辉, 冯西安, 魏燕, 许驰, 陈慧灵. 基于增强核极限学习机的专业选择智能系统[J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13]	傅文博, 张杰, 陈永乐. 物联网环境下抵抗路由欺骗攻击的网络拓扑发现算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14]	侯永宏, 王利伟, 邢家明. 基于HTTP的动态自适应流媒体传输算法[J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
[15]	杨东升, 张展, 廉梦佳, 王丽娜. 位图局部敏感哈希的匹配二进制特征搜索算法[J]. 吉林大学学报(工学版), 2018, 48(3): 893-902.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

智能交通混合动态路径优化算法

Dynamic route optimization algorithm based on hybrid in ITS

RICH HTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10