Problema do Caixeiro Viajante Periódico com restrições de consistência

Financiador

Organização

Publicações

The Travelling salesman problem with positional consistency constraints

Publication . Ponte, Mafalda; Gouveia, Luís Eduardo Neves; Paias, Ana Maria Duarte Silva Alves

Consider a depot and a set of client nodes divided into non-disjoint subsets. Each subset is associated with a route. The aim of the Travelling Salesman Problem with positional consistency constraints is to generate a minimum cost set of routes, one for each subset, such as all the routes start and end at the depot, and each route visits all the nodes of the corresponding subset. Positional consistency means that client nodes should be visited in the same relative position in all the routes they appear in. The problem was inspired by an application in healthcare services. Several compact formulations were developed to solve the problem with the current ILP packages. Due to the positional constraints, the study focused on so-called time-dependent formulations with specially developed consistency constraints. To overcome the size of the previously proposed formulations, an aggregated formulation that does not use route-indexed variables was also proposed and shown to be valid. Some enhancements were proposed for disaggregated and aggregated models, some including exponentially sized sets of constraints for which separation routines were implemented. Theoretical relations of the corresponding LP relaxations were also established. An empirical comparison was carried out using instances with characteristics from the healthcare application and more general instances adapted from the literature. Computational results show that, in some cases, the aggregated formulation is the most efficient one. An iterated local search algorithm was also developed to address the instances that the exact methods could not solve to optimality. The heuristic showed a robust performance for the instances with known optimal solutions and was able to improve, in some cases, considerably, the upper bounds provided by the ILP packages combined with the proposed models, for most of the remaining instances.

2023-07Tese de doutoramento

Acesso aberto

Ver mais

Entidade financiadora

Fundação para a Ciência e a Tecnologia

Número da atribuição

SFRH/BD/146812/2019