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

Natasja Sluijk (), Alexandre M. Florio (), Joris Kinable (), Nico Dellaert () and Tom Van Woensel ()
Additional contact information
Natasja Sluijk: School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, Netherlands
Alexandre M. Florio: School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, Netherlands
Joris Kinable: School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, Netherlands; Supply Chain Optimization Technologies, Amazon, Seattle, Washington 98109
Nico Dellaert: School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, Netherlands
Tom Van Woensel: School of Industrial Engineering, Eindhoven University of Technology, 5600MB Eindhoven, Netherlands

Transportation Science, 2023, vol. 57, issue 1, 252-272

Abstract: 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.

Keywords: correlated demands; feasibility bounds; column generation; multilabel (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1162 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:1:p:252-272

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().