4f174a7fd39c20a

User-based Vehicle Route Guidance in Urban Networks Based on Intelligent Multi Agents Systems and the ANT-Q Algorithm

Document Type: Research Paper

Authors

1 Assistant Professor, Faculty of Engineering, University of Kurdistan, Sanandaj, Iran

2 MSc. Grad., Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran

3 Professor, Faculty of Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

Guiding vehicles to their destination under dynamic traffic conditions is an important topic in the field of Intelligent Transportation Systems (ITS). Nowadays, many complex systems can be controlled by using multi agent systems. Adaptation with the current condition is an important feature of the agents. In this research, formulation of dynamic guidance for vehicles has been investigated based on the characteristics of ITS and using the user-based approach to meet drivers’ satisfaction. As a result of time-varying flows on traffic networks, a multi agent model and the routing algorithm based on artificial intelligence techniques emphasized on a hybrid algorithm combining Ant Colony and Reinforcement Learning is proposed. The critical result of this paper is the ability of designing an algorithm for better trip planning, routing decisions in a dynamic urban transportation. Finally, the validity of the proposed algorithm is shown by implementation on a sub-network extracted from Tehran traffic map.

Keywords


- Adler, J. L. and Blue, V. J. (1998) “Toward the design of intelligent traveler information systems”, Transportation Research Part C, Vol.6, No.3, pp.157-172.

- Adler J. L. and  Blue, V. J.  (2002) “A cooperative multi-agent transportation management and route guidance system”, Transportation Research, Part C, Vol.10, No.5-6, pp.433-454.

- Cai, C. Q. and Yang, Z. S. (2007) "Study on urban traffic management based on multi-agent system", Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, pp.25-29.

- Cao, Z., Guo, H., Zhang J., Fastenrath, U. (2016) “Multi agent-based route guidance for increasing the chance of arrival on time”, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pp.3814-3820.

- Chabrol, M., Sarramia, D. and Tchernev, N.(2006) "Urban traffic systems modeling methodology", Int. J. Production Economics, Vol.99, No.1-2, pp.156-176.

- Che, K., Li, L.-L., Niu, X.-T. and Xing, S.-T. (2009) “Research of software development methodology based on self-adaptive multi-agent systems”, IEEE International Symposium on IT in Medicine & Education (ITME 2009), Vol. 1, pp. 235–240.

- Chen, B. and Cheng, H. H. (2010) “A Review of the applications of agent technology in traffic and transportation systems”, IEEE Transactions on Intelligent Transportation Systems, Vol.11, No.2, pp. 485-497.

- Claes, R., Holvoet, T. and Weyns, D. (2011) “A decentralized approach for anticipatory vehicle routing using delegate multi agent systems”, IEEE Transactions on Intelligent Transportation Systems, 10.1109/TITS.2011.2105867.

- Colorni A., Dorigo  M. and Maniezzo V. (1991) “Distributed optimization by ant colonies”, Proceedings of ECAL91 - European Conference on Artificial Life, Paris, France, F. Varela and P. Bourgine   (Eds.), Elsevier Publishing, pp.134–142.

- Deflorio, F. P. (2003) “Evaluation of a reactive dynamic route guidance strategy”, Transportation Research Part C, Vol.11, No.5, pp.375-388.

- Dong, W. (2011) “An overview of in-vehicle route guidance”, Proceedings of the Australasian Transport Research Forum, Adelaide, Australia.

- Fu, L. (2001) “Adaptive routing algorithm for in-vehicle route guidance systems with real-time information”,  Transportation Research Part B: Methodological, Vol. 35, No. 8, pp. 749-765.

- Fu, L P., Sun, D. and Rillet, L. R. (2006) “Heuristic shortest path algorithms for transportation applications: State of the art”, Computers and Operations Research, Vol.33, No.11, pp.3324-3343.

- Gambardella L. and M. Dorigo. (1995) “Ant-Q: A reinforcement learning approach to the traveling salesman problem”, Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, pp.252–260.

- Gu, J., Lin, E., Liu, Y. and Zhang, N. (2010) “Study on improved ant colony algorithm in dynamic multi-paths route guidance system”, Applied Mechanics and Materials, Vol. 20-23, pp.243-248.

- Jiong, S. and Zhao, J. (2011) “Q-learning based multi-intersection traffic signal control model”, International Conference on System Science, Engineering Design and Manufacturing Informatization, Guiyang, China, pp. 280-283.

- Karimi,  A., Hegyi, A. De Schutter, B. Hellendoorn, J. and  Middelham, F.  (2004) "Integrated model predictive control of dynamic route guidance information systems and ramp metering," Intelligent Transportation Systems, pp. 491- 496.

- Lee, D. C (2006) “Proof of a modified Dijkstra's algorithm for computing shortest bundle delay in networks with deterministically time-varying links”, IEEE Communications Letters, Vol.10, No.10, pp.734-736.

