explicit solutions – Optimization Online

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

Published: 2017/07/22, Updated: 2018/08/16

Combinatorial Optimization explicit solutions, forbidden neighborhood, grid, traveling salesman problem

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 … Read more

The Traveling Salesman Problem on Grids with Forbidden Neighborhoods

Published: 2016/04/20

Anja Fischer

Philipp Hungerländer

Combinatorial Optimization constrained euclidean traveling salesman problem, explicit solutions, grid, shortest hamiltonian path problem, traveling salesman problem

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