Heuristics for K-Independent Total Traveling Salesperson Problem

This paper is concerned with K-independent total traveling salesperson problem (KITTSP) which is a variant of the famous traveling salesperson problem (TSP). KITTSP seeks K mutually independent Hamiltonian tours such that the total cost of these K tours is minimized. KITTSP is an NP-hard problem since it is a generalisation of TSP. KITTSP is a recently introduced problem, and, so far no solution approach exists in the literature for this problem. We have proposed six constructive heuristics to solve KITTSP which are the first approaches for this problem. We have evaluated the performance of these heuristics on an extensive range of TSPLIB instances and presented a detailed comparative study of their performance.