Publication: Traveling Salesman Problem with Neighborhoods (TSPN)
The Traveling Salesman Problem with Neighborhoods (TSPN) is a generalization of the TSP where points are replaced by neighborhoods and the goal is to find a minimum cost tour through the set of neighborhoods visiting each of them once.
Our approaches
In CSE, we propose two methods for solving TSPN - Constricting Insertion Heuristic and Constricting 3-Opt. For more details, please refer to:
- Alatartsev, Sergey & Mersheeva, Vera & Augustine, Marcus & Ortmeier, Frank. (2013). On Optimizing a Sequence of Robotic Tasks. IEEE International Conference on Intelligent Robots and Systems. 10.1109/IROS.2013.6696356.
- Alatartsev, Sergey & Augustine, Marcus & Ortmeier, Frank. (2013). Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods. 10.13140/2.1.4267.6165.
Known test instances for TSPN
- We propose a set of test instances to evaluate methods for solving TSPN: Download
- The test set was presented by I. Gentilini, F. Margot and K. Shimada and is available here: http://wpweb2.tepper.cmu.edu/fmargot/ampl.html
- There are some similar problems to TSPN, e.g. Close-enough TSP (CETSP). Benchmarks from CETSP could also be used to evaluate TSPN methods. A well-known test set was created by William Mennell, Bruce Golden and Edward Wasil and is available here: http://drum.lib.umd.edu/handle/1903/9822