AAAI Publications, Twenty-Third International Conference on Automated Planning and Scheduling

Font Size: 
Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods
Sergey Alatartsev, Marcus Augustine, Frank Ortmeier

Last modified: 2013-06-02


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.


Traveling Salesman Problem with Neighborhoods; TSPN; Insertion Heuristic; Sequence optimization

Full Text: PDF