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

Previous Articles     Next Articles

Dynamic route optimization algorithm based on hybrid in ITS

ZHAO Hong-wei1,2, LIU Yu-qi1,2, DONG Li-yan1,2, WANG Yu1,3, LIU Pei1,2   

  1. 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: 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

CLC Number: 

  • TP399
[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.
[1] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[12] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[13] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[14] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
[15] ZHAO Hong-wei, LIU Yu-qi, TE Ri-gen, CHEN Chang-zheng, ZANG Xue-bai. New compression algorithms based on finite sequence [J]. 吉林大学学报(工学版), 2018, 48(3): 882-886.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] ZHU Jian-feng, LIN Yi, CHEN Xiao-kai, SHI Guo-biao. Structural topology optimization based design of automotive transmission housing structure[J]. 吉林大学学报(工学版), 2013, 43(03): 584 -589 .
[5] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[6] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[7] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[8] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[9] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[10] XIAO Yun, LEI Jun-qing, ZHANG Kun, LI Zhong-san. Fatigue stiffness degradation of prestressed concrete beam under multilevel amplitude cycle loading[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .