Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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 ...