改进蚁群算法的多约束质量最优路径选择

doi:10.3969/j.issn.1001-2400.2016.03.032

Abstract

Abstract:

As the traffic congestion becomes more and more serious, the public evaluation standard for the road quality during driving changes greatly. How to avoid congestion to find the best way to travel has become an important scientific issue and social issue urgent to address in the context of building a smart city. Thus this paper first defines the novel concept of optimal path with multi-constraints and models it. Then, in order to solve the proposed model more efficiently, we improve the state transition rules of the heuristic function and pheromone update operator based on the classical ant colony algorithm by increasing the path optimization algorithm's awareness of real-time path quality information, such as traffic conditions, resulting in the strong dynamic adjustment ability of our proposed path optimization algorithm to path information. Simulation results show that our proposed ant colony algorithm can find the optimal path with multi-constraints more accurately and more quickly than other ant colony algorithms.

Key words: multi-constraint path routing, optimal quality path, ant colony algorithm, pheromone update, heuristic function

CLC Number:

TP751

MA Ronggui;CUI Hua;XUE Shijiao;GUO Lu;YUAN Chao. Improved ant colony algorithm for the optimal-quality-path routing problem with multi-constraints[J].Journal of Xidian University, 2016, 43(3): 185-189.

References

［1］ YAO E J, LANG Z F, YANG Y. Vehicle Routing Problem Solution Considering Minimising Fuel Consumption［J］. IEEE Transactions on Intelligent Transportation Systems, 2015, 9(5): 523-529.
［2］ LIN X, LO H K. Adaptive Vehicle Navigation with EN Route Stochastic Traffic Information［J］. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(5): 1900-1912.
［3］ HAMZHEEI M, FARAHANI R Z, RASHIDI-BAJGAN H. An Ant Colony-based Algorithm for Finding the Shortest Bidirectional Path for Automated Guided Vehicles in a Block Layout［J］. The International Journal of Advanced Manufacturing Technology, 2013, 64(4): 399-409.
［4］ HUANG M, DING P. An Improved Ant Colony Algorithm and Its Application in Vehicle Routing Problem［J］. Mathematical Problems in Engineering, 2013, 2013: 1-9.
［5］ SCHYNS M. An Ant Colony System for Responsive Dynamic Vehicle Routing［J］. European Journal of Operational Research, 2015, 245(3): 704-718.
［6］ LISSOVOI A, WITT C. Runtime Analysis of Ant Colony Optimization on Dynamic Shortest Path Problems［C］//Proceedings of the 2013 Genetic and Evolutionary Computation Conference, Association for Computing Machinery. New York: ACM, 2013: 1605-1612.
［7］ REED M, YIANNAKOU A, EVERING R. An Ant Colony Algorithm for the Multi-compartment Vehicle Routing Problem［J］. Applied Soft Computing, 2014, 15: 169-176.
［8］ MAVROVOUNIOTIS M, YANG S X. Ant Algorithms with Immigrants Schemes for the Dynamic Vehicle Routing Problem［J］. Information Sciences, 2015, 294: 456-477.
［9］ NIE Y, WU X. Shortest Path Problem Considering on-time Arrival Probability［J］. Transportation Research Part B: Methodological, 2009, 43(6): 597-613.
［10］ MAHI M, BAYKAN O K, KODAZ H. A New Hybrid Method Based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt Algorithms for Traveling Salesman Problem［J］. Applied Soft Computing, 2015, 30: 484-390.

[1]	YANG Siyan;CAO Wencan;LI Shiping. Second-order graph model ant and colony optimization based image matching [J]. Journal of Xidian University, 2017, 44(1): 159-164.
[2]	LIU Daohua;NI Yongjun;SUN Fang;ZHANG Fei. Optimization method for multimodal functions based on chaotic ant colony algorithms [J]. J4, 2015, 42(3): 141-147.
[3]	ZHANG Jun-ying1;2;AO Lei1;JIA Jiang-tao1;GAO Lin1. An improvement of the ant colony algorithm for solving TSP problems [J]. J4, 2005, 32(5): 681-685.

Improved ant colony algorithm for the optimal-quality-path routing problem with multi-constraints

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Metrics

Comments

Recommended 10