The computation of shortest paths in weighted and directed networks has been subject to research for more than five decades by now, and it has never lost its relevance in up-to-date applications. Recently, there has been increasing interest in incorporating time-dependencies into the modeling of the network. This is motivated by a large field of applications, such as intelligent transportation systems, internet routing, multi-agent-systems and networked control systems. The topic of this thesis is the computation of optimal paths in time-dependent networks. Although the time-independent optimal path problem is polynomially solvable, the time-dependent optimal path problem is NP-hard if the cost is different from the travel time, or the travel time functions do not fulfill the FIFO-property. After providing some background information on the physical modeling of travel times and travel costs in the time-dependent road network we formally introduce the mathematical model of time-dependent networks which is used in this thesis. In this model, we allow negative cost functions and we incorporate arrival time constraints as well as waiting time constraints into the problem description. Based on the theory of dynamic programming, we prove the existence of optimal paths and the lower semicontinuity of the optimal value function both for the optimal path problem in which all travel time and cost functions are precisely known and for the robust shortest path problem. We identify necessary and sufficient conditions for the continuity of the optimal value function and discuss the cases of piecewise analytic and piecewise linear functions. In particular, under the assumption that all cost and constraint functions are piecewise analytic, we prove the following assertions: The optimal value function is directionally differentiable, the set of points in which the optimal value function is not differentiable is discrete and the optimal value function is analytic in an open neighborhood of any other point. We also carry out a complexity analysis for the case in which all travel time, cost and constraint functions are piecewise linear. We then consider a problem setting in which the waiting time constraints are formulated in such a way that admissible paths are constrained to stay close to fastest paths (which are computable in polynomial time in FIFO-networks). Assuming that waiting is forbidden everywhere in the network, we discuss the impact of the arrival time constraints on the complexity of the time-dependent optimal path problem with fixed departure time. We develop two algorithms, which efficiently solve the problem of computing the optimal value function and the corresponding optimal paths in time-dependent networks. The first approach is a generalization of a class of previously published solution methods (decreasing order of time methods) to heuristic search. In the second approach, assuming that the time-dependent network has the FIFO-property, we generate an admissible initial solution in polynomial time and then iteratively and monotonically approximate the optimal value function. Since an upper bound on the error of the current iterate is maintained throughout the algorithm, this method allows a trade-off between computation time and accuracy of the found solution. Finally, we demonstrate the application of the above theoretical results and algorithmical solutions in a case study in the time-dependent road network of Ingolstadt.     «

The computation of shortest paths in weighted and directed networks has been subject to research for more than five decades by now, and it has never lost its relevance in up-to-date applications. Recently, there has been increasing interest in incorporating time-dependencies into the modeling of the network. This is motivated by a large field of applications, such as intelligent transportation systems, internet routing, multi-agent-systems and networked control systems. The topic of this thes...     »

