The Problem

The optimal path under uncertainty problem seeks a path between a given pair of vertices in a graph, having lowest expected cost where the edge travel times are random variables and the cost is a (non-linear) function of total travel time. It is a natural model for route-planning on real-world road networks.

Our Approach

The static stochastic route planning problem asks for optimal routes on a directed graph where travel times on the edges are random variables with fixed distributions. In this setting, one must optimize an objective that makes some tradeoff between the speediness (expected travel time) and reliability (variance) of a route. Optimizing one or the other, though quite tractable, makes little sense. Optimizing a linear combination of the two is another possibility, though it seems ad-hoc and not clearly motivated, interestingly it turns out to be a special case of our formulation.

Decision theory, the standard framework for making optimal plans and policies under uncertainty, expresses the trade-off between speediness and reliability through a utility or cost function C(.). In our setting C(t) assesses a reward or penalty for arriving at time t relative to a deadline. For example, a linear C(t) minimizes expected travel time; quadratic C(t) minimizes variance; the minimizer of their weighted sum takes a surprising form related to the cumulant generating function of the travel time distributions, however it cannot tell us when to set out. We give hardness results for a variety of stochastic route planning problems, with an emphasis on cost functions that value timeliness without time-wasting. E.g. ``What is the optimal start time and route for a given deadline?'' and ``Now that I am on the road, what is the optimal route for that deadline?'' Surprisingly, for some cost functions of interest, the former question is tractable while the latter is NP-hard.

This highlights the dependence of stochastic solutions on time. For example, imagine that we have a choice of two routes and only care to arrive at the destination before a given deadline. Maximizing the probability of doing so implies that C(t) is a step function. If we set out close to the deadline, a slower and highly variable route will actually be preferable to a faster and highly reliable route, because the less predictable route offers a greater chance of arriving on time. This is probably not a good model of driver values; choice of this cost function also implies that the optimal time to set out is the dawn of time and that if one sets out late, all routes are equally good.

We identify a family of appropriate cost models for drivers and uncertainty models for road networks. In a departure from the stochastic path-planning literature, these are closed under convolution, so that the expected cost of any one path can be computed analytically. We survey a range of stochastic route-planning problems, finding that some can be converted into classic Djikstra shortest-path.

Progress

We obtain hardness results for routing problems with a given start time and cost minima located finitely far from a deadline as well as cost functions with a unique global minimum, in both deterministic and stochastic settings. On the positive side, we identify a family of appropriate cost models and travel time distributions that are closed under convolution and physically valid. In general, the cost of a path is not separable into edge costs. For discretizations of the travel times we give a pseudopolynomial algorithm via dynamic programming and show that the usual technique of scaling cannot yield a polynomial approximation scheme. In contrast, certain (both discrete and continuous) routing problems with flexible start time can be reduced to the deterministic shortest path problem and therefore solved exactly and efficiently.

Future Work

A number of interesting open questions remain. For the case of static stochastic networks, in which edge distributions are fixed, we have yet to find efficient algorithms or prove hardness of finding the optimal path and optimal start time for general non-linear cost functions. Perhaps even more importantly, we would like to extend our analysis to the case of dynamic networks, where both topology and distributions change with time. Other open questions include comparing the optimal non-adaptive to the optimal adaptive solution, under both static and dynamic travel time distributions.

References:

[1] Matthew Brand, David Karger and Evdokia Nikolova. ``Optimal Paths under Uncertainty: The Case of Non-linear Objective." Work in progress, working draft available upon request.