Montag, 07. November 2016, 16:45 - 17:45 iCal

ISOR Colloquium

"The Traveling Salesman Problem on Grids with Forbidden Neighborhoods"

Philipp Hungerländer (MIT & Univ. Klagenfurt)

Sky Lounge OMP1, 12th Floor
Oskar-Morgenstern-Platz 1, 1090 Vienna

Vortrag

---

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.

Zur Webseite der Veranstaltung

---

Veranstalter

Institut für Statistik und Operations Research

---

Kontakt

Mag. Vera Lehmwald
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38651
vera.lehmwald@univie.ac.at

Erstellt am Freitag, 21. Oktober 2016, 16:02
Letzte Änderung am Montag, 24. Oktober 2016, 08:50