####
Improved Results for Route Planning in Stochastic Transportation Networks

In the bus network problem, the goal is to generate a plan for getting
from point X to point Y within a city using buses in the smallest
expected time. Because bus arrival times are not determined by a fixed
schedule but instead may be random, the problem requires more than
standard shortest path techniques. In recent work, Datar and Ranade
provide algorithms in the case where bus arrivals are assumed to be
independent and exponentially distributed.
We offer solutions to two important generalizations of the problem,
answering open questions posed by Datar and Ranade. First, we provide
a polynomial time algorithm for a much wider class of arrival
distributions, namely those with increasing failure rate. This class
includes not only exponential distributions but also uniform, normal,
and gamma distributions. Second, in the case where bus arrival times
are independent and geometric discrete random variables, we provide an
algorithm for transportation networks of buses and trains, where
trains run according to a fixed schedule.