Optimization Online


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

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

Abstract: 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.

Keywords: Traveling salesman problem, forbidden neighborhood, grid, explicit solutions.

Category 1: Combinatorial Optimization

Citation: Technical report, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, TR-AAUK-M-O-22-07-17, 2017.

Download: [PDF]

Entry Submitted: 07/22/2017
Entry Accepted: 08/01/2017
Entry Last Modified: 08/16/2018

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