The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 3D Grids

  • Anja Fischer
  • Philipp Hungerländer
  • Anna Jellen
    • Categories Combinatorial Optimization Tags , , , Short URL: https://optimization-online.org/?p=14697

    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.

    Article

    Download

    View The Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 3D Grids