- Levinson, D. (2003) “The value of advanced traveler information systems for route choice”, Transportation Research Part C, Vol.11, No.1, pp.75-87.

- Marti, I., Tomas, V.R., Saez, A. and Martinez, J. J. (2009) “A rule-based multi-agent system for road traffic management”, International Joint Conference on Web Intelligence and Intelligent Agent Technology, Vol. 3.

- Masoomi, Z., Sadeghi Nearki, A. and  Mesgari, A. (2011) “Designing and using a multi-objective route planning algorithm in Intelligent Transportation Systems” (In Persian), Journal of Transportation Research, Vol.8, No.1, pp.47-62.

- Nadi, S. and Delavar,  M. R.  (2011) “Multi-criteria, personalized route planning using quantifier-guided ordered weighted averaging operators”, International Journal of Applied Earth Observation and Geoinformation, Vol.13, pp.322–335.

- Nadi, S. and  Delavar, M. R. (2010) “Location-based services for in-vehicle route guidance with real time traffic information”, The 12th World Conference on Transport Research.

- Ng, K. M., Ibne Reaz, M. B., Mohd Ali, M.A. and Chang, T. G. (2013) “A brief survey on advances of control and intelligent systems methods for traffic-responsive control of  urban networks”, Technical Gazette, Vol. 20, No.3, pp. 555-562.

- Nakhai Kamalabadi I. and  Eydi, A.  (2009) “Vehicle routing in dynamic route guidance system”( In Persian), Journal of Transportation Research, Vol.6, No.3, pp.269-286.

- Pahlavani P. and Delavar, M. (2014) “Multi-criteria route planning based on a driver’s preferences in multi-criteria route selection”, Transportation Research Part C 40, pp.14–35.

- Papageorgiou, M., Diakaki, C., Dinopoulou, V. , Kotsialos, A. and Wang, Y.(2003) “Review of road traffic control strategies”,  Proceedings of the IEEE, Vol. 91, No. 12, pp. 2043-2067.

- Pahlavani P., Samadzadegan, F. and Delavar, M. (2006) “A GIS-Based Approach for Urban Multi-criteria Quasi Optimized Route Guidance by Considering Unspecified Site Satisfaction”, Geographic Information Science , Lecture Notes in Computer Science Volume 4197, pp 287-303.

- Park D., Laurence, R. and  Choi,  C.  (2007a) “A class of multi criteria shortest path problems for real-time in-vehicle routing, Canadian journal of civil engineering, Vol.34, No.9, p.1096.

- Park, K., Bell, M. Kaparias, I.  and Bogenberger,  K. (2007b) “Learning user preferences of route choice behaviour for adaptive route guidance”, Special Issue: Selected papers from the 13th World Congress on Intelligent Transport Systems and Services, IET Intell. Transp. Syst., Vol.1, No.2, pp. 159–166.

- Sadek, A. and Chowdhury, M. A. (2003) “Fundamentals of intelligent transportation systems planning”, Boston, Artech House.

Sadeghi Niaraki, A. and Kim, K. (2009) “Ontology based personalized route planning system using a multi-criteria decision making approach”, Expert Syst. Appl., Vol.36, pp.2250–2259.

- Schmitt, E. J. and Jula, H. (2006) “Vehicle route guidance systems: classification and comparison”, Proceedings of the IEEE Intelligent Transportation Systems conference, Toronto, Canada. pp. 242 –247.

- Shi, A., Na, C. and Chun-bin, H. (2008) “Simulation and analysis of route guidance strategy based on a multi-agent game approach”, 15th International conference on Management science & Engineering, Long Beach, USA, pp.140-146.

- Vandebon, U. and Upadhyay, P. K. (1997) “Simulation modeling of route guidance concept”, Transportation Research Record,  1573, pp.44-51.

- Wu, J. J.,  Sun, H. J. and Gao, Z. Y. (2008) “Dynamic urban traffic flow behavior on scale-free networks”, Physica A: Statistical Mechanics and its Applications 387, pp.653-660. 

- Wunderlich, K.E., Kaufman, D. E. and  Smith,   R. L.  (2000) "Link travel time prediction for decentralized route guidance architectures," Intelligent Transportation Systems, Vol. 1, No. 1, pp. 4-14.

- Yamashita, T., Izumi, K. and Kurumatani, K. (2004) "Car navigation with route information sharing for improvement of traffic efficiency," Intelligent Transportation Systems, pp. 465- 470.

- Yoshikawa, M. and Otani, K. (2010) “Ant colony optimization routing algorithm with tabu search”, Proceeding of International Multi conference of Engineers and Computer Scientists Hong Kong: IMECS, pp. 2104-2107.

- Zolfpour, M., Selamat, A., MohdHashim, S. and Selamat, M. (2011) “Route guidance system based on self-adaptive multiagent algorithm”, Computational Collective Intelligence. Technologies and Applications, Lecture Notes in Computer Science Volume 6923, pp. 90-99.