Detailansicht
Branch-and-Price Algorithm for the Team Orienteering Problem with Time-Dependent Rewards
Elena A. Prishchepo
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Betriebswirtschaft
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.47458
URN
urn:nbn:at:at-ubw:1-13164.87778.997253-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Team Orienteering Problem mit zeitabhängigen Belohnungen (Team Orienteering Problem with Time-Dependent Rewards (TOPwTDR)) ist eine Erweiterung des klassischen Team Orienteering Problems, bei der der kundenbezogene Gewinn als eine Zeitfunktion dargestellt wird, z.B. linear fallende Funktion, exponentiell wachsende Funktion etc. Das Ziel des TOPwTDRs besteht darin, den Gesamtgewinn zu maximieren, so dass jeder Kunde innerhalb einer vorgeschriebenen Frist höchstens einmal besucht wird. Das TOPwTDR wurde bisher in der Literatur unter der Annahme von sinkenden Gewinnen betrachtet.
Die Dantzig-Wolfe-Zerlegung wird angewendet und das TOPwTDR wird durch einen Branch-and-Price-Algorithmus exakt gelöst. Zur Lösung des Pricing-Problems wird ein modifizierter Labelling-Algorithmus vorgeschlagen, der in der ersten Stufe für die Spaltenfindung Heuristiken verwendet, um das reduzierte Masterproblem einzugeben. Da die Dominanzregeln aufgrund der zeitabhängigen Gewinne sehr schwach sind, werden Schranken der reduzierten Kosten benutzt, um den Suchraum des Pricing-Problems deutlich zu reduzieren. Zwei Schranken werden implementiert, und zur weiteren Beschleunigung des Algorithmus werden spezielle Verfahren eingesetzt. Die Methode verwendet ein Branching Scheme, das mit dem vorgeschlagenen Spaltenerzeugungsverfahren kompatibel ist.
Für die Durchführung der Berechnungsexperimente werden die klassischen TOP-Instanzen aus der Fachliteratur verwendet, die je nach Problemart leicht modifiziert werden. Die Ergebnisse zeugen von der Wirksamkeit der Methode.
Abstract
(Englisch)
The Team Orienteering Problem with Time-Dependent Rewards (TOPwTDR) is an extension of the classical Team Orienteering Problem, where the profit associated with each customer is a function of time, e.g. linear decreasing, exponentially increasing, etc. The objective of the TOPwTDR is to maximise the total collected profit by finding vehicle routes, which visit each customer at most once within a prescribed time limit. The TOPwTDR has been considered previously in the literature under the assumption of decreasing profits.
The Dantzig-Wolfe decomposition is applied and the TOPwTDR is solved exactly with a Branch-and-Price algorithm. For tackling the Pricing problem a modified labelling algorithm is proposed, which on the first stage uses heuristics to find columns to enter the reduced master problem. As the dominance rules are very weak due to time-dependency of the profits, reduced costs bounding is used to reduce significantly the search space of the Pricing problem. Two of such bounds are implemented, and for further speeding up the algorithm a set of accelerating techniques are employed. The methodology is completed with a branching scheme compatible with the proposed Column Generation procedure.
Computational experiments are conducted on the classical TOP instances found in the literature, slightly modified according to the nature of the problem. The results demonstrate the effectiveness of the method.
Schlagwörter
Schlagwörter
(Englisch)
Branch-and-Price team orienteering problem column generation exact method time-dependent reward
Schlagwörter
(Deutsch)
Branch-and-Price Team Orienteering Problem Column Generation exakte Methode zeitabhängigen Belohnungen
Autor*innen
Elena A. Prishchepo
Haupttitel (Englisch)
Branch-and-Price Algorithm for the Team Orienteering Problem with Time-Dependent Rewards
Paralleltitel (Deutsch)
Der Branch-and-Price Algorithmus für das Team Orienteering Problem mit zeitabhängigen Belohnungen
Publikationsjahr
2017
Umfangsangabe
15 ungezählte Blätter
Sprache
Englisch
Beurteiler*in
Richard Hartl
Klassifikationen
85 Betriebswirtschaft > 85.06 Unternehmensführung ,
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC13793083
Utheses ID
42003
Studienkennzahl
UA | 066 | 915 | |