Solving a Multi-Conveyance Travelling Salesman Problem using an Ant Colony Optimization Method

Moumita Mondal; Durgesh Srivastava

doi:10.17485/IJST/v15i45.1506

Article

Solving a Multi-Conveyance Travelling Salesman Problem using an Ant Colony Optimization Method

VIEWS 632
PDF 136

Indian Journal of Science and Technology

DOI: 10.17485/IJST/v15i45.1506

Year: 2022, Volume: 15, Issue: 45, Pages: 2468-2475

Original Article

Solving a Multi-Conveyance Travelling Salesman Problem using an Ant Colony Optimization Method

Moumita Mondal^1*, Durgesh Srivastava²

¹Department of Computer Science and Engineering, Shri JJT University, Jhunjhunu, 333010, Rajasthan, India
²Department of Computer Science & Engineering, Chitkara University Institute of Engineering & Technology, Chitkara University, Rajpura, 140401, Punjab, India

*Corresponding Author
Email: [email protected]

Received Date:25 July 2022, Accepted Date:17 November 2022, Published Date:05 December 2022

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

Objectives: A well-known NP-complete problem is the travelling salesman problem (TSP). It has numerous engineering and scientific applications. In this article, we have proposed a multi-conveyance TSP where different conveyances are present to travel from one city to another city. This is an extension to classical TSP. In this TSP, the salesman visits all the cities only once during his/her tour, using different conveyances to travel from one city to another. The cost of travelling between cities using various modes of conveyance varies. The objective of this research is to find the minimum cost tour using an ant colony optimization (ACO) based approach by satisfying the constraints of the proposed multi-conveyance TSP. Method: The considered TSP has been solved using a novel ACO technique. The proposed ACO is adopted with the Roulette-wheel selection and “tuning solution” techniques. We have used a few benchmark datasets from TSPLIB to check the effectiveness of the proposed algorithm. The experimental findings for a few benchmarks TSP instances show that almost always, the proposed ACO is able to find a better result. Then, we used some redefined and randomly generated datasets for experiments. The experimental outcomes for various input datasets are also very encouraging. Findings: The goal of the proposed TSP is to find a complete tour with a minimum cost without exceeding the total travel cost and total travel time. Thus, there are two novel constraints in the classical TSP. Novelty: A unique aspect of the proposed research is the use of several conveyance facilities and a fixed total travel time and cost. This is new, as these three factors are integrated into a single TSP model.

Keywords: Travelling Salesman Problem; Travel Cost; Travel Time; MultiConveyance TSP; Ant Colony Optimization

References

