Constricting Insertion Heuristic for Traveling Salesman Problem with Neighborhoods

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.