Optimal route planning under uncertainty
Evdokia Nikolova, Matthew Brand, David R. Karger · 2006
We present new complexity results and efcient algorithms for optimal route planning in the presence of uncertainty. We employ a decision theoretic framework for dening the op-timal route: for a given source S and destination T in the graph, we seek an ST-path of lowest expected cost where the edge travel times are random variables and the cost is a nonlinear function of total travel time. Although this is a natural model for route-planning on real-world road net-works, results are sparse due to the analytic difculty of nd-ing closed form expressions for the expected cost (Fan, Kal-aba & Moore), as well as the computational/combinatorial difculty of efciently nding an optimal path which mini-mizes the expected cost. We identify a family of appropri-ate cost models and travel time distributions that are closed under convolution and physically valid. We obtain hardness results for routing problems with a given start time and cost functions with a global minimum, in a variety of determin-istic and stochastic settings. In general the global cost is not separable into edge costs, precluding classic shortest-path ap-proaches. However, using partial minimization techniques, we exhibit an efcient solution via dynamic programming with low polynomial complexity.