Title: An ant colony optimisation-based approach to solve time interval dependent travelling salesman problem under fuzziness

Authors: Chiranjit Changdar; Kousik Dhara; Rajat Kumar Pal; Pravash Kumar Giri

Addresses: Department of Computer Science, Raja N.L. Khan Women's College, Midnapore, 721102, West Bengal, India ' Jhikuria Bani Vidyamandir (HS), Jhikuria, Debra, Paschim Medinipur, 721156, West Bengal, India ' Department of Computer Science and Engineering, University of Calcutta, Kolkata, 700106, West Bengal, India ' Department of Mathematics, Government General Degree College, Dantan-II, Kashmuli, Porolda, Paschim Medinipur, 721445, West Bengal, India

Abstract: In this study, we have explained a constrained travelling salesman problem (TSP) where total travelling cost must maintain a maximum level. The objective of this proposed TSP is to minimise the total travel time. In this proposed TSP we have considered a time interval dependent constraint as well. There is a time interval in which a traveller must visit a predetermined set of cities (city-set). Here, a city-set consists of a set of cities and the time interval is a time slot in his/her total time to complete the tour. The problem is solved in fuzzy random environment. The travel cost, time, and total travelling cost limit are considered as fuzzy random in nature. The proposed TSP is solved by an ant colony optimisation (ACO)-based approach. The basic ACO algorithm is improved by adopting a filtering operation. Finally, experimental results are given to illustrate the proposed approach; the computed results obtained are also highly encouraging.

Keywords: travelling salesman problem; TSP; ant colony optimisation; ACO; city-set; filtering operation; fuzzy random number.

DOI: 10.1504/IJCSM.2021.118792

International Journal of Computing Science and Mathematics, 2021 Vol.14 No.2, pp.196 - 214

Received: 04 Jun 2018
Accepted: 13 Nov 2018
Published online: 08 Nov 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article