Optimization of vehicle routing based on the combination of ant colony and particle swarm algorithms with the heuristic function of the cosine of angles

Document Type : Original Article

Authors

Department of Computer Engineering, Faculty of Engineering, Arak University, Arak, Iran.

Abstract

The congestion of roads is a very important factor in urban traffic. A lot of research has tried to solve these problems using meta-heuristic algorithms. In these algorithms, firstly, routing is done randomly over large areas. This will increase the search time. In addition, these algorithms only consider the physical distance between the vehicles. Since environmental factors such as traffic are very effective in routing, these factors should be considered in routing. In this paper, to solve the problems, a dynamic path programming method based on the combination of the ant colony algorithm and particle swarm optimization, along with a cosine function of angle, has been proposed. This method takes into account various factors of roads, such as the length of the urban road and the incoming and outgoing traffic at intersections. In the method, the points that are aligned with the navigation path towards the final destination are given more chances. The results of applying the proposed model on the valid data of the TSPLIB library, which is based on the physical distance between cars, show that the search time of the proposed method has decreased by 40.74% on average compared to the results of ten other methods used for evaluation. The highest and lowest rates of decrease are 98.01% and 6.02%, respectively. The test of dynamic route planning under road traffic on some intersections of Beijing city also shows that the proposed method only causes congestion of about 1.57%.

Keywords

Main Subjects

References

