Das zu Grunde liegende mathematische Modell ist eine Erweiterung des bekannten Tourenplanungsproblems mit Zeitfenstern. Der neue Aspekt sind Kopplungsbedingungen innerhalb der Zeitfenster. Für diese neue Problemklasse führen wir die Bezeichnung Tourenplanungsproblem mit gekoppelten Zeitfenstern ein. IOSANA ist damit zugleich ein erster Anwendungsfall eines derartigen Modells mit gekoppelten Zeitfenstern. Instanzen dieses Problems sind theoretisch (im Sinne der Komplexitätstheorie) wie auch praktisch schwer zu lösen. Zur Lösung entwickeln und vergleichen wir daher verschiedene primale und duale Verfahren.
Auf der primalen Seite erweitern wir bekannte Heuristiken (sogenannte Greedy-Verfahren) zunächst um Aspekte der Kopplung von Zeitfenstern. Der nächste naheliegende Schritt ist die Parametrisierung der Auswahlfunktion, welche die Suchrichtung der Heuristik steuert. Zur Bestimmung "guter" Parameterwerte verwenden wir unter anderem Improving Hit-and-Run, ein zufallsbasiertes Verfahren der Globalen Optimierung.
Da es sich bei IOSANA um ein ganzzahliges lineares Programm handelt, lassen sich Branch-and-Cut Verfahren einsetzen, um untere Schranken für die Anzahl der eingesetzten Busse zu erhalten. Zur Verbesserung dieser Schranken untersuchen wir Möglichkeiten, die Modellformulierung zu verschärfen. Als besonders wirksam stellt sich die Reformulierung als Set-Partitioning-Problem heraus, wodurch jedoch die Zulässigkeit verloren geht.
Wir stellen die Resultate der in dieser Arbeit entwickelten Verfahren anhand verschiedener zufällig generierter und realer Instanzen vor. Reale Datensätze aus fünf verschiedenen deutschen Landkreisen wurden von unserem Projektpartner BPI-Consult zur Verfügung gestellt. Unsere Lösungen vergleichen wir mit dem Status-Quo in den jeweiligen Landkreisen.
Eine Einsparung von 10-30 Prozent der Fahrzeugflotte ist durch den Einsatz der integrierten Optimierung möglich. Jeder eingesparte Bus ist in etwa 30.000 Euro pro Jahr wert. Pro Landkreis errechnen sich so Einsparungen von bis zu 1,4 Mio. Euro jährlich. Rechnet man dieses auf alle 323 Landkreise Deutschlands hoch, so ergeben sich Einsparungen von bis zu 300 Mio. Euro an jährlichen Zuschüssen der Landkreise für die Schülerbeförderung im ÖPNV.
The underlying mathematical model turns out to be an extension of the well-known vehicle routing problem with time windows (VRPTW). The new aspect are coupling constraints among the time windows. For this new class of problems we propose the notion vehicle routing problem with coupled time windows (VRPCTW). This problem is theoretically (in the sense of complexity theory) as well as practically (for large real-world instances) difficult to solve. For its solution we develop and compare different primal and dual algorithms.
On the primal side we first extend known heuristic methods (so-called greedy algorithms) to aspects of coupled time windows. The next related step is a parameterization of the scoring function which takes control of the search direction within the heuristic. For the computation of "good" parameters we use (among others) improving hit-and-run, a randomized method from the field of Global Optimization.
Since IOSANA is formulated as an integer linear program branch-and-cut algorithms can be used to derive lower bounds on the number of deployed vehicles. To improve the so derived lower bounds we present a bundle of different techniques (preprocessing, lifting, and cutting planes) to strengthen the LP relaxation. A reformulation as a set partitioning problem turns out to be very useful in this respect, but at the price of losing feasibility.
We present results of the different algorithms of this thesis using various randomly generated and real-world instances. Real-world data sets from five different German counties were provided by our project partner BPI-Consult. We compare our solutions to the respective status quo of the counties.
Reductions of 10-30% in the number of vehicles are possible by the integrated optimization. A single bus yields already savings of about 30,000 Euro per year. For the entire county this might add up to 1.4 million Euro per year. Extrapolated to all 323 of Germany's counties this would yield up to 300 million Euro of saved public money for the transport of pupils.
40.50 € | ||
only 1 in stock |