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

Philipp Armbrust (), Philipp Hungerländer () and Anna Jellen ()
Additional contact information
Philipp Armbrust: Alpen-Adria-Universität Klagenfurt
Philipp Hungerländer: Alpen-Adria-Universität Klagenfurt
Anna Jellen: Alpen-Adria-Universität Klagenfurt

A chapter in Operations Research Proceedings 2018, 2019, pp 95-101 from Springer

Abstract: 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 (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-18500-8_13

Ordering information: This item can be ordered from
http://www.springer.com/9783030185008

DOI: 10.1007/978-3-030-18500-8_13

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().