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 rela-tive 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 con-sistency 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.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper explores the Consistent Traveling Salesman Problem with positional consistency constraints (CTSP), which aims to find a set of routes with minimal cost while ensuring that all visited clients maintain positional consistency across routes. Various compact formulations and a new aggregated model derived from Time-dependent TSP (TDTSP) models are presented. Computational experiments reveal that the new aggregated model outperforms existing models in cases with consistent nodes appearing in all or most routes, while the original time-dependent model is more efficient when consistent nodes appear in fewer routes or less frequently.