Dynamic flow problems arising from traffic planning
The subject of this work is the solution of four classes of combinatorial optimization problems arising from traffic planning applications. To this end, we use algorithms and techniques from the field of mixed-integer programming, tailoring them to the specific problem classes. The robust shortest path problem is a generalization of the famous shortest path problem to a scenario in which the travel times through a given network are subject to uncertainty. The air-to-air refueling problem arises in the context of commercial trans-continental flights. A special feature of this problem is the nonlinearity with respect to the fuel consumption of the feeder aircraft. We address this issue by containing the nonlinearity in a combinatorial subproblem. The time-dependent TSP is a generalization of the notorious traveling salesman problem to scenarios in which the travel times are subject to change over time, introducing a temporal dynamic. Finally we study the Aircraft Landing Problem, a large-scale optimization problem where a large amount of domain constraints --- scheduling of landing times and consistent runway assignments --- have to be satisfied.
Column Generation is a subject of paramount importance for the solution of large-scale problem instances. The technique consists of generating problem variables one after another based on the predicted reduction of the objective function value, producing a provably optimal solution using a fraction of the whole set of problem variables, significantly reducing computational overhead. Modern column generation variants such as dual stabilization methods allow to control the generation of variables in such a way as to significantly increase the speed of convergence. Further techniques include the usage of cutting planes, tightening the outer approximations of the polyhedra of feasible integral points, as well as branching rules and priorities supporting existing codes and primal heuristics used to find feasible solutions. For each problem class we begin by settling its computational complexity, discussing approximation methods where appropriate. We proceed to derive exact solution algorithms based on mixed-integer programming formulations of the problem classes. To evaluate different solution techniques we perform a series of computational experiments with both real-world and synthetic data. Our work increases the scale of tractable problem instances dramatically, decreasing computational time by orders of magnitude.
In dieser Arbeit betrachten wir vier Klassen kombinatorische Optimierungsprobleme aus dem Bereich der Verkehrsplanung. Um diese zu lösen verwenden wir Algorithmen und Techniken aus dem Bereich der gemischt-ganzzahligen Optimierung, welche wir für die spezifischen Problemklassen anpassen. Das robuste Kürzeste-Wege Problem ist eine Verallgemeinerung des berühmten Kürzeste-Wege Problems auf ein Szenario in dem die Fahrzeiten durch ein Netzwerk mit Unsicherheiten behaftet sind. Das Luftbetankungsproblem entsteht im Kontext des kommerziellen transatlantischen Flugbetriebs. Eine Besonderheit dieses Prolems ist die Nichtlinearität bezüglich des Treibstoffverbrauchs der Tankflugzeuge. Wir behandeln dieses Problem dadurch, dass wir die Nichtlinearität in ein kombinatorisches Subproblem verlagern. Das zeitabhängige TSP ist eine Verallgemeinerung des TSP auf eine Situation, in der sich die Fahrzeiten über Planungshorizont verändern. Als letztes betrachten wir das Aircraft Landing Problem, bei dem eine große Anzahl spezifischer Nebenbedingungen --- Zur Lösung von großen Probleminstanzen ist die Technik der Spaltengenerierung von außerordentlicher Bedeutung. Die Technik besteht darin, Problemvariablen nacheinander basierend auf einer vorhergesagten Reduktion des Zielfunktionswerts zu erzeugen. Es ist dadurch möglich, eine beweisbar optimale Lösung zu berechnen, dabei jedoch nur einen Bruchteil der Gesamtmenge der Problemvariablen zu verwenden und die Rechenzeit deutlich zu reduzieren. Moderne Varianten der Spaltengenerierung, wie beispielsweise Techniken zur dualen Stabilisierung können dabei verwendet werden, um die Geschwindigkeit der Konvergenz zu erhöhen. Weitere Techniken sind die Erzeugung von Schnittebenen, also das Hinzufügen weiterer zulässiger Ungleichungen, um die äußere Approximation der zulässigen Menge zu verbessern, sowie Branching-Regeln und -Prioritäten um existierende Lösungsverfahren zu verbessern und Primalheuristiken zum Finden zulässiger Lösungen. Wir beginnen bei jeder Problemklasse damit, ihre Komplexität zu klären und bei Bedarf Algorithmen zur Approximation anzugeben. Wir fahren damit fort, für die Problemklassen exakte Algorithmen basierend auf Techniken der gemischt-ganzzahligen Optimierung herzuleiten. Wir werten dabei verschiedene Lösungsansätze durch rechnergestützte Experimente basierend auf echten und synthetischen Daten aus. Unsere Arbeit verschiebt die Größe der praktisch lösbaren Instanzen dramatisch und senkt benötigte Rechenzeiten enorm.
die konsistente Vergabe von Ankunftszeitpunkten sowie Landebahnen --- erfüllt werden müssen.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
