Simulation-based method for finding minimum travel time budget paths in stochastic networks with correlated link times

Ali Zockaie, Yu M. Nie, Hani S. Mahmassani*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

31 Scopus citations


The aim of this study was to solve the minimum path travel time budget (MPTTB) problem, in which the travel time budget was the reliability index. This index was defined as the sum of the mean path travel time and the scaled standard deviation, which included the covariance matrix to consider correlation. Two existing solution methods in the literature, the outer approximation algorithm and Monte Carlo simulation method, were applied to solve the MPTTB problem. The former method approximated the hard nonlinear constraint of the MPTTB problem by a series of linear cuts generated iteratively and repeatedly solved a mixed integer program. The latter method, which was a simulation-based method, included two stages. The first stage founded a set of candidate paths, and the second stage generated the distribution of travel times for the existing paths in the candidate set. The numerical results for these two solution methods were conducted on the Chicago sketch network, and results showed that the methods found comparable solutions though they have respective advantages and drawbacks. Although the outer approximation algorithm demonstrated promising performance, it still relied on repeatedly solving a mixed integer program (subproblem)with a commercial solver, which could be a challenging task in its own right. The simulation-based method offers a good Plan B in the case in which other algorithms encounter difficulties.

Original languageEnglish (US)
Title of host publicationTransportation Research Record
PublisherNational Research Council
Number of pages9
ISBN (Electronic)9780309295611
StatePublished - 2014

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Mechanical Engineering


Dive into the research topics of 'Simulation-based method for finding minimum travel time budget paths in stochastic networks with correlated link times'. Together they form a unique fingerprint.

Cite this