TY - JOUR

T1 - Least possible time paths in stochastic, time-varying networks

AU - Miller-Hooks, Elise D.

AU - Mahmassani, Hani S.

N1 - Funding Information:
The authors are grateful to Dr Athanasios Ziliaskopoulos, presently at Northwestern University, for many useful discussions in the general area of multidimensional optimum path algorithm implementation and for the use of his random network generator (upon which the generator used in this research was based). The authors also appreciate the comments of an anonymous referee, which helped clarify several aspects of the presentation. Partial funding for the work reported herein came from a research contract through the Amarillo National Research Center for Plutonium, as well as through the Southwest University Transportation Center.

PY - 1998/12

Y1 - 1998/12

N2 - 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.

AB - 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.

KW - Shortest paths

KW - Stochastic dynamic networks

UR - http://www.scopus.com/inward/record.url?scp=0032358743&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032358743&partnerID=8YFLogxK

U2 - 10.1016/S0305-0548(98)00027-6

DO - 10.1016/S0305-0548(98)00027-6

M3 - Article

AN - SCOPUS:0032358743

VL - 25

SP - 1107

EP - 1125

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 12

ER -