Die Berechnung kürzester Wege in gewichteten und gerichteten Netzwerken wird bereits seit über fünf Jahrzehnten erforscht und hat dabei nie ihre Relevanz in aktuellen Anwendungen verloren. Seit einiger Zeit besteht ein verstärktes Interesse darin, Zeitabhängigkeiten in die Netzwerkbeschreibung miteinzubeziehen. Dieses Interesse begründet sich in einem weiten Anwendungsfeld, das unter anderem aus intelligenten Verkehrssystemen, Internet Routing, Multi-Agenten-Systemen und Systemen mit vernetzter Kontroll- und Regelstruktur besteht. Das Thema dieser Dissertation ist die Berechnung optimaler Wege in zeitabhängigen Netzwerken. Obwohl das zeitunabhängige optimale Wege Problem polynomiell lösbar ist, ist das zeitabhängige optimale Wege Problem NP-schwer falls die Kosten verschieden von der Reisezeit sind, oder die Reisezeitfunktionen nicht die FIFO-Eigenschaft erfüllen. Nach der Bereitstellung einiger Hintergrundinformationen über die physikalische Modellierung von Reisezeiten und Reisekosten in zeitabhängigen Straßennetzwerken führen wir formell das mathematische Modell zeitabhängiger Netzwerke ein, das wir in dieser Dissertation verwenden. In diesem Modell lassen wir auch negative Kostenfunktionen zu und beziehen Ankunftszeitbeschränkungen und Wartezeitbeschränkungen in die Problembeschreibung mit ein. Basierend auf der Theorie der dynamischen Programmierung beweisen wir die Existenz optimaler Wege und die Unterhalbstetigkeit der Optimalwertfunktion, sowohl für das optimale Wege Problem in dem alle Reisezeit- und Kostenfunktionen präzise bekannt sind, als auch für das robuste optimale Wege Problem. Wir identifizieren notwendige und hinreichende Bedingungen für die Stetigkeit der Optimalwertfunktion und diskutieren die Fälle stückweise analytischer und stückweise linearer Funktionen. Unter der Voraussetzung, dass alle Reisezeit-, Kosten- und Beschränkungsfunktionen stückweise analytisch sind, beweisen wir, dass die Optimalwertfunktion richtungsdifferenzierbar ist, dass die Menge der Punkte in denen die Optimalwertfunktion nicht differenzierbar ist eine diskrete Menge ist und dass die Optimalwertfunktion analytisch in der Umgebung jedes anderen Punktes ist. Des weiteren führen wir für den Fall, dass alle Reisezeit-, Kosten- und Beschränkungsfunktionen stückweise linear sind, eine Komplexitätsanalyse durch. Wir betrachten dann eine Problemstellung in der die Wartezeitbeschränkungen derart formuliert sind, dass zulässige Wege nahe bei schnellsten Wegen liegen (welche in FIFO-Netzwerken in polynomieller Zeit berechnet werden können). Unter der Voraussetzung, dass Warten überall im Netzwerk verboten ist, diskutieren wir die Auswirkung der Ankunftszeitbeschränkungen auf die Komplexität des zeitabhängigen optimale Wege Problems mit fester Abfahrtszeit. Wir entwickeln zwei Algorithmen, unter Verwendung derer sich das Problem der Berechnung der Optimalwertfunktion in zeitabhängigen Netzwerken effizient lösen lässt. Der erste Ansatz ist eine Verallgemeinerung kürzlich veröffentlichter Methoden, welche die Optimalwertfunktion rückwärts in der Zeit berechnen, zu einem heuristischen Suchalgorithmus. Für den zweiten Ansatz nehmen wir an, dass das zeitabhängige Netzwerk die FIFO-Eigenschaft erfüllt, berechnen eine zulässige Startlösung in polynomieller Zeit und approximieren dann in iterativer und monotoner Weise die Optimalwertfunktion. Da eine obere Schranke des Fehlers der derzeitigen Iterierten während des Ablaufs des Algorithmus aufrecht erhalten wird, erlaubt diese Methode einen Kompromiss zwischen der Rechenzeit und der Genauigkeit der gefundenen Lösung. Schließlich veranschaulichen wir die Verwendbarkeit der theoretischen Resultate und der algorithmischen Lösungsverfahren in einer Fallstudie im zeitabhängigen Straßennetzwerk von Ingolstadt.      «

Die Berechnung kürzester Wege in gewichteten und gerichteten Netzwerken wird bereits seit über fünf Jahrzehnten erforscht und hat dabei nie ihre Relevanz in aktuellen Anwendungen verloren. Seit einiger Zeit besteht ein verstärktes Interesse darin, Zeitabhängigkeiten in die Netzwerkbeschreibung miteinzubeziehen. Dieses Interesse begründet sich in einem weiten Anwendungsfeld, das unter anderem aus intelligenten Verkehrssystemen, Internet Routing, Multi-Agenten-Systemen und Systemen mit vernetz...     »