TU Darmstadt / ULB / TUbiblio

Competitive analysis of the online dial-a-ride problem

Birx, Alexander (2020)
Competitive analysis of the online dial-a-ride problem.
Technische Universität Darmstadt
doi: 10.25534/tuprints-00014134
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

Online optimization, in contrast to classical optimization, deals with optimization problems whose input data is not immediately available, but instead is revealed piece by piece. An online algorithm has to make irrevocable optimization decisions based on the arriving pieces of data to compute a solution of the online problem. The quality of an online algorithm is measured by the competitive ratio, which is the quotient of the solution computed by the online algorithm and the optimum offline solution, i.e., the solution computed by an optimum algorithm that has knowledge about all data from the start.

In this thesis we examine the online optimization problem online Dial-a-Ride. This problem consists of a server starting at a distinct point of a metric space, called origin, and serving transportation requests that appear over time. The goal is to minimize the makespan, i.e., to complete serving all requests as fast as possible. We distinguish between a closed version, where the server is required to return to the origin, and an open version, where the server is allowed to stay at the destination of the last served request.

In this thesis, we provide new lower bounds for the competitive ratio of online Dial-a-Ride on the real line for both the open and the closed version by expanding upon the approach of Bjelde et al.'s work. In the case of the open version, the improved lower bound separates online Dial-a-Ride from its special case online TSP, where starting position and destination of requests coincide.

To produce improved upper bounds for the competitive ratio of online Dial-a-Ride, we generalize the design of the Ignore algorithm and the Smartstart algorithm into the class of schedule-based algorithms. We show lower bounds for the competitive ratios of algorithms of this class and then provide a thorough analysis of Ignore and Smartstart. Identifying and correcting a critical weakness of Smartstart gives us the improved Smarterstart algorithm. This schedule-based algorithm attains the best known upper bound for open online Dial-a-Ride on the real line as well as on arbitrary metric spaces.

Finally, we provide an analysis of the Replan algorithm improving several known bounds for the algorithm's competitive ratio.

Typ des Eintrags: Dissertation
Erschienen: 2020
Autor(en): Birx, Alexander
Art des Eintrags: Erstveröffentlichung
Titel: Competitive analysis of the online dial-a-ride problem
Sprache: Englisch
Referenten: Disser, Prof. Dr. Yann ; Stougie, Prof. Dr. Leen
Publikationsjahr: 10 September 2020
Ort: Darmstadt
Datum der mündlichen Prüfung: 9 Oktober 2020
DOI: 10.25534/tuprints-00014134
URL / URN: https://tuprints.ulb.tu-darmstadt.de/14134
Kurzbeschreibung (Abstract):

Online optimization, in contrast to classical optimization, deals with optimization problems whose input data is not immediately available, but instead is revealed piece by piece. An online algorithm has to make irrevocable optimization decisions based on the arriving pieces of data to compute a solution of the online problem. The quality of an online algorithm is measured by the competitive ratio, which is the quotient of the solution computed by the online algorithm and the optimum offline solution, i.e., the solution computed by an optimum algorithm that has knowledge about all data from the start.

In this thesis we examine the online optimization problem online Dial-a-Ride. This problem consists of a server starting at a distinct point of a metric space, called origin, and serving transportation requests that appear over time. The goal is to minimize the makespan, i.e., to complete serving all requests as fast as possible. We distinguish between a closed version, where the server is required to return to the origin, and an open version, where the server is allowed to stay at the destination of the last served request.

In this thesis, we provide new lower bounds for the competitive ratio of online Dial-a-Ride on the real line for both the open and the closed version by expanding upon the approach of Bjelde et al.'s work. In the case of the open version, the improved lower bound separates online Dial-a-Ride from its special case online TSP, where starting position and destination of requests coincide.

To produce improved upper bounds for the competitive ratio of online Dial-a-Ride, we generalize the design of the Ignore algorithm and the Smartstart algorithm into the class of schedule-based algorithms. We show lower bounds for the competitive ratios of algorithms of this class and then provide a thorough analysis of Ignore and Smartstart. Identifying and correcting a critical weakness of Smartstart gives us the improved Smarterstart algorithm. This schedule-based algorithm attains the best known upper bound for open online Dial-a-Ride on the real line as well as on arbitrary metric spaces.

Finally, we provide an analysis of the Replan algorithm improving several known bounds for the algorithm's competitive ratio.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Im Kontrast zur klassischen Optimierung, handelt Online Optimierung von Optimierungsproblemen, deren Parameter nicht unmittelbar bekannt sind, sondern stattdessen nach und nach verfügbar werden. Ein online Algorithmus muss unwiderrufliche Optimierungsentscheidungen basierend auf den gerade vorhandenen Daten treffen, um eine Lösung des online Optimierungsproblems zu berechnen. Die Güte eines online Algorithmus wird als kompetitiver Faktor angegeben. Dieser ist der Quotient einer Lösung, welche von einem online Algorithmus berechnet wurde, und der optimalen offline Lösung, d. h., der Lösung, die von einem optimalen Algorithmus berechnet wurde, der alle Daten bereits zu Beginn zur Verfügung hat.

In dieser Dissertation wird das online Problem online Dial-a-Ride behandelt. In diesem online Problem muss ein Zusteller, welcher in einem ausgezeichneten Punkt, Ursprung genannt, eines metrischen Raumes startet, Transportanfragen, welche zu verschiedenen Zeitpunkten erscheinen, bedienen.Ziel ist es, die Gesamtzeit für das Bedienen aller Anfragen zu minimieren. Wir unterscheiden zwischen einer geschlossenen Version des Problems, in der der Zusteller wieder zum Ursprung zurückkehren muss und einer offenen Version des Problems.

In dieser Dissertation beweisen wir verbesserte untere Schranken für den kompetitiven Faktor von online Dial-a-Ride auf der reellen Achse, sowohl für die offene, als auch für die geschlossene Variante des Problems. Die Schranke für die offene Version baut auf einer Konstruktion aus der Arbeit von Bjelde et al. auf und separiert online Dial-a-Ride von seinem Spezialfall online TSP, in welchem jede Anfrage jeweils den gleichen Start- und Endpunkt hat.

Im Weiteren verallgemeinern wir das Design des Ignore Algorithmus und des Smartstart Algorithmus und führen die Klasse der schedulebasierten Algorithmen. Wir zeigen untere Schranken an den kompetitiven Faktor von Algorithmen dieser Klasse und führen eine umfassende Analyse von Ignore und Smartstart durch. Durch das Identifizieren und Beheben einer kritischen Schwäche von Smartstart, erhalten wir den Algorithmus Smarterstart. Dieser schedulebasierte Algorithmus ist der beste bekannte Algorithmus für online Dial-a-Ride sowohl auf der reellen Achse als auch in beliebigen metrischen Räumen.

Abschließend analysieren wir den Algorithmus Replan und verbessern mehrere bekannte Schranken an seinen kompetitiven Faktor.

Deutsch
URN: urn:nbn:de:tuda-tuprints-141341
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): Exzellenzinitiative
Exzellenzinitiative > Graduiertenschulen
Exzellenzinitiative > Graduiertenschulen > Graduate School of Computational Engineering (CE)
04 Fachbereich Mathematik
04 Fachbereich Mathematik > Optimierung
04 Fachbereich Mathematik > Optimierung > Discrete Optimization
Hinterlegungsdatum: 21 Okt 2020 07:22
Letzte Änderung: 27 Okt 2020 08:33
PPN:
Referenten: Disser, Prof. Dr. Yann ; Stougie, Prof. Dr. Leen
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 9 Oktober 2020
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen