Traveling Salesman Problem with Neighborhoods (TSPN) is a generalization of TSP where points are substituted with areas and the objective is to find a minimal cost tour through the set of regions that visits each of them once.
In CSE we propose two methods to solve TSPN – Constricting Insertion Heuristic and Constricting 3-Opt. The further details can be found in:
On Optimizing a Sequence of Robotic Tasks Inproceedings
Proceedings of the International Conference on Intelligent Robots and Systems (IROS), IEEE, 2013.
Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS-2013), AAAI, 2013.
Known Test Instances for TSPN
- We propose a set of test instances for evaluation of methods to solve TSPN: Download.
- Test set presented by I. Gentilini, F. Margot, and K. Shimada. and available here: http://wpweb2.tepper.cmu.edu/fmargot/ampl.html
- There are some similar to TSPN problems, e.g., Close-enough TSP (CETSP). Benchmarks from CETSP also could be used for evaluation of TSPN methods. One known set of tests was made by William Mennell, Bruce Golden and Edward Wasil and available from here: http://drum.lib.umd.edu/handle/1903/9822