Least possible time paths in stochastic,time-varying networks

Selection of optimal routes for emergency response units, vehicles carrying hazardous material and individuals to and from various activities in congested city streets is vital to these systemsʹ performance. Travel times in congested transportation systems are time-varying quantities that are at best known a priori with uncertainty. Methodologies that recognize the inherent stochastic and time-varying nature of travel conditions are important in many of the above applications, motivating the need for efficient algorithms for determining optimal paths in networks where the arc costs are time-varying random quantities, and for considering trade-offs among various risk dimensions in the selection process. This paper presents two efficient procedures to find the paths that have the least possible time from any origin to a given destination in such networks. These algorithms provide a well-defined and efficiently-computed benchmark against which to evaluate paths obtained using heuristic procedures (that may consider other risk dimensions); in addition they can be used to solve subproblems that arise as components of more elaborate procedures. These problems are encountered in a variety of areas, including intelligent transportation systems (ITS), emergency response systems operations (medical, police, fire) and communication networks. In this paper, two computationally efficient algorithms are presented for determining the least possible time paths for all origins to a single destination in networks where the arc weights are discrete random variables whose probability distribution functions vary with time. The first algorithm determines the least possible time path from each node for each departure time interval, the least possible travel time and a lower bound on the associated probability of the occurrence of this travel time. The second algorithm determines up to k least possible time paths, the associated travel times and the corresponding probabilities of occurrence of the travel times (or a lower bound on this probability). No such efficient algorithms for determining least time paths in stochastic, time-varying networks exist in the literature.