Indian Journal of Science and Technology
Year: 2022, Volume: 15, Issue: 45, Pages: 2468-2475
Moumita Mondal1*, Durgesh Srivastava2
1Department of Computer Science and Engineering, Shri JJT University, Jhunjhunu, 333010, Rajasthan, India
2Department of Computer Science & Engineering, Chitkara University Institute of Engineering & Technology, Chitkara University, Rajpura, 140401, Punjab, India
Email: [email protected]
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
© 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.