|
|
|
This repository contains algorithms for the Travelling Salesperson *Problem with Circle Placement* **(TSP-CP)** and related subproblems: *Travelling Salesperson Problem with Self-deleting graphs* **(TSP-SD)** and *Weak Path-Conforming Circle Placement Problem* **(WPCCP)**.
|
|
|
|
|
|
|
|
# Travelling Salesperson Problem with Self-deleting graphs (TSP-SD)
|
|
|
|
|
|
|
|
TSP-SD was first introduced in the paper *[The Hamiltonian Cycle and Travelling Salesperson problems with traversal-dependent edge deletion
|
|
|
|
](https://www.sciencedirect.com/science/article/pii/S1877750323002168)*.
|
|
|
|
```
|
|
|
|
@article{Carmesin23jocs,
|
|
|
|
title = {The Hamiltonian Cycle and Travelling Salesperson problems with traversal-dependent edge deletion},
|
|
|
|
author = {Sarah Carmesin and David Woller and David Parker and Miroslav Kulich and Masoumeh Mansouri},
|
|
|
|
journal = {Journal of Computational Science},
|
|
|
|
volume = {74},
|
|
|
|
pages = {102156},
|
|
|
|
year = {2023},
|
|
|
|
issn = {1877-7503},
|
|
|
|
doi = {https://doi.org/10.1016/j.jocs.2023.102156},
|
|
|
|
url = {https://www.sciencedirect.com/science/article/pii/S1877750323002168}
|
|
|
|
}
|
|
|
|
```
|
|
|
|
Given a self-deleting graph $S=(G,f)$, where $G=(V,E)$ is a simple graph and $f:V \to 2^E$ is a delete function, the goal of the TSP-SD is to find the shortest Hamiltonian cycle on $S$.
|
|
|
|
The 11 instances used in `Carmesin23jocs` are available in the `./data/TSPLIB/` directory.
|
|
|
|
|
