计算机科学
车辆路径问题
贝叶斯概率
水准点(测量)
迭代函数
数学优化
运筹学
特征(语言学)
约束(计算机辅助设计)
封面(代数)
钥匙(锁)
布线(电子设计自动化)
人工智能
数学
工程类
计算机网络
数学分析
语言学
哲学
大地测量学
计算机安全
地理
机械工程
几何学
作者
Alexandre M. Florio,Michel Gendreau,Richard F. Hartl,Stefan Minner,Thibaut Vidal
标识
DOI:10.1016/j.ejor.2022.10.045
摘要
We consider the vehicle routing problem with stochastic demands (VRPSD), a stochastic variant of the well-known VRP in which demands are only revealed upon arrival of the vehicle at each customer. Motivated by the significant recent progress on VRPSD research, we begin this paper by summarizing the key new results and methods for solving the problem. In doing so, we discuss the main challenges associated with solving the VRPSD under the chance-constraint and the restocking-based perspectives. Once we cover the current state-of-the-art, we introduce two major methodological contributions. First, we present a branch-price-and-cut (BP&C) algorithm for the VRPSD under optimal restocking. The method, which is based on the pricing of elementary routes, compares favorably with previous algorithms and allows the solution of several open benchmark instances. Second, we develop a demand model for dealing with correlated customer demands. The central concept in this model is the “external factor”, which represents unknown covariates that affect all demands. We present a Bayesian-based, iterated learning procedure to refine our knowledge about the external factor as customer demands are revealed. This updated knowledge is then used to prescribe optimal replenishment decisions under demand correlation. Computational results demonstrate the efficiency of the new BP&C method and show that cost savings above 10% may be achieved when restocking decisions take account of demand correlation. Lastly, we motivate a few research perspectives that, as we believe, should shape future research on the VRPSD.
科研通智能强力驱动
Strongly Powered by AbleSci AI