Partial-route inequalities for the multi-vehicle routing problem with stochastic demands

Ola Jabali, Walter Rei, Michel Gendreau, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

37 Citations (SciVal)


This paper describes an exact algorithm for a variant of the vehicle routing problem in which customer demands to be collected are stochastic. Demands are revealed upon the vehicle arrival at customer locations. As a result, a vehicle may reach a customer and does not have sufficient capacity to collect the realized demand. Such a situation is referred to as a failure. In this paper the following recourse action is then applied when failure occurs: the vehicle returns to the depot to unload and resumes its planned route at the point of failure. The capacitated vehicle routing problem with stochastic demands (VRPSD) consists of minimizing the sum of the planned routes cost and of the expected recourse cost. The VRPSD is formulated as a two-stage stochastic programming model and solved by means of an integer L-shaped algorithm. This paper introduces three lower bounding functionals based on the generation of general partial routes, as well as an exact separation procedure to identify violated cuts. Extensive computational results confirm the effectiveness of the proposed algorithm, as measured by a substantial reduction in the number of feasible solutions that have to be explicitly eliminated. This translates into a higher proportion of instances solved to optimality, reduced optimality gaps, and lower computing times.

Original languageEnglish
Pages (from-to)121-136
Number of pages16
JournalDiscrete Applied Mathematics
Publication statusPublished - 20 Nov 2014


  • General partial routes
  • Integer L-shaped algorithm
  • Lower bounding functionals
  • Stochastic demand
  • Stochastic programming
  • Stochastic vehicle routing problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Partial-route inequalities for the multi-vehicle routing problem with stochastic demands'. Together they form a unique fingerprint.

Cite this