Analysis and evaluation of metaheuristic, heuristic, and deterministic methods in providing an optimal path for small, medium, and large networks
Document Type : Original Article
Authors
1 Assistant Professor, Faculty of Civil, Water and Environmental Engineering, Shahid Beheshti University, Tehran, Iran.
2 M.Sc., Graduated, Islamic Azad University, Tehran, Iran.
10.22034/road.2021.293402.1964
Abstract
Optimal routing is one of the most widely used network issues in transportation planning and aims to find the shortest route among the available routes. Shortest Path Problem Focuses on finding the path with the least distance, time, or cost from source node to destination node. On the other hand, this processing time is very important in applications related to intelligent and user-based transportation. Various deterministic and innovative algorithms are used to perform routing. One of these algorithms is the ant colloquial ant colony optimization algorithm, which is inspired by the ant feeding behavior of ants and deals with the issue of routing from nest to feed, and in the present article, its results with two other algorithms, namely genetics. And Dijkstra is compared. Genetic algorithm is a meta-heuristic algorithm and Dijkstra is a definite algorithm. All three algorithms were tested on three small networks with 200 nodes, medium with 1000 nodes and large with 2000 nodes. Examination of the results showed that the ant colony algorithm gives better results in large networks. The computational time of the ant colony algorithm algorithm is close to the computational time of the genetic algorithm, but it is more accurate and its computational accuracy is the same as the Diextra definitive algorithm method.
Keywords
-Bin, Yu; Zhong-Zhen, Yang; (2010), “An ant colony optimization model: The period vehicle routing problem with time windows”, Transportation Research Part E.
-Bin, Yu; Zhong-Zhen, Yang; Baozhen, Yao; (2009), “An improved ant colony optimization for vehicle routing problem”, European Journal of Operational Research 196, pp.171–176.
-Davies, C., Lingras, P., (2003), “Discrete Optimization, Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks”, European Journal of Operational Research 144, pp. 27–38.
-Dorigo, M., and Blum, C., (2005), “Ant colony optimization theory: A survey”, Theoretical Computer Science 344, pp. 243 – 278.
-Dorigo, M., Stutzle, T., 2004; Ant Colony Optimization; the MIT Press, Cambridge, Massachusetts, London, England, ISBN 0-262-04219-3.
-Gajpal, Yuvraj; Abad, Prakash; )2009(, “An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup”, Computers &Operations Research 36; pp.3215-3223.
-Gao, S., Wang, Y., Cheng, J., Inazumi, Y. and Tang, Z., (2016), “Ant colony optimization with clustering for solving the dynamic location routing problem”, Applied Mathematics and Computation, 285, pp.149-173.
-Gao, Yu., (2011), “Shortest path problem with uncertain arc lengths”, Computers and Mathematics with Applications 62,
pp.2591–2600.
pp.2591–2600.
-Ghezavati, V.R. and Beigi, M., (2016), “Solving a bi-objective mathematical model for location-routing problem with time windows in multi-echelon reverse logistics using metaheuristic procedure”, Journal of Industrial Engineering International, 12(4), pp.469-483.
-Ghoseiri, Keivan; Nadjari, Behnam, (2010), “An ant colony optimization algorithm for the bi-objective shortest path problem”, Applied Soft Computing 10, pp.1237–1246.
-Ginantra, N.L.W.S.R., Taufiqurrahman, T., Bhawika, G.W., Iswara, I.B.A.I. and Wanto, A., (2019), “Determination of the Shortest Route towards the Tourist Destination Area Using the Ant Algorithma”, IOP Publishing, In Journal of Physics: Conference Series, Vol. 1339, No. 1, pp. 012038.
-Ginantra, N.L.W.S.R., Taufiqurrahman, T., Bhawika, G.W., Iswara, I.B.A.I. and Wanto, A., (2019), “Determination of the Shortest Route towards the Tourist Destination Area Using the Ant Algorithma”, IOP Publishing, In Journal of Physics: Conference Series, Vol. 1339, No. 1, pp. 012038.
-Ginantra, N.L.W.S.R., Taufiqurrahman, T., Bhawika, G.W., Iswara, I.B.A.I. and Wanto, A., (2019), “December. Determination of the Shortest Route towards the Tourist Destination Area Using the Ant Algorithma”, IOP Publishing, In Journal of Physics, Conference Series, Vol. 1339, No. 1, pp. 012038.
-Ji, X., (2005), “Models and algorithm for stochastic shortest path problem”, Applied Mathematics and Computation 170, pp.503–514.
-Lee, Chou-Yuan; Lee, Zne-Jung; Lin, Shih-Wei; Ying, Kuo-Ching, (2010), “An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem”,
Appl Intell 32, pp.88–95.
Appl Intell 32, pp.88–95.
-Machuca, E.; Mandow, L.; J.L. Pérez de la Cruz; A. Ruiz-Sepulveda, (2011), “A comparison of heuristic best-first algorithms for bicriterion shortest path problems”, European Journal of Operational Research.
-Mahpour, A., Amiri, A.M., Deldar, M., Saffarzadeh, M. and Nazifi, A., (2018),
“A heuristic method to determine traffic bottlenecks based on ant colony, A case study of Iran, Case Studies on Transport Policy, 6(4),
pp.716-721.
“A heuristic method to determine traffic bottlenecks based on ant colony, A case study of Iran, Case Studies on Transport Policy, 6(4),
pp.716-721.
-Mahpour, A., Mamdoohi, A. and Hakimelahi, A., (2020), “A heuristic technique for traffic assignment with variable step size and number of iterations”, Transportation Research Procedia, 48, pp.2569-2579.
-Mahpour, A., Nazifi, A. and Amiri, A.M., 2021. Development of Optimization Model to Reduce Unloading and Loading Time at Berth in Container Ports. Iranian Journal of Science and Technology, Transactions of Civil Engineering, pp.1-10.
-Min, F., Zhang, Z.H. and Dong, J., (2018), “Ant colony optimization with partial-complete searching for attribute reduction”, Journal of Computational Science, 25, pp.170-182.
-Qureshi, A. G., Taniguchi, E., Yamada, T., (2010), “Exact solution for the vehicle routing problem with semi soft time windows and its application, Procedia Social and Behavioral Sciences 2, pp.5931–5943.
-Vidal, T., Crainic, T.G., Gendreau, M. and Prins, C., (2013), “Heuristics for multi-attribute vehicle routing problems, A survey and synthesis”, European Journal of Operational Research, 231(1), pp.1- 21.
-Vidal, T., Crainic, T.G., Gendreau, M. and Prins, C., (2014), “A unified solution framework for multi attribute vehicle routing problems”, European Journal of Operational Research, 234(3), pp.658-673.
-Wanto, A., Zarlis, M. and Hartama, D., (2017), “Analysis of Artificial Neural Network Back propagation Using Conjugate Gradient Fletcher Reeves in the Predicting Process”, IOP Publishing, In Journal of Physics, Conference Series,Vol. 930, No. 1, pp. 012018.
-Wu, J., Chen, B., Zhang, K., Zhou, J. and Miao, L., (2018), “Ant pheromone route guidance strategy in intelligent transportation systems”, Physica A: Statistical Mechanics and its Applications, 503, pp.591-603.
-Yang, X., Dong, H. and Yao, X., (2017), “Passenger distribution modeling at the subway platform based on ant colony optimization algorithm”, Simulation Modeling Practice and Theory, 77, pp.228- 244.