 Formulations and Branch-and-cut algorithms for the Period Travelling Salesman ProblemSofia Henriques and Ana Paias European Journal of Operational Research, 2025, vol. 323, issue 3, 739-752 Abstract: In this work, we address two variants of the Period Travelling Salesman Problem: one where some nodes cannot be visited consecutively over the time horizon, and another one where this restriction is not imposed. A new flow-based formulation that uses specific information about the visit patterns of nodes is studied and empirical tests show that it is able to solve test instances where a flow-based formulation based on the Single Commodity Flow formulation for the Travelling Salesman Problem reached the time limit. Non-compact formulations are studied in this work as well. We propose two new sets of exponentially-sized valid inequalities that have not been studied yet in the literature. A formulation which is based on connectivity cuts per period enhanced with these sets of valid inequalities proved to be the most efficient and it was able to solve several instances. Keywords: Combinatorial optimisation; Period travelling salesman problem; Multicommodity flows; Valid inequalities; Branch-and-cut (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:323:y:2025:i:3:p:739-752 DOI: 10.1016/j.ejor.2025.01.015 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 |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.