Stochastic Routing
We are developing optimal routing algorithms for networks where the costs vary probabilistically.
Background & Objective: We study real-world networks such as traffic, communications, and logistics. In these settings, advancing a link is not a sure thing: The cost, time, and success will vary probabilistically. Classical routing algorithms can yield catastrophically bad outcomes. We are developing methods to optimize various measures of performance and bound the probability of failure.
Technical Discussion: We optimize expected utility where the user's utility is some nonlinear function of the realized total travel time or cost. We have proven that some such optimizations are NP-hard and/or inapproximable. For other useful cases we have found very efficient algorithms and approximation schemes. Two examples that are especially suitable for current car-navi hardware: Choosing a route that maximizes the probability of arriving before a deadline, and choosing a policy that minimizes time and avoids jams when the congestion state of the whole network changes stochastically.
Outside Collaborations: Jan Kara, Charles University (Prague).
Future Direction: We are now looking at wireless transmission problems where the link cost distributions are extremely heavy-tailed.
Contact: Matthew Brand
| Technical Reports: | |
| Optimal Route Planning under Uncertainty | |
Technology Area: Algorithms
Modification Date: September 12, 2007
