Optimization Online


The Traveling Salesman Problem on Grids with Forbidden Neighborhoods

Anja Fischer(anja.fischer***at***mathematik.uni-goettingen.de)
Philipp Hungerländer(philipp.hungerlaender***at***aau.at)

Abstract: 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 one hopes to reduce the internal stresses of the workpiece by excluding the heating of positions that are too close. The points in this application are often arranged in some regular (grid) structure. In this paper we study optimal solutions of TSPFN instances where the points in the Euclidean plane are the points of a regular grid. Indeed, we explicitly determine the optimal values for the TSPFN and its associated path version on rectangular regular grids for different minimal distances of the points visited consecutively. For establishing lower bounds on the optimal values we use combinatorial counting arguments depending on the parities of the grid dimensions. Furthermore we provide construction schemes for optimal TSPFN tours for the considered cases.

Keywords: Shortest Hamiltonian Path Problem, Traveling Salesman Problem, Constrained Euclidean Traveling Salesman Problem, Grid, Explicit Solutions

Category 1: Combinatorial Optimization

Citation: Preprint 2016-3, Preprint-Serie des Instituts für Numerische und Angewandte Mathematik (Preprint of the Institute for Numerical and Applied Mathematics of the University of Goettingen), April 2016

Download: [PDF]

Entry Submitted: 04/20/2016
Entry Accepted: 04/20/2016
Entry Last Modified: 04/20/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society