We study the traveling salesperson problem with forbidden neighborhoods (TSPFN) on regular three-dimensional grids. The TSPFN asks for a shortest tour over all grid points such that successive points along a tour have at least some given distance. We present optimal solutions and explicit construction schemes for the Euclidean TSP and the TSPFN where edges of length at most one are forbidden for grid instances.
Citation
Technical report, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, TR-AAUK-M-O-22-07-17, 2017.