A fast metaheuristic for the travelling salesperson problem with hotel selection

The travelling salesperson problem with hotel selection (TSPHS) is a recently proposed variant of the travelling salesperson problem. Currently, the approach that finds the best solutions is a memetic algorithm. However, this approach is unsuitable for applications that require very short computation times. In this paper, a new set-partitioning formulation is presented along with a simple but powerful metaheuristic for the TSPHS. The algorithm is able to obtain very competitive results while remaining at least one order of magnitude faster than the best-performing method so far. The parameters of the metaheuristic were carefully tuned by means of an extensive statistical experiment.