The Hamiltonian Cycle and Travelling Salesperson problems with traversal-dependent edge deletion

[CWP+23] Sarah Carmesin, David Woller, David Parker, Miroslav Kulich and Masoumeh Mansouri. The Hamiltonian Cycle and Travelling Salesperson problems with traversal-dependent edge deletion. Journal of Computational Science, 74, Elsevier. December 2023. pdf bib

Downloads
PDF 1.54 MBBibTeX
Search for this paper
Google · Google Scholar

Abstract

Variants of the well-known Hamiltonian Cycle and Travelling Salesperson problems have been studied for decades. Existing formulations assume either a static graph or a temporal graph in which edges are available based on some function of time. In this paper, we introduce a new variant of these problems inspired by applications such as open-pit mining, harvesting and painting, in which some edges become deleted or untraversable depending on the vertices that are visited. We formally define these problems and provide both a theoretical and experimental analysis of them in comparison with the conventional versions. We also propose two solvers, based on an exact backward search and a meta-heuristic solver, and provide an extensive experimental evaluation.