The multiple travelling salesperson problem with hotel selection

In this paper, the multiple travelling salesperson problem with hotel selection (m-TSPHS) is presented. This combinatorial optimisation problem is a generalisation of both the travelling salesperson problem with hotel selection (TSPHS) and the multiple travelling salesperson problem (m-TSP). As in the TSPHS, a tour is split into trips whose duration does not exceed a certain travel time, the objective of the m-TSPHS is to design a collection of tours, one for each available salesperson, while minimising the total travel costs. A set-partitioning formulation is presented as well as an efficient solution method together with a number of benchmark instances in order to evaluate the algorithm. Experimental results show that the proposed method is able to keep average gaps with respect to optimal solutions below 1:5%.