Heuristic Approaches for the Probabilistic Traveling Salesman Problem

Christoph Weiler, Benjamin Biesinger, Bin Hu, G. Raidl

Publikation: Beitrag in Buch oder TagungsbandBeitrag in Tagungsband ohne Präsentation


The Probabilistic Traveling Salesman Problem (PTSP) is a variant of the classical Traveling Salesman Problem (TSP) where each city has a given probability requiring a visit. We aim for an a-priori tour including every city that minimizes the expected length over all realizations. In this paper we consider different heuristic approaches for the PTSP. First we analyze various popular construction heuristics for the classical TSP applied on the PTSP: nearest neighbor, farthest insertion, nearest insertion, radial sorting and space filling curve. Then we investigate their extensions to the PTSP: almost nearest neighbor, probabilistic farthest insertion, probabilistic nearest insertion. To improve the constructed solutions we use existing 2-opt and 1-shift neighborhood structures for which exact delta evaluation formulations exist. These are embedded within a Variable Neighborhood Descent framework into a Variable Neighborhood Search. Computational results indicate that this approach is competitive to already existing heuristic algorithms and able to find good solutions in low runtime.
TitelComputer Aided Systems Theory - EUROCAST 2015
PublikationsstatusVeröffentlicht - 2015

Research Field

  • Ehemaliges Research Field - Mobility Systems


Untersuchen Sie die Forschungsthemen von „Heuristic Approaches for the Probabilistic Traveling Salesman Problem“. Zusammen bilden sie einen einzigartigen Fingerprint.

Diese Publikation zitieren