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: |
|
||||
| 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 |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum