Publications
Publications › References ›
2023
Journal papers
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 MB
BibTeX
- 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.