Least possible time paths in stochastic, time-varying networks

Elise D. Miller-Hooks, Hani S. Mahmassani*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

91 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1107-1125
Number of pages19
JournalComputers and Operations Research
Volume25
Issue number12
DOIs
StatePublished - Dec 1998

Keywords

  • Shortest paths
  • Stochastic dynamic networks

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Least possible time paths in stochastic, time-varying networks'. Together they form a unique fingerprint.

Cite this