A Chance-Constrained Two-Echelon Vehicle Routing Problem with Stochastic Demands
研究了城市物流中两级配送系统的车辆路径问题，在随机需求下用机会约束保证第二级车辆容量以高概率满足，提出了基于列生成的高效算法，并利用统计推断和可行性边界提升效率。
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. Funding: This work was funded by the Dutch Research Council (NWO) DAREFUL project [Grant 629.002.211] and was carried out on the Dutch national e-infrastructure with the support of SURF Cooperative. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2022.1162 .