The Travelling Salesperson Problem with Forbidden Neighborhoods on Re...

We suggest and examine an extension of the Travelling Salesperson Problem (TSP) motivated by an application in mechanical engineering. The TSP with forbidden neighborhoods (TSPFN) with radius r is asking for a shortest Hamiltonian cycle of a given graph G, where vertices traversed successively have a distance larger than r.

The TSPFN is motivated by an application in mechanical engineering, more precisely in laser beam melting. This technology is used for building complex workpieces in several layers, similar to 3D printing. For each layer new material has to be heated up at several points. The question is now how to choose the order of the points to be treated in each layer such that internal stresses are low. Furthermore, one is interested in low cycle times of the workpieces. One idea is to look for short paths between the points or more precisely between the segments in each layer that do not connect segments that are too close so that the heat quantity in each region is not too high in short periods. In particular in the instances resulting from this application the layers are rectangular non-regular grids.

In this work we start with the consideration of regular grids, i.e., adjacent vertices in the same row or column all have the same distance from each other. First we suggest a linear integer programming formulation√

of TSPFN. Then we examine TSPFN with r = 0, r = 1 and r = 2. We determine the length and structure of optimal solutions and show that these problems can be solved in linear time. After discussing optimal TSPFN tours in the plane we briefly consider the three dimensional case and determine optimal TSPFN tours for r = 0 and r = 1 on regular 3D grids. This is joint work with Anja Fischer and Philipp Hungerländer.