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
Ph.D. Thesis, Primary publication

Preview

Text
thesis_birx_final.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.
Download (2MB) | Preview

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

Competitive analysis of the online dial-a-ride problem

Language:

English

Referees:

Disser, Prof. Dr. Yann ; Stougie, Prof. Dr. Leen

Date:

10 September 2020

Place of Publication:

Darmstadt

Date of oral examination:

9 October 2020

DOI:

10.25534/tuprints-00014134

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.

Alternative Abstract:

Alternative Abstract

Language

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.

German

URN:

urn:nbn:de:tuda-tuprints-141341

Classification DDC:

500 Science and mathematics > 510 Mathematics

Divisions:

Exzellenzinitiative > Graduate Schools > Graduate School of Computational Engineering (CE)
04 Department of Mathematics > Optimization > Discrete Optimization

Date Deposited:

21 Oct 2020 07:22

Last Modified:

29 Sep 2022 12:45