A Chance-Constrained Two-Echelon Vehicle Routing Problem with Stochastic Demands

Natasja Sluijk (Corresponding author), Alexandre Florio, Joris Kinable, Nico P. Dellaert, Tom van Woensel

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
124 Downloads (Pure)


Two-echelon distribution systems are often considered in city logistics to maintain economies of scale and satisfy the emission zone requirements in the cities. In this work, we formulate the two-echelon vehicle routing problem with stochastic demands as a chance-constrained stochastic optimization problem, where the total demand of the customers in each second-echelon route should fit within the second-echelon vehicle capacity with a high probability. We propose two efficient solution procedures based on column generation. Key to the efficiency of these procedures is the underlying labeling algorithm to generate new columns. We propose a novel labeling algorithm based on simultaneous construction of second-echelon routes and a labeling algorithm that builds second-echelon routes sequentially. To further enhance the performance of the solution procedure, we use statistical inference tests to ensure that the chance constraints are met. We reduce the number of customer combinations for which the chance constraint needs to be verified by imposing feasibility bounds on the stochastic customer demands. With these bounds, the runtimes of the labeling algorithms are reduced significantly. The novel labeling algorithm, statistical inference, and feasibility bounds can also be applied to dependent, correlated, and data-driven (scenario-based) demand distributions. Finally, we show the value of the stochastic formulation in terms of improved solution cost and guaranteed feasibility of second-echelon routes.
Original languageEnglish
Pages (from-to)252-272
Number of pages21
JournalTransportation Science
Issue number1
Early online date17 Aug 2022
Publication statusPublished - Jan 2023


  • column generation
  • correlated demands
  • feasibility bounds
  • multilabel


Dive into the research topics of 'A Chance-Constrained Two-Echelon Vehicle Routing Problem with Stochastic Demands'. Together they form a unique fingerprint.

Cite this