They did not check the draft very thoroughly... Picture by Mike McBay licensed under the Creative Commons Attribution 2.0 Generic (CC BY 2.0) license
This is a solver for a generalisation of the Traveling Salesman Problem, namely the Traveling Salesman Problem with Pickups, Deliveries and Draft Limits.
It's a problem that stems from maritime applications, where the draught of a ship is a function of the quantity of cargo it currently has on board. Because of its current draught, a ship might or might not be able to visit a certain port.
This software includes:
- An exact branch-and-cut algorithm
- Constructive heuristics
- K-opt recombination heuristics
- Tabu search meta-heuristics (neighbourhood defined by 3-opt moves)
- An implementation of the subgradient method with lagrangean relaxation
It also contains many test instances derived from the TSPLIB and a script to generate new ones. More info is contained in the other README.md
files present in the subfolders.
If you use this software, please cite the following paper:
@article{malaguti2018travelling,
title={The {Traveling Salesman Problem} with Pickups, Deliveries, and Draft Limits},
author={Malaguti, Enrico and Martello, Silvano and Santini, Alberto},
journal={{Omega}},
volume=74,
pages={50--58},
year=2018,
doi={10.1016/j.omega.2017.01.005}
}
You can also cite this repository via Zenodo.
@misc{tsppddl_github,
title={The Traveling Salesman Problem with Pickups, Deliveries and Draft Limits},
author={Santini, Alberto},
date={2022-12-30},
howpublished={Github repository},
doi={10.5281/zenodo.7494135},
url={https://github.com/alberto-santini/tsppddl/}
}
This software is distributed under the GNU General Public License v3, as detailed in LICENSE.txt
.