Optimal Route Planning Under Uncertainty

Download Now Date Added: Jan 2011
Format: PDF

The authors present new complexity results and efficient algorithms for optimal route planning in the presence of uncertainty. They employ a decision theoretic framework for defining the optimal route: for a given source S and destination T in the graph, the authors 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 networks, results are sparse due to the analytic difficulty of finding closed form expressions for the expected cost (Fan, Kalaba & Moore), as well as the computational/combinatorial difficulty of efficiently finding an optimal path which minimizes the expected cost.