[1] J. Yang, A.-O. Purevjav, and S. Li, “The marginal cost of traffic congestion and road pricing: evidence from a natural experiment in Beijing,” American Econ. J. Econ. Policy, vol. 12, no. 1, pp. 418-453, 2020, doi: 10.1257/pol.20170195. 
[2] M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Comput. Intel. Mag., vol. 1, no. 4, pp. 28-39, 2006, doi: 10.1109/ci-m.2006.248054.
[3] I. Karaoglan, F. Altiparmak, I. Kara, and B. Dengiz, “The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach,” Omega, vol. 40, no. 4, pp. 465-477, 2012, doi: 10.1016/j.omega.2011.09.002.
[4] S. Doostali and M. Khalily-Dermany, “A multi-hop PSO based localization algorithm for wireless sensor networks,” Soft Comput. J., vol. 8, no. 1, pp. 58-69, 2019, doi: 10.22052/8.1.58 [In Persian].
[5] R. Ghasemi, H.R. Mohammadi, and S.A. Taher, “Frequency Control of an Islanded Microgrid based on Intelligent Control of Demand Response using Fuzzy Logic and Particle Swarm Optimization (PSO) Algorithm,” Soft Comput. J., vol. 6, no. 2, pp. 18-31, 2018, dor: 20.1001.1.23223707.1396.6.2.2.6 [In Persian].
[6] C. Wu, S. Zhou, and L. Xiao, “Dynamic path planning based on improved ant colony algorithm in traffic congestion,” IEEE Access, vol. 8, pp. 180773-180783, 2020, doi: 10.1109/access.2020.3028467.
[7] H.R. Mohammadi and A. Akhavan, “Performance Comparison of HSA, ICA and PSO Algorithms for Selective Harmonic Elimination in Cascaded Multilevel Inverter with Variable DC Sources,” Soft Comput. J., vol. 3, no. 2, pp. 20-30, 2015, dor: 20.1001.1.23223707.1393.3.2.55.8 [In Persian].
[8] V. Chvatal, W. Cook, G.B. Dantzig, D.R. Fulkerson, and S.M. Johnson, “Solution of a Large-Scale Traveling-Salesman Problem,” in M. Junger, et al. 50 Years of Integer Programming 1958-2008, Springer, Berlin, Heidelberg, 2010, doi: 10.1007/978-3-540-68279-0_1.
[9] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” in Proc. European Conf. Artif. Life (ECAL91), Paris, France, 1991, pp. 134-142. 
[10] G. Shang, J. Xin-zi, T. Kezong, and Y. Jingyu, “Hybrid Algorithm Combining Ant Colony Optimization Algorithm with Particle Swarm Optimization,” in Chinese Control Conf., Harbin, China, 2006, pp. 1428-1432, doi: 10.1109/CHICC.2006.280708.
[11] C.-x. Shi, B. Ying-yong, L. Zi-guang, and T. Jun, “Solving path planning problem by an aco-pso hybrid algorithm,” in Int. Conf. Intell. Syst. Knowl. Eng., Atlantis Press, 2007, pp. 1-4,‏ doi: 10.2991/iske.2007.91.
[12] D. Pal, P. Verma, D. Gautam, and P. Indait, “Improved optimization technique using hybrid ACO-PSO,” in 2nd Int. Conf. Next Gener. Comput. Technol. (NGCT), Dehradun, India, 2016, pp. 277-282, doi: 10.1109/NGCT.2016.7877428.
[13] A.J. Ouyang and Y.Q. Zhou, “An improved PSO-ACO algorithm for solving large-scale TSP,” Adv. Mater. Res., vol. 143-144, pp. 1154-1158, 2010, doi: 10.4028/www.scientific.net/amr.143-144.1154.
[14] W. Li, L. Xia, Y. Huang, and S. Mahmoodi, “An ant colony optimization algorithm with adaptive greedy strategy to optimize path problems,” J. Ambient Intell. Humaniz. Comput., vol. 13, no. 3, pp. 1557-1571, 2022, doi: 10.1007/s12652-021-03120-0.
[15] P. Stodola, P. Otrisal, and K. Hasilova, “Adaptive ant colony optimization with node clustering applied to the travelling salesman problem,” Swarm Evol. Comput., vol. 70, p. 101056, 2022, doi: 10.1016/j.swevo.2022.101056.
[16] R. Zheng, Y. Zhang, and K. Yang, “A transfer learning-based particle swarm optimization algorithm for travelling salesman problem,” J. Comput. Des. Eng., vol. 9, no. 3, pp. 933-948, 2022, doi: 10.1093/jcde/qwac039.
[17] S.A. Al-Agamy, F.M. Ba-Alwi, and A.M. Mohsen, “A Fuzzy Logic for Parameter Adaptation in Ant Colony Optimization Approach,” Int. J. Innov. Sci. Res. Technol. vol. 7, no. 5, pp. 1549-1560, 2022, doi: 10.5281/zenodo.6774879.
[18] M. Sahin, “Solving TSP by using combinatorial Bees algorithm with nearest neighbor method,” Neural Comput. Appl., vol. 35, no. 2, pp. 1863-1879, 2023,‏ doi: 10.1007/s00521-022-07816-y.
[19] Dataset Description (2022, Dec. 02), [Online]. Available: https://github.com/article2023-uni/code-dataset-Description.
[20] W. Zhangqi, Z. Xiaoguang, and H. Qingyao, “Mobile robot path planning based on parameter optimization ant colony algorithm,” Procedia Eng., vol. 15, pp. 2738-2741, 2011,‏ doi: 10.1016/j.proeng.2011.08.515.
[21] A.K.M.F. Ahmed and J.U. Sun, “An improved particle swarm optimization algorithm for the travelling salesman problem,” Adv. Sci. Lett., vol. 22, no. 11, pp.3318-3322, 2016, doi: 10.1166/asl.2016.7864.
[22] X. Xie and P. Wu, “Research on the optimal combination of ACO parameters based on PSO,” in Int. Conf. Netw. Digit. Soc., Wenzhou, China, 2010, pp. 94-97, doi: 10.1109/ICNDS.2010.5479311.
[23] TSPLIB (2022, Dec. 02), [Online]. Available: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
[24] W. Deng, J. Xu, and H. Zhao, “An improved ant colony optimization algorithm based on hybrid strategies for scheduling problem,” IEEE Access, vol. 7, pp. 20281-20292, 2019, doi: 10.1109/access.2019.2897580.
[25] E. Elsayed, A.H. Omar, and K. Elsayed, “Smart solution for STSP semantic traveling salesman problem via hybrid ant colony system with genetic algorithm,” Int. J. Intell. Eng. Syst., vol. 13, no. 5, pp. 476-489, 2020, ‏ doi: 10.22266/ijies2020.1031.42.
[26] A.E. Ezugwu and A.O. Adewumi, “Discrete symbiotic organisms search algorithm for travelling salesman problem,” Expert Syst. Appl., vol. 87, pp. 70-78, 2017,‏ doi: 10.1016/j.eswa.2017.06.007.
[27] E. Liao and C. Liu, “A hierarchical algorithm based on density peaks clustering and ant colony optimization for traveling salesman problem,” IEEE Access, vol. 6, pp. 38921-38933, 2018,‏ doi: 10.1109/access.2018.2853129.
[28] A. Hossam, A. Bouzidi, and M.E. Riffi, “Elephants Herding Optimization for Solving the Travelling Salesman Problem,” in M. Ezziyyani, (eds) Advanced Intelligent Systems for Sustainable Development (AI2SD), Advances in Intelligent Systems and Computing, vol. 912. Springer, Cham, 2019, doi: 10.1007/978-3-030-12065-8_12.
[29] A.E. Ezugwu, A.O. Adewumi, and M.E. Frincu, “Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem,” Expert Syst. Appl., vol.  77, pp. 189-210, 2017, ‏ doi: 10.1016/j.eswa.2017.01.053.
[30] A.I. Hammouri, E.T.A. Samra, M.A. Al-Betar, R.M. Khalil, Z. Alasmer, and M. Kanan, “A Dragonfly Algorithm for Solving Traveling Salesman Problem,” in 8th IEEE Int. Conf. Control Syst. Comput. Eng. (ICCSCE), Penang, Malaysia, 2018, pp. 136-141, doi: 10.1109/ICCSCE.2018.8684963.
[31] Z. Zhang, K. Zou, and J. Zhang, “Parameter Analysis for a Novel Ant Colony Optimization Algorithm,” Eng. Technol. Res., 2016, doi: 10.12783/dtetr/icca2016/6052.
[32] Congest (2022, Dec. 02), [Online]. Available: https://report.amap.com/congest.do.
[33] R.S. Cochran, Book Reviews: J. Neter, W. Wasserman, and G.A. Whitmore, Applied Statistics, Boston: Allyn and Bacon, Inc., 1978. pp. xix + 743. Educ. Psychol. Meas., vol. 40, no. 1, pp. 267-270, 1980, doi: 10.1177/001316448004000148.
[34] M. Amiri, L. Mohammad-Khanli, and R. Mirandola, “A new efficient approach for extracting the closed episodes for workload prediction in cloud,” Computing, vol. 102, no. 1, pp. 141-200, 2020, doi: 10.1007/s00607-019-00734-3.
[35] M. Amiri and H. Askari, “Illegal Miner Detection based on Pattern Mining: A Practical Approach,” J. Comput. Secur., vol. 9, no. 2, pp. 1-10, 2022, doi: 10.22108/jcs.2022.133306.1096.
[36] F. Farnaghi-Zadeh, M. Rahmani, and M. Amiri, “Feature Selection Using Neighborhood based Entropy,” J. Univers. Comput. Sci., vol. 28, no. 11, pp. 1169-1192, 2022, doi: 10.3897/jucs.79905.
[37] F. Jaryani, and M. Amiri, “A Pre-Trained Ensemble Model for Breast Cancer Grade Detection Based on Small Datasets,” Iranian J. Health Sci., vol. 11, no. 1, pp. 47-58, 2023, doi: 10.32598/ijhs.11.1.883.1.
Soft Computing Journal
Volume 12, Issue 2 - Serial Number 24
February 2024
Pages 146-164

Files

History

  • Receive Date: 17 December 2022
  • Revise Date: 09 May 2023
  • Accept Date: 22 June 2023

Share

How to cite

Statistics