Arriving on Time: Routing in a Stochastic Network


Wednesdays@NICO Seminar, Noon, November 28 2007, Chambers Hall, Lower Level

Prof. Marco Nie, Northwestern University


Routing in a stochastic network provides a general framework to deal with decision-making under uncertainty. In transportation, stochastic routing is used to provide predetermined optimal paths or adaptive en-route guidance. Often a routing strategy is considered optimal if it incurs the least expected travel time (LET). However, a LET path (or policy) may subject to high risks and therefore is not desirable to a risk averse traveler. For example, people tend to budget a large chunk of time for travel when they plan for important events (e.g., catch a flight). The key objective of routing in such a circumstance is to reduce the risk of running late rather than to minimize the expected travel time. In many cases, however, such risk averse behavior leads to excessively conservative time budgets. It is therefore necessary to find a way to both guarantee reliable on-time arrival and to avoid excessive waiting at the destination. This research addresses such risk averse behavior in routing under uncertainty. Specifically, we are concerned with the following instance of the stochastic routing: Determine the latest possible departure time and the associated path (or a routing policy) which ensures on-time arrival (i.e., arrive on time or earlier) at a given reliability. We provide a continuous, dynamic-programming-based formulation and a discrete solution algorithm which runs in polynomial time. We also present a multi-criteria shortest path algorithm to find predetermined optimal paths that guarantee a given probability of on-time arrival.