Vehicle routing problems with time windows and stochastic travel and service times : Models and algorithm

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

229 Scopus Citations
View graph of relations


  • Xiangyong Li
  • Peng Tian
  • Stephen C.H. Leung

Related Research Unit(s)


Original languageEnglish
Pages (from-to)137-145
Journal / PublicationInternational Journal of Production Economics
Issue number1
Publication statusPublished - May 2010


This paper studies a version of stochastic vehicle routing problems, in which travel and service times are stochastic, and a time window constraint is associated with each customer. This problem is originally formulated as a chance constrained programming model and a stochastic programming model with recourse in terms of different optimization criteria. To efficiently solve these two models, a heuristic based on tabu search, which takes into account the stochastic nature of this problem, is then proposed. Finally, some testing instances with different properties are established to investigate the algorithmic performance, and the computational results are then reported. © 2010 Elsevier B.V. All rights reserved.

Research Area(s)

  • Stochastic service time, Stochastic travel time, Tabu search, Time windows, Vehicle routing problem