Integer Optimization for Disjoint Trajectories: Complexity Results, Algorithms and Resilience to Uncertainty
Ganzzahlige Optimierung für Disjunkte Trajektorien: Komplexitätsresultate, Algorithmen und Resilienz bei Unsicherheiten
Creators: name: Hoch, Benno
Publisher: name: Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Year: 2024

description: The task of joint optimization of trajectories, i.e., paths over time, arises in contexts where commodities use shared network resources. Separation constraints between commodities render the often challenging continuous trajectory optimization problem even harder, especially if only a subset of multiple possible separation conditions have to be met. In this case discrete decisions which separation conditions to fulfill are added to the task. For real world applications like arrival planning at airports, this can lead authorities to solve the resulting highly complex discrete-continuous optimization problems sequentially or with restricted planning space. In this thesis we develop a novel model and solution algorithms for the disjoint trajectories problem to lift unused optimization potentials resulting from those restrictions and to provide globally optimal solutions. Aiming at giving a comprehensive picture for various facets of our model, we cover a study of properties related to computational complexity, as well as designing solution algorithms and dynamic discretization techniques for the available planning space. First, we study a basic combinatorial problem formulation on an undirected base-network with unit traversal times. We define trajectories to be disjoint if they never meet. For the theoretical considerations, we further require that trajectories satisfy a non-stop condition, which disallows waiting at vertices or along arcs. We call this the non-stop disjoint trajectories problem. Variants appear, e.g., in bufferless packet routing or when disjoint aircraft trajectories shall be determined. The model we provide can be interpreted as an extension to the k-disjoint paths problem, for which a plethora of (in-)tractability results are known. In this thesis, we study the computational complexity for feasibility and optimization versions of the non-stop disjoint trajectories problem. Our results focus on three graph classes that are frequently used where space and time are discretized simultaneously: the path, the grid, and the mesh. If all commodities have a common release date we show that feasibility can be decided in polynomial time on paths. For the unbounded mesh and unit-costs, a constructive proof to determine optimal trajectories is presented. In contrast, if commodities have individual release intervals and turns are forbidden, we prove that deciding feasibility is NP-complete even for the path. For the mesh with arbitrary edge-costs, individual release dates, and turning abilities of commodities restricted to at most 90° turns, we show that optimization and approximation are not fixed-parameter tractable. Second, we examine solution routines for a generalized version on a directed graph as base-network, arbitrary traversal times on the arcs, waiting allowed, and generalized separation constraints. On the corresponding time-expanded network we formulate an integer linear program which scales with the size of the time-expanded network. We overcome prohibitively large instance sizes by developing an adaptive- refinement algorithm that re-optimizes in neighborhoods of globally optimal solutions that are determined in a coarse discretization. To enable the solution of more detailed instances we further detail a way to integrate the method into a rolling horizon approach. As not only the integer program itself, but already the representation of a complex, fully dimensional planning space can become prohibitively large to store, we develop a highly flexible representation of the spatial planning environment. To cope with imperfect release information we take on the paradigm of strict robust optimization. To obtain trajectories that are feasible under all possible realizations of release times, we introduce a concept for reference trajectories. Those are designed to allow the commodities to follow them, regardless of the release date (within a given set of possible release times), and still maintain all necessary separation conditions. We apply our models and solution routines to the integrated trajectory optimization and runway scheduling problem in the surrounding of airports. For this application, we further develop a method for conflict detection under uncertain release information. Conflict detection methods allow us to use a feasibility cut approach in the solution process of the integer programs, regardless of whether we consider perfect or uncertain information. Computational experiments with instances based on realistic data demonstrate the eﬀiciency of our method.
description: In der vorliegenden Arbeit ”Ganzzahlige Optimierung für Disjunkte Trajektorien: Komplexitätsresultate, Algorithmen und Resilienz bei Unsicherheiten” entwickeln und untersuchen wir das disjunkte Trajektorien Problem — eine Verallgemeinerung des bekannten k-disjoint Paths Problems. Mehrere Trajektorien gleichzeitig zu optimieren ist eine Problemstellung, die in vielen Kontexten auftritt, wo sich ‘Güter’ Netzwerkressourcen teilen. Separationsbedingungen zwischen den Gütern machen das ohnehin komplexe Problem kontinuierliche Trajektorien zu bestimmen noch herausfordernder. Dies gilt insbesondere dann, wenn nur eine Teilmenge von mehreren möglichen Separationsbedingungen erfüllt werden muss und somit zusätzlich diskrete Entscheidungen involviert sind. In Anwendungen wie der Anflugplanung an Flughäfen kann dies dazu führen, dass die daraus resultierenden, hochkomplexen diskret-kontinuierlichen Optimierungsprobleme sequentiell oder mit eingeschränktem Planungsraum gelöst werden. Um die aus diesen Restriktionen resultierenden ungenutzten Optimierungspotenziale zu heben, und global optimale Lösungen bereitzustellen, werden in dieser Arbeit ein neues Modell und Lösungsalgorithmen für das disjunkte Trajektorien Problem entwickelt und untersucht. Mit dem Ziel, ein umfassendes Bild der verschiedenen Facetten unseres Modells zu vermitteln, befassen wir uns mit Fragestellungen zur Computational Complexity, sowie mit der Entwicklung von Lösungsalgorithmen und dynamischen Diskretisierungstechniken für den verfügbaren Planungsraum. Zunächst untersuchen wir eine grundlegende Formulierung als kombinatorisches Problem auf einem ungerichteten Netzwerk mit einheits Traversalzeiten auf den Kanten. Wir definieren Trajektorien als disjunkt, wenn sie sich niemals treffen. Für die theoretischen Überlegungen verlangen wir außerdem, dass die Trajektorien eine Non-Stop-Bedingung erfüllen, die das Warten an Knoten oder entlang von Kanten verbietet. Wir nennen dies das Non-Stop Disjoint Trajectories Problem. Varianten davon treten z.B. beim Bufferless Routing auf, oder wenn disjunkte Flugbahnen von Flugzeugen bestimmt werden sollen. Das von uns vorgestellte Modell kann als Erweiterung des k-disjoint Paths-Problems interpretiert werden, für das eine Fülle von (Nicht-)Tractability-Ergebnissen bekannt sind. Im ersten Teil dieser Arbeit untersuchen wir die Computational Complexity für Zulässigkeits- und Optimierungsversionen des Non-Stop Disjoint Trajectories Problems. Unsere Ergebnisse konzentrieren dabei sich auf drei Graphenklassen die häufig verwendet werden, wenn Raum und Zeit gleichzeitig diskretisiert werden: der Pfad, das Gitter und das Mesh. Für den Fall, dass alle Güter gleichzeitig im Netzwerk releast werden, zeigen wir, dass die Zulässigkeit auf dem Pfad in polynomieller Zeit entschieden werden kann. Für das unbeschränkte Mesh und Einheitskosten wird ein konstruktiver Beweis für optimale Trajektorien vorgestellt. Im Gegensatz dazu zeigen wir für den Fall, dass Güter individuelle Release-Intervalle haben und Wenden verboten ist, dass selbst das Zulässigkeitsproblem für den Pfad NP-vollständig ist. Für das Mesh mit beliebigen Kantenkosten, individuellen Release-Zeiten und einer auf höchstens 90° beschränkten Wendefähigkeit von Gütern zeigen wir, dass weder Optimierung noch Approximation fixed-parameter tractable sind. Anschließend untersuchen wir Lösungsalgorithmen für eine allgemeinere Version auf einem gerichteten Netzwerk, beliebige Traversalzeiten auf den Kanten, der Möglichkeit zu Warten und verallgemeinerten Separationsbedingungen. Für das entsprechende zeit-expandierte Netzwerk formulieren wir ein ganzzahliges lineares Programm, das mit der Größe des zeit-expandierten Netzwerks skaliert. Wir überwinden unhändelbar große Instanzen, indem wir einen adaptiven Verfeinerungsalgorithmus entwickeln, der in Nachbarschaften von global optimalen Lösungen, die für eine groben Diskretisierung bestimmt wurden, re-optimiert. Zur Lösung detaillierterer Instanzen integrieren wir diesen Ansatz in ein rolling-horizon Verfahren. Da nicht nur das ganzzahlige Programm selbst, sondern auch die Darstellung eines komplexen, voll dimensionalen Planungsraumes sehr groß werden kann, entwickeln wir zusätzlich eine hochflexible Darstellung des Planungsraumes. Im Rahmen von strikt robuster Optimierung betrachten wir außerdem unvollkommenen Release-Informationen. Um Trajektorien zu bestimmten, die unter allen möglichen Realisierungen von Freigabezeiten machbar sind, führen wir das Konzept von Referenztrajektorien ein. Diese sind so konzipiert, dass die Güter ihnen unabhängig vom Release-Zeitpunkt (innerhalb einer vorgegebenen Menge möglicher Release-Zeiten) folgen können und dennoch alle notwendigen Separationsbedingungen einhalten. Wir testen unsere Modelle und Lösungsroutinen für die integrierte Optimierung von Trajektorien und Runway Schedulings in der Umgebung von Flughäfen. Für diese Anwendung entwickeln wir außerdem eine Methode zur Konfliktdetektion unter unsicheren Release-Zeiten, die es erlaubt, einen Feasiblity-Cut-Ansatz zur Lösung des ganzzahligen Programms nicht nur im Falle perfekter Informationen zu verwenden. Rechen-Experimente mit Instanzen, die auf realistischen Daten basieren, demonstrieren die Eﬀizienz der Methode.