The travelling salesman problem with positional consistency constraints: An application to healthcare services

In this paper we study the Consistent Traveling Salesman Problem with positional consistency constraints (CTSP), where we seek to generate a set of routes with minimum cost, in which all the clients that are visited in several routes require total positional consistency, that is, they need to appear in the same relative position in all the routes they are visited in. This problem was motivated by a scheduling application in healthcare. We present several compact formulations for the CTSP, which have been adapted from models known from the Time-dependent TSP (TDTSP) literature, and propose a new model, which is an aggregated version of a model adapted from the TDTSP. A preliminary computational experiment allowed us to identify the three most competitive models. These models were then evaluated in more detail, first through a set of instances with 2, 3 or 5 routes and characteristics that derive from an healthcare application; and second through a set of tests with 5 routes and seven different and more general consistency configurations. The computational results show that for consistency configurations in which the consistent nodes appear in all, or most, of the routes, the new aggregated model can outperform the best model adapted from the literature. For the cases where the consistent nodes appear in fewer routes or less frequently, the original time-dependent model is more efficient.