Solving the k-best traveling salesman problem

Although k-best solutions for polynomial solvable problems are extensively studied in the literature not much is known for NP-hard problems. In this paper we design algorithms for finding sets of k-best solutions to the Traveling Salesman Problem (TSP) for some positive integer k. It will be shown that a set of k-best Hamiltonian tours in a weighted graph can be determined by applying the so-called partitioning algorithms and by algorithms based on modifications of solution methods like branch-and-bound. In order to study the effectiveness of these algorithms the time for determining a set of k-best solutions is investigated for a number of instances in Reinelt's TSPLIB library. It appears that the time required to find a set of k-best tours grows rather slowly in k. Furthermore the results of numerical experiments show that the difference in length between a longest and a shortest tour in the set of k-best solutions grows only slowly in k and that also the 'structure' of the tours in the set of k-best tours is quite robust.Scope and purposeAfter having solved an optimization problem, it is often the case that one still must verify whether the optimal solution satisfies some additional restrictions that are not included in the original model. Such conditions are called ''subtle conditions''. In the case of subtle conditions, it is particularly of interest to have a set of k-best solutions in order to see which of the solutions in that set satisfy the extra conditions and how high the ''price'' is for incorporating such conditions.Algorithms for finding sets of k-best solutions have mainly been studied in the literature for polynomially solvable combinatorial optimization problems. Little is known on algorithms for finding k-best solutions for NP-hard combinatorial optimization problems. In this paper, we study algorithms for finding k-best solutions for one of the most notorious NP-hard problems, namely the Traveling Salesman Problem (TSP). Properties of the sets of k-best solutions for the TSP, such as the increase in tour length and the number of edges that the k-best solutions have in common or differ in, are discussed in detail.