Solving k-city multiple travelling salesman using genetic algorithm

Abstract

This paper addresses a novel variant of the classical multiple traveling salesman problem (MTSP) i.e. k-city multiple traveling salesman problem (k-MTSP). The problem can describe as follows. Let there are n cities, m salesman positioned at depot city and a predefined positive value k. The distance between each pair of cities is known. The objective of the k-MTSP is to determine a collection of m closed tours for salesman, which covers exactly k (including depot city) of n cities such that the total distance covered is minimum. The k-MTSP can be seen as a combination of both subset selection and permutation characteristics. From the through literature review, it is found that this study on k-MTSP is first of its kind to the best of author’s knowledge. The paper introduces a zero-one integer linear programming (0-1 ILP) formulation alongside an efficient genetic algorithm (GA), designed to address k-MTSP. No comparative studies carried out due to the absence of existing studies on k-MTSP. However, the developed GA is tested over various benchmark test cases from TSPLIB and results are reported, which may potentially serve as basis for further comparative studies. Overall findings demonstrate that the GA consistently produces best solutions within reasonable computational times for relatively smaller and medium test cases, suggesting its robustness and effectiveness in tackling the k-MTSP. However, to enhance consistency and efficiency, particularly for larger datasets, further algorithm improvements are necessary.