Detailansicht
An Enumerative Approach to the Solution of a Multi-Period Orienteering Problem
Alexander Ruth
Art der Arbeit
Magisterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Magisterstudium Statistik
Betreuer*in
Walter Gutjahr
DOI
10.25365/thesis.49828
URN
urn:nbn:at:at-ubw:1-13165.27607.514063-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Üblicherweise werden Orienteering Probleme mithilfe von Heuristiken gelöst. Im Speziellen werden in dieser Magisterarbeit Multiperioden Orienteering Probleme mit nachfolgenden charakteristischen Eigenschaften behandelt. Es gibt keine Kapazitätseinschränkung der Fahrzeuge. Die Nachfrage wächst linear mit der Zeit, kann bei einem Besuch komplett gedeckt werden und sinkt exponentiell falls kein Besuch stattfindet. Es gibt eine vorab festgelegte Anzahl von Zeitpunkten und für jeden Zeitpunkt ist genau eine Tour geplant. Für alle Zeitpunkte ist die Längenbeschränkung der Tour konstant und es gibt keine Rückvergütung falls dieses Limit nicht ausgereizt wird. Es gibt keine Einschränkung der Besuchszeiten der Knoten. Alle Touren starten und enden beim Depot.
Diese Magisterarbeit stellt die Konstruktion eines neuen Algorithmus vor, der dieses spezielle Problem exakt und zeiteffizient lösen kann. Der Algorithmus besteht aus zwei Teilen, wobei zuerst candidate tours ermittelt werden und dann aus diesen der optimale Zeitplan berechnet wird. Ein Vorteil gegenüber vollständiger Enumeration ist die niedrigere Anzahl an Travelling Salesman Problemen (TSP) (deutsch auch "Problem des Handlungsreisenden"), die gelöst werden müssen, da schrittweise durch eine Schranke und das Lösen von Linear Assignment Problemen (LAP) (deutsch auch "Lineares Zuordnungsproblem") einige der zu testenden Touren ausgeschlossen werden. Außerdem werden Subtouren von Touren, die die Nebenbedingungen erfüllen, ausgeschlossen. Daraus ergibt sich die minimale Anzahl von relevanten Touren, was weiters die Laufzeit für die Berechnung des optimalen Zeitplans im Vergleich zur vollständigen Enumeration drastisch verkürzt.
Das Feintuning, welches daraus bestand zu vergleichen, ob es schneller ist die Schranke zu benutzen oder wegzulassen oder wegzulassen und zu entscheiden, ab welchem Zeitpunkt man von LAPs auf TSPs wechseln sollte, stellte sich heraus, dass die optimale Kombination die Verwendung von Schranke und maximaler Anzahl an LAPs ist. Als Demonstration des Algorithmus wird ein Anwendungsbeispiel bearbeitet, dass aus ausgewählten Landeshauptstädten von Österreich und Deutschland besteht, und analysiert.
Abstract
(Englisch)
When dealing with orienteering problems, most people would pick heuristics as their choice. Especially, multi-period orienteering problems with the following characteristics are considered in this thesis. There are no vehicle capacity constraints. The demand grows linear over time, can be accommodated completely upon visit and decays exponentially if not visited. There is a fixed number of time steps and on each time step one tour will be scheduled. The tour length limit is constant without bonus for left over length. There are no time window constraints. Starting and end points are at the depot.
This thesis depicts the construction of a new algorithm which is able to solve multi-period orienteering problems exactly and in an efficient way. This algorithm consists of two parts, generating candidate tours and computing the optimal schedule, respectively. One advantage over standard complete enumeration is the reduction of the number of travelling salesman problems (TSP) that need to be solved. In a stepwise algorithm, many tours are discarded by using an easy-to-compute bound and the solving of linear assignment problems (LAP). Also, subtours of positive TSPs are discarded. This also leaves a lot smaller number to work with for the scheduling problem, which is the second advantage over complete enumeration.
For algorithm tuning multiple options such as the tradeoff between using and not using the bound or between LAPs and TSPs are considered and the best methods are determined by runtime analysis. It turned out that using the bound while using the maximum number of LAPs is the best combination. As a demonstration, a real-world application example with selected provincial capitals of Austria and Germany is profoundly analyzed.
Schlagwörter
Schlagwörter
(Englisch)
Optimization Orienteering Problem TSP Exact Optimization Dynamic Programming
Schlagwörter
(Deutsch)
Optimierung Orienteering Problem TSP Exakte Optimierung Dynamische Programmierung
Autor*innen
Alexander Ruth
Haupttitel (Englisch)
An Enumerative Approach to the Solution of a Multi-Period Orienteering Problem
Paralleltitel (Deutsch)
Ein enumerativer Ansatz zur Lösung des Multiperioden Orienteering Problems
Publikationsjahr
2017
Umfangsangabe
v, 90 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Walter Gutjahr
AC Nummer
AC14509943
Utheses ID
44058
Studienkennzahl
UA | 066 | 951 | |