Online-Optimisation of a travelling salesman problem on the circle with lookahead

Die mathematische Optimierungstheorie geht davon aus, dass grundsätzlich zur Bearbeitung einer Problemstellung alle Daten bereits vorliegen. Unter diesen Voraussetzungen spricht man von einer Offline-Bearbeitung. In der alltäglichen Praxis hingegen sind meist schon dann Entscheidungen zu treffen, wenn noch nicht alle Daten bekannt sind. Die damit verbundene Aufgabenstellung ist die Online-Optimierung. Hierbei geht es darum, anhand von Teilmengen der Daten derartige Entscheidungen zu treffen, dass das Ergebnis insgesamt über alle Daten nicht zu schlecht ausfällt. Da bei der Entscheidungsfindung nur ein Teil der gesamten Daten einbezogen werden kann, sind die dabei entstehenden Lösungsvorschläge in der Regel nicht optimal und daher das Endergebnis meist schlechter als das der Offline-Bearbeitung. Die vorliegende Arbeit stellt beispielhaft für eine konkrete Problemstellung dar, welchen Mehrwert eine Verbesserung der Informationslage, bis hin zur kompletten Information der Offline-Bearbeitung, für den Online-Algorithmus hat. Der erste Teil stellt dabei die Theorie und ausgewählte Algorithmen der Online-Optimierung vor. Hierbei wird insbesondere Bezug genommen auf die kompetitive Analyse, diese ist ein Worst-Case Vergleich zwischen der Güte der Offline-Bearbeitung und der des Online-Algorithmus. Der zweite Teil umfasst eine Einführung des Informationsvorlaufs, dabei werden die beiden konzeptionellen Ansätze einer Vorschauinformation und einer Bearbeitungsinformation eingeführt und erläutert. Im dritten Teil, dem Kernstück der Arbeit, wird die Problemstellung der Rundreise auf der Kreislinie, also die Zielsetzung bekannte Punkte auf der Kreislinie aufzusuchen, analytisch und empirisch untersucht. Die Ziele werden nur nach und nach bekannt, das heißt das nächste Ziel muss immer aus einer kleinen Teilmenge an Zielen ausgewählt werden. Dabei wird unterstellt, dass die Ziele jeweils stochastisch unabhängig und gleichverteilt auf der Kreislinie liegen. Die damit verbundene Zielsetzung ist es, die Reihenfolge der angefahrenen Ziele so zu gestalten, dass die insgesamt notwendige Länge der Rundreise minimal wird. Als Kriterium für die Güte eines Algorithmus wird die durchschnittliche Schrittweite zwischen zwei nacheinander besuchten Zielen verwendet. Diese Problemstellung wird in zwei Varianten, nämlich einmal ohne die Möglichkeit eines Richtungswechsels und einmal mit erlaubten Richtungswechseln untersucht. Es wird dabei garantiert, dass dem Online-Algorithmus zu jedem Zeitpunkt eine feste Anzahl von unbearbeiteten Zielen zur Auswahl zur Verfügung stehen. Anschließend wird für jede solche feste Größe des Informationsvorlaufs das Verhalten der durchschnittlichen Schrittweite ermittelt. Durch das sukzessive Erhöhen des Informationsvorlaufs kann der Übergang von der Online-Optimierung, mit jeweils einem direkt zu bearbeitenden Ziel, zur Offline-Bearbeitung simuliert werden und mit den dabei gewonnenen Ergebnissen wird erkennbar, welchen Nutzen die Steigerung des Informationsvorlaufs hat.In standard optimisation theory all data of an optimisation problem are known when the calculation starts. This situation is denoted by the term Offline-Optimisation. In practice the usual situation is, that several decisions have to be made when only some and not all data are available. The optimisation of problems of this type is called Online-Optimisation. The aim of Online-Optimisation is to make all decisions in such a way, that the complete result becomes best possible. Naturally, during the optimisation, the incomplete information about the data leads to some suboptimal decisions and so to a suboptimal result in comparison to to the result won by an Offline-Optimisation. This thesis demonstrates for one special problem type how improvements on the available data for the Online-Algorithm change the quality of the results. The first part gives an introduction to online optimisation and presents some established problems and algorithms to solve them with special emphasis on the concept of competitivity. This is a Worst-Case-Comparison between the quality of results by the Online-Algorithm and the Offline-Optimisation. The second part presents the concept of lookahead. This is used as a measure for the information which an Online-Algorithm has when it makes the single decisions. In part three, the main part of the thesis, the focus goes on the specific problem of a travelling salesman tour on the circle. It includes, that the traveller has to visit a number of points on the circle (which are distributed independently and uniformly). The goal of the traveller is to minimize the step size between two points in the resulting tour. To do this he always chooses, in any moment when one of the sequentially incoming requests becomes known, one of the known points but still unvisited points. For the analysis the traveller gets the guarantee that he always has a constant number of requests to choose as his next point. Then for every such number the average step size is empirically determined. By successively increasing this information it is possible to simulate the changeover between the minimal Online-Optimisation, with only data about one request available, to the Offline-Optimisation, with the data of all requests available