Traveling Salesman Problem with Neighborhoods (TSPN)

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.

Our Approaches

In CSE we propose two methods to solve TSPN – Constricting Insertion Heuristic  and Constricting 3-Opt. The further details can be found in:

Alatartsev, Sergey; Mersheeva, Vera; Augustine, Marcus; Ortmeier, Frank

On Optimizing a Sequence of Robotic Tasks Inproceedings

Proceedings of the International Conference on Intelligent Robots and Systems (IROS), IEEE, 2013.

Abstract | Links | BibTeX

Alatartsev, Sergey; Augustine, Marcus; Ortmeier, Frank

Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods Inproceedings

Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS-2013), AAAI, 2013.

Abstract | Links | BibTeX

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
Traveling Salesman Problem with Neighborhoods (TSPN)