• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

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

Original Article

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

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


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


  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. Dorigo M, Stützle T. Ant colony optimization. Scholarpedia. 2004;2(3):1461.
  24. 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


© 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)


Subscribe now for latest articles and news.