Dynamic Multi-Objective Navigation in Urban Transportation Network Using Ant Colony Optimization

Document Type : Research Paper

Authors

1 GIS Department, Faculty of Geodesy and Geomatics Engineering, K. N. Toosi University of Technology, Tehran, Iran

2 GIS Department, Faculty of Geodesy and Geomatics Engineering, GIS Excellence Center, K. N. Toosi University of Technology, Tehran, Iran

Abstract

Intelligent Transportation System (ITS) is one of the most important urban systems that its functionality affects other urban systems directly and indirectly. In developing societies, increasing the transportation system efficiency is an important concern, because variety of problems such as heavy traffic condition, rise of the accident rate and the reduced performance happen with the rise of population. Route finding and navigation are two effective tools to reduce the pressure on the transportation system. Better navigation methods can reduce the traffic concentration in specific areas. In most of the cases, transportation networks are changing through time and they don’t have a static status. On the other hand, different users consider different objectives when they want to move through the transportation network. So, this paper proposed a novel method to solve dynamic navigation and route finding problem while considering different objectives. This new method is based on multi-objective Ant Colony Optimization (ACO). Experiments are designed in a simulated network and results are compared with static navigation in single-objective and multi-objective mode. Results indicated that the proposed method is performing very accurate in finding the optimal paths. Also the proposed method for dynamic navigation is performing better than the static navigation. It has improved the trip duration of the 80% of the altered routes and decreased the trip duration of some experiments up to 50%. These results indicate that the proposed method has the ability to solve multi-objective dynamic navigation in urban transportation systems in the presence of high rate traffic information.

Keywords


