constrained euclidean traveling salesman problem

A Heuristic for the Traveling Salesperson Problem with Forbidden Neighborhoods on Regular 2D and 3D Grids

  • Philipp Armbrust
  • Philipp Hungerländer
  • Anna Jellen
    • Categories Applications - OR and Management Sciences Tags , , ,

    We examine an extension of the Traveling Salesperson Problem (TSP), the so called TSP with Forbidden Neighborhoods (TSPFN). The TSPFN is asking for a shortest Hamiltonian cycle of a given graph, where vertices traversed successively have a distance larger than a given radius. This problem is motivated by an application in mechanical engineering, more precisely … Read more

    The Traveling Salesman Problem on Grids with Forbidden Neighborhoods

  • Anja Fischer
  • Philipp Hungerländer
    • Categories Combinatorial Optimization Tags , , , ,

    We introduce the Traveling Salesman Problem with forbidden neighborhoods (TSPFN). This is an extension of the Euclidean TSP in the plane where direct connections between points that are too close are forbidden. The TSPFN is motivated by an application in laser beam melting. In the production of a workpiece in several layers using this method … Read more