Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods

Alatartsev, Sergey; Augustine, Marcus; Ortmeier, Frank

doi:10.13140/2.1.4267.6165

by Sergey Alatartsev, Marcus Augustine, Frank Ortmeier

Abstract:

Sequence optimization is an important problem in many production automation scenarios involving industrial robots. Mostly, this is done by reducing it to Traveling Salesman Problem (TSP). However, in many industrial scenarios optimization potential is not only hidden in optimizing a sequence of operations but also in optimizing the individual operations themselves. From a formal point of view, this leads to the Traveling Salesman Problem with Neighborhoods (TSPN). TSPN is a generalization of TSP where areas should be visited instead of points. In this paper we propose a new method for solving TSPN efficiently. We compare the new method to the related approaches using existing test benchmarks from the literature. According to the evaluation on instances with known optimal values, our method is able to obtain a solution close to the optimum.

Reference:

Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods (Sergey Alatartsev, Marcus Augustine, Frank Ortmeier), In Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS-2013), AAAI, 2013.

Bibtex Entry:

@inproceedings{alatartsev_constricting_2013,
	address = {Rome},
	title = {Constricting {Insertion} {Heuristic} for {Traveling} {Salesman} {Problem} with {Neighborhoods}},
	doi = {10.13140/2.1.4267.6165},
	abstract = {Sequence optimization is an important problem in many production automation scenarios involving industrial robots. Mostly, this is done by reducing it to Traveling Salesman Problem (TSP). However, in many industrial scenarios optimization potential is not only hidden in optimizing a sequence of operations but also in optimizing the individual operations themselves. From a formal point of view, this leads to the Traveling Salesman Problem with Neighborhoods (TSPN). TSPN is a generalization of TSP where areas should be visited instead of points. In this paper we propose a new method for solving TSPN efficiently. We compare the new method to the related approaches using existing test benchmarks from the literature. According to the evaluation on instances with known optimal values, our method is able to obtain a solution close to the optimum.},
	booktitle = {Proceedings of the 23rd {International} {Conference} on {Automated} {Planning} and {Scheduling} ({ICAPS}-2013)},
	publisher = {AAAI},
	author = {Alatartsev, Sergey and Augustine, Marcus and Ortmeier, Frank},
	year = {2013},
	pages = {2--10}
}