- Abolhoseini, S. and Sadeghi-Niaraki, A. (2016) “Survey on certain and heuristic route finding algorithms in GIS”, GEJ, Vol. 7, No. 4,  pp. 49-65.
- Boroujerdian, A. M., Fetanat, M. and Abolhasannejad, V. (2015) “Identification of high crash road segment using genetic algorithm”, International Journal of Transportation Engineering, Vol. 3, No. 2,  pp. 93-107.
- Chakhar, S. and Martel, J.-M. (2003) “Enhancing geographical information systems capabilities with multi-criteria evaluation functions”, Journal of geographical information and decision analysis, Vol. 7, No. 2, pp. 47-71.
- Claes, R. and Tom, H. (2011) “Ant colony optimization applied to route planning using link travel time predictions”, IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW).
- Coello Coello, C. A., Lamount, G. and Veldhuizen, D. A. (2002) “Evolutionary algorithms for solving multi-objective problems”, New York: Springer.
- Deneubourg, J. L., Aron, S., Goss, S. and Pasteels, J. M. (1990) “The self-organizing exploratory pattern of the argentine ant”. Journal of insect behavior, Vol. 3, No. 2, pp. 159-168.
- Di Caro, G. (2004) “Ant colony optimization and its application to adaptive routing in telecommunication networks”, PhD Dissertation, Faculté des Sciences Appliquées, Université Libre de Bruxelles, Brussels, Belgium.
- Dijkstra, E. W. (1959) “A note on two problems in connection with graphs”, Numerische Mathematik, Vol. 1, No. 1, pp. 269-271.
- Ding, J., Wang , C., Meng , F. and Wu , T. (2010) “Real-time vehicle route guidance using vehicle-to-vehicle communication”, IET Communications, Vol. 4, No. 7, pp. 870-883.
- Dorigo, M. and Birattari, M. (2010) “Ant colony optimization. In: Encyclopedia of machine learning”, Berlin, Heidelberg: Springer Science and Business Media, pp. 36-39.
- Dorigo, M. (1992) “Optimization learning and natural algorithms (in Italian)”, Ph.D. Dissertation, Dipartimento di Electronica Politecnico di Milano, Italy.
- Dorigo, M., Di Caro, G. and Gambardella, L. (1999) “Ant algorithms for discrete optimization”, Artificial Life, Vol. 5, No. 2, pp. 137-172.
- Eydi, A., Panahi, S. and Nakhai Kamalabadi, I. (2017) “User-based vehicle route guidance in urban networks based on intelligent multi agents systems and the ANT-Q Algorithm”. International Journal of Transportation Engineering, Vol. 3, No. 4, pp. 147-161.
- Fu, L. (2001) “An 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.
- Gao, S. and Chabini, I. (2006) “Optimal routing policy problems in stochastic time dependent networks”, Transportation Research Part B: Methodological, Vol. 40, No. 2, pp. 93-122.
- Jabbarpour, M. R., Jalooli, A., Shaghaghi, E., Noor, R. M., Rothkrantz, L., Khokhar, R. H. and Anuar, N. B. (2014) “Ant-based vehicle congestion avoidance system using vehicular networks”, Engineering Applications of Artificial Intelligence, Vol. 36, pp. 303-319.
- Jozefoweiz , N., Semet, F. and Talbi, E. (2008) “Multi-objective vehicle routing problem”, European Journal of Operational Research, Vol. 189, No. 2, pp. 293-309.
- LaValle, S. M. (2006) “Planning algorithms”, Lauren Cowles ed. Cambridge: Cambridge University Press.
- Lin, J., Yu, W., Yang, X., Yang, Q., Fu, X. and Zhao, W. (2017) “A real-time en-route route guidance decision scheme for transportation-based Cyberphysical Systems”, IEEE Transactions on Vehicular Technology, Vol. 66, No. 3, pp. 2551-2566.
- Lopez-Ibanez, Mm. (2004) “Multi-Objective Ant Colony Optimization”, Diploma Thesis: Technische Universität Darmstadt.
- Magzhan, K. and Mat Jani, H. (2013) “A review and evaluations of shortest path algorithms”, International Journal Of Scientific and Technology Research, Vol. 2, No. 6, pp. 99-104.
- Masoomi, Z., Sadeghi-Niaraki, A. and Mesgari, M. S. (2011) “Designing and using a multi-objective route planning algorithm in intelligent transportation system”, Transportation Research Journal (TRJ), Vol. 8, No. 1, pp. 47-62.
- Mooney, P. and Winstanley, A. (2006) “An evolutionary algorithm for multicriteria path optimization problems”, International Journal of Geographical Information Science, Vol. 20, No. 4, pp. 401-423.
- Nadi, S. and Delavar, M. R. (2010) “Location-based service for In-vehicle route guidance with real time traffic information”, Lisboa, Portugal, the 12th World Conference on Transport Research.
- Pahlavani, P., Delavar, M. R. and Frank, A. U. (2012) “Using a modified invasive weed optimization algorithm for personalized urban multi-criteria path optimization problem”. International Journal of Applied Earth Observation and Geoinformation, Vol. 18, pp. 313-328.
- Pahlavani, P., Samadzadegan, F. and Delavar, M. R. (2006) “A GIS-Based approach for urban multi-criteria quasi optimized route guidance by considering unspecified site satisfaction”, Berlin Heidelberg, International Conference on Geographic Information Science.
- Ueda, N. Naya, F., Shimizu, H., Iwata, T., Okawa, M. and Sawada, H. (2015) “Real-time and proactive navigation via spatio-temporal prediction”, ACM, Adjunct Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2015 ACM International Symposium on Wearable Computers.
- Wang, M., Shan, H., Lu, R., Zhang, R., Shen, X. and Bai, F. (2015) “Real-time path planning based on Hybrid-VANET-enhanced transportation system”, IEEE Transactions on Vehicular Technology, Vol. 64, No. 5, pp. 1664-1678.
- Zakaria, S., Rey, G., Mohamed, E., Lavirotte, S., Abdelaziz, E. F. and Tigli, J.Y. (2015) “Smart geographic object: Toward a new understanding of GIS Technology in ubiquitous computing”, JCSI International Journal of Computer Science, Vol. 12, No, 2.
- Zhang, W., Zhang, Z. and Xu, J. (2006) “Dynamic route guidance using neurodynamic programming”, Sixth International Conference on Intelligent Systems Design and Applications, Vol. 2, pp. 1177-1181. IEEE.
- Zitzler, E. and Thiele, L. (1998) “Multi objective optimization using evolutionary algorithms- A comparative case study”, Springer Berlin Heidelberg, International Conference on Parallel Problem Solving from Nature.