Mathematical formulations for consistent travelling salesman problems

Daniel Díaz-Ríos and Juan-José Salazar-González

European Journal of Operational Research, 2024, vol. 313, issue 2, 465-477

Abstract: The consistent travelling salesman problem looks for a minimum-cost set of Hamiltonian routes, one for every day of a given time period. When a customer requires service in several days, the service times on different days must differ by no more than a given threshold (for example, one hour). We analyze two variants of the problem, depending on whether the vehicle is allowed to wait or not at a customer location before its service starts. There are three mathematical models in the literature for the problem without waiting times, and this paper describes a new model appropriated to be solved with a branch-and-cut algorithm. The new model is a multi-commodity flow formulation on which Benders’ Decomposition helps manage a large number of flow variables. There were no mathematical models in the literature for the variant with waiting times, and this paper adapts the four mathematical models to it. We analyze the computational results of the formulations on instances from the literature with up to 100 customers and three days.

Keywords: Travelling salesman; Time consistency; Benders’ decomposition; Branch and cut (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723006501
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:313:y:2024:i:2:p:465-477

DOI: 10.1016/j.ejor.2023.08.021

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().