Optimization Online


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

Philipp Armbrust(pharmbrust***at***edu.aau.at)
Philipp Hungerländer(philipp.hungerlaender***at***aau.at)
Anna Jellen(anna.jellen***at***aau.at)

Abstract: 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 in laser beam melting. This paper discusses a heuristic for solving the TSPFN when there don't exist closed-form solutions and exact approaches fail. The underlying concept is based on Warnsdorff's Rule but allows arbitrary step sizes and produces a Hamiltonian cycle instead of a Hamiltonian path. We implemented the heuristic and conducted a computational study for various neighborhoods. In particular the heuristic is able to find high quality TSPFN tours on 2D and 3D grids, i.e., it produces optimum and near-optimum solutions and shows a very good scalability also for large instances.

Keywords: Constrained Euclidean Traveling Salesman Problem, Warnsdorff's Rule, Forbidden Neighborhoods, Grid

Category 1: Applications -- OR and Management Sciences

Citation: TR-AAUK-M-O-18-09-10, Alpen-Adria-Universität Klagenfurt, Mathematics, Optimization Group, September 2018

Download: [PDF]

Entry Submitted: 09/10/2018
Entry Accepted: 09/10/2018
Entry Last Modified: 09/10/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