Artigo em revista científica 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.);
Título Revista
European Journal of Operational Research
Ano (publicação definitiva)
2023
Língua
Inglês
País
Estados Unidos da América
Mais Informação
Web of Science®

N.º de citações: 2

(Última verificação: 2024-05-12 08:48)

Ver o registo na Web of Science®


: 0.3
Scopus

N.º de citações: 2

(Última verificação: 2024-05-07 21:44)

Ver o registo na Scopus


: 0.3
Google Scholar

Esta publicação não está indexada no Google Scholar

Abstract/Resumo
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.
Agradecimentos/Acknowledgements
--
Palavras-chave
Combinatorial optimisation,Travelling salesman problem,Positional consistency,Healthcare services
  • Matemáticas - Ciências Naturais
  • Ciências da Computação e da Informação - Ciências Naturais
  • Engenharia Civil - Engenharia e Tecnologia
  • Engenharia Mecânica - Engenharia e Tecnologia
  • Engenharia Química - Engenharia e Tecnologia
  • Economia e Gestão - Ciências Sociais
  • Outras Ciências Sociais - Ciências Sociais
Registos de financiamentos
Referência de financiamento Entidade Financiadora
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