Alipour MM, Razavi SN. A new local search heuristic based on nearest insertion into the convex hull for solving Euclidean TSP. International Journal of Operational Research. 2019;34(3):409. Available from: https://doi.org/10.1504/IJOR.2019.098314
Alzyadat T, Yamin M, Chetty G. Genetic algorithms for the travelling salesman problem: a crossover comparison. International Journal of Information Technology. 2020;12:209–213. Available from: https://doi.org/10.1007/s41870-019-00377-9
Aman B, Ciobanu G. Travelling salesman problem in tissue P systems with costs. Journal of Membrane Computing. 2021;3:97–104. Available from: https://doi.org/10.1007/s41965-021-00077-z
Aziz AA, Mousavi SM, Tavana M, Niaki STA. An investigation of the robustness in the Travelling Salesman problem routes using special structured matrices. International Journal of Systems Science: Operations & Logistics. 2020;7(2):172–181. Available from: https://doi.org/10.1080/23302674.2018.1551584
Boryczka U, Szwarc K. An effective hybrid harmony search for the asymmetric travelling salesman problem. Engineering Optimization. 2020;52(2):218–234. Available from: https://doi.org/10.1080/0305215X.2019.1579804
Budak G, Chen X. Evaluation of the size of time windows for the travelling salesman problem in delivery operations. Complex & Intelligent Systems. 2020;6:681–695. Available from: https://doi.org/10.1007/s40747-020-00167-y
Chandar A, Srinivasan A, Anand GP. Favourable subpopulation migration strategy for travelling salesman problem. International Journal of Business Intelligence and Data Mining. 2022;20(3):299. Available from: https://doi.org/10.1504/IJBIDM.2022.122155
Changdar C, Mondal M, Giri PK, Nandi U, Pal RK. A two-phase ant colony optimization based approach for single depot multiple travelling salesman problem in Type-2 fuzzy environment. Artificial Intelligence Review. 2014;15. Available from: https://doi.org/10.1016/j.swevo.2013.11.001
Derya T, Dinler E, Kececi B. Selective generalized travelling salesman problem. Mathematical and Computer Modelling of Dynamical Systems. 2020;26(1):80–118. Available from: https://doi.org/10.1080/13873954.2019.1705496
Du P, Liu N, Zhang H, Lu J. An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem. Journal of Advanced Transportation. 2021;2021:1–16. Available from: https://doi.org/10.1155/2021/6642009
Eremeev AV, Kovalenko YV. A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem. Memetic Computing. 2020;12(1):23–36. Available from: https://doi.org/10.1007/s12293-019-00291-4
Gharehchopogh FS, Abdollahzadeh B. An efficient harris hawk optimization algorithm for solving the travelling salesman problem. Cluster Computing. 2022;25(3):1981–2005. Available from: https://doi.org/10.1007/s10586-021-03304-5
Herraiz A, Gutierrez M, Ortega-Mier M. Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation. Central European Journal of Operations Research. 2022;30(4):1427–1450. Available from: https://doi.org/10.1007/s10100-021-00784-z
Kaabi J, Harrath Y. Permutation rules and genetic algorithm to solve the traveling salesman problem. Arab Journal of Basic and Applied Sciences. 2019;26(1):283–291. Available from: https://doi.org/10.1080/25765299.2019.1615172
Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, Lee S, Tanchoco JMA, Brunese PA. Multiple traveling salesman problem with drones: Mathematical model and heuristic approach. Computers & Industrial Engineering. 2019;129:14–30. Available from: https://doi.org/10.1016/j.cie.2019.01.020
Obi CJ. Using genetic algorithm to solve multiple traveling salesman problem and considering Carbon emissions. Indian Journal of Science and Technology. 2020;13(36):3707–3715. Available from: https://doi.org/ 10.17485/IJST/v13i36.1316
Oliveira SMD, Bezerra LCT, Stützle T, Dorigo M, Wanner EF, Souza SRD. A computational study on ant colony optimization for the traveling salesman problem with dynamic demands. Computers & Operations Research. 2021;135:105359. Available from: https://doi.org/10.1016/j.cor.2021.105359
Rana S, Srivastava SR. Solving Travelling Salesman Problem Using Improved Genetic Algorithm. Indian Journal of Science and Technology. 2017;10(30):1–6. Available from: https://doi.org/10.17485/ijst/2017/v10i30/115512
Salehi Ö, Glos A, Miszczak JA. Unconstrained binary models of the travelling salesman problem variants for quantum optimization. Quantum Information Processing. 2022;21(2):67. Available from: https://doi.org/10.1007/s11128-021-03405-5
Shahadat ASB, Akhand MAH, Kamal MAS. Visibility Adaptation in Ant Colony Optimization for Solving Traveling Salesman Problem. Mathematics. 2022;10(14):2448. Available from: https://doi.org/10.3390/ math10142448
Soh M, Tsofack BN, Djamegni CT. A multi ant colony optimization approach for the travelling salesman problem. Revue Africaine de la Recherche en Informatique et. Mathématiques Appliquées. INRIA. 2020;34. Available from: https://doi.org/10.46298/arima.6752
Stodola P, Michenka K, Nohel J, Rybanský M. Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem. Entropy. 2020;22(8):884. Available from: https://doi.org/10.3390/e22080884
Stodola P, Otřísal P, Hasilová K. Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem. Swarm and Evolutionary Computation. 2022;70:101056. Available from: https://doi.org/10.1016/j.swevo.2022.101056
Zheng RZ, Zhang Y, Yang K. A transfer learning-based particle swarm optimization algorithm for travelling salesman problem. Journal of Computational Design and Engineering. 2022;9(3):933–948. Available from: https://doi.org/10.1093/jcde/qwac039
Changdar C, Mahapatra GS, Pal RK. An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness. Swarm and Evolutionary Computation. 2014;15:27–37. Available from: https://doi.org/10.1016/j.swevo.2013.11.001
Dorigo M. Optimization, Learning and Natural Algorithms. thesis
Engelbrech A. Fundamentals of computational swarm intelligence. Wiley. 2005.
Dorigo M, Stützle T. Ant colony optimization. Scholarpedia. 2004;2(3):1461.
Osaba E, Yang XS, Diaz F, Lopez-Garcia P, Carballedo R. An improved discrete bat algorithm for symmetric and asymmetric travelling salesman problems. Engineering Applications of Artificial Intelligence. 2016;48(1):59–71. Available from: https://doi.org/10.48550/arXiv.1604.04138

Copyright

© 2022 Mondal & Srivastava. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited. Published By Indian Society for Education and Environment (iSee)