A Stochastic Vehicle Routing Problem with Travel Time Uncertainty: Trade-Off Between Cost and Customer Service

Junlong Zhang, Hing Keung William Lam, Bi Yu Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

53 Citations (Scopus)


On-time shipment delivery is critical for just-in-time production and quick response logistics. Due to uncertainties in travel and service times, on-time arrival probability of vehicles at customer locations can not be ensured. Therefore, on-time shipment delivery is a challenging job for carriers in congested road networks. In this paper, such on-time shipment delivery problems are formulated as a stochastic vehicle routing problem with soft time windows under travel and service time uncertainties. A new stochastic programming model is proposed to minimize carrier's total cost, while guaranteeing a minimum on-time arrival probability at each customer location. The aim of this model is to find a good trade-off between carrier's total cost and customer service level. To solve the proposed model, an iterated tabu search heuristic algorithm was developed, incorporating a route reduction mechanism. A discrete approximation method is proposed for generating arrival time distributions of vehicles in the presence of time windows. Several numerical examples were conducted to demonstrate the applicability of the proposed model and solution algorithm.
Original languageEnglish
Pages (from-to)471-496
Number of pages26
JournalNetworks and Spatial Economics
Issue number4
Publication statusPublished - 1 Dec 2013


  • Customer service
  • Discrete approximation
  • Stochastic programming
  • Tabu search
  • Time window
  • Vehicle routing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Artificial Intelligence
  • Software

Cite this