Scientific journal paper Q1
The travelling salesman problem with positional consistency constraints: An application to healthcare services
Luís Gouveia (Gouveia, L.); Ana Paias (Paias, A.); Mafalda Ponte (Ponte, M.);
Journal Title
European Journal of Operational Research
Year (definitive publication)
2023
Language
English
Country
United States of America
More Information
Web of Science®

Times Cited: 2

(Last checked: 2024-05-19 01:49)

View record in Web of Science®


: 0.3
Scopus

Times Cited: 2

(Last checked: 2024-05-15 08:08)

View record in Scopus


: 0.3
Google Scholar

This publication is not indexed in Google Scholar

Abstract
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.
Acknowledgements
--
Keywords
Combinatorial optimisation,Travelling salesman problem,Positional consistency,Healthcare services
  • Mathematics - Natural Sciences
  • Computer and Information Sciences - Natural Sciences
  • Civil Engineering - Engineering and Technology
  • Mechanical Engineering - Engineering and Technology
  • Chemical Engineering - Engineering and Technology
  • Economics and Business - Social Sciences
  • Other Social Sciences - Social Sciences
Funding Records
Funding Reference Funding Entity
PTDC/MAT-NAN/2196/2014 Fundação para a Ciência e a Tecnologia
SFRH/BD/146812/2019 Fundação para a Ciência e a Tecnologia
UIDB/04561/2020 Fundação para a Ciência e a Tecnologia