Reliable vehicle routing problem in stochastic networks with correlated travel times

Mojtaba Rajabi-Bahaabadi, Afshin Shariat-Mohaymany*, Mohsen Babaei, Daniele Vigo

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

16 Downloads (Pure)


This study is motivated by the fact that travel times on road networks are correlated. However, all existing studies on the vehicle routing problem share a common simplifying assumption that arc travel times are independently distributed. In this paper, we address a variant of the vehicle routing problem with soft time windows in which travel times are treated as correlated random variables. To this end, correlations among arc travel times are modeled by a variance–covariance matrix. We use a mathematical model in which penalties are incurred for early and late arrival at each customer (violation of time window constraints). A Max–Min ant colony system is hybridized with a tabu search algorithm to solve the model. Results show that ignorance of correlations among arc travel times can significantly lead to inefficient solutions to the vehicle routing problem in stochastic networks. We also conduct an exploratory analysis of real travel time data. The results of the analysis demonstrate that travel times are significantly correlated and the shifted log-normal distribution is an appropriate candidate for modeling travel time uncertainty.

Original languageEnglish
Pages (from-to)299-330
Number of pages32
JournalOperational Research
Issue number1
Early online date28 Jan 2019
Publication statusPublished - Mar 2021


  • Correlated travel times
  • Hybrid algorithm
  • Time windows
  • Vehicle routing problem


Dive into the research topics of 'Reliable vehicle routing problem in stochastic networks with correlated travel times'. Together they form a unique fingerprint.

Cite this