Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands
Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands
复制标题
DOI：
10.1016/j.trc.2010.09.007
复制
发表时间：
2011-08
影响因子：
8.3
通讯作者：
A. Juan;J. Faulin;S. Grasman;D. Riera;J. Marull;C. Méndez
中科院分区：
文献类型：
--
作者：
A. Juan;J. Faulin;S. Grasman;D. Riera;J. Marull;C. Méndez
本文在介绍了随机需求车辆路径问题（VRPSD）及其相关工作的基础上，提出了一种灵活的求解方法。这种方法背后的逻辑是将解决给定VRPSD实例的问题转化为解决一小组容量限制车辆路径问题（CVRP）实例的问题。因此，我们的方法利用了这样一个事实，即CVRP已经存在非常有效的元分析。CVRP实例是从原始VRPSD实例中获得的，方法是为路由车辆必须使用的安全库存水平分配不同的值，以处理意外需求。该方法还利用蒙特卡罗模拟（MCS），以获得每个先验解决方案的可靠性估计-也就是说，没有车辆运行的负载完成其交付路线之前的概率-以及与纠正路由行动（追索行动）后，车辆运行的负载完成其路线的预期成本。通过这种方式，获得了不同路由选择方案的预期总成本的估计。最后，一个广泛的数值实验，包括在不同的不确定性的情况下，分析所描述的方法的效率的文件。
After introducing the Vehicle Routing Problem with Stochastic Demands (VRPSD) and some related work, this paper proposes a flexible solution methodology. The logic behind this methodology is to transform the issue of solving a given VRPSD instance into an issue of solving a small set of Capacitated Vehicle Routing Problem (CVRP) instances. Thus, our approach takes advantage of the fact that extremely efficient metaheuristics for the CVRP already exists. The CVRP instances are obtained from the original VRPSD instance by assigning different values to the level of safety stocks that routed vehicles must employ to deal with unexpected demands. The methodology also makes use of Monte Carlo simulation (MCS) to obtain estimates of the reliability of each aprioristic solution – that is, the probability that no vehicle runs out of load before completing its delivering route – as well as for the expected costs associated with corrective routing actions (recourse actions) after a vehicle runs out of load before completing its route. This way, estimates for expected total costs of different routing alternatives are obtained. Finally, an extensive numerical experiment is included in the paper with the purpose of analyzing the efficiency of the described methodology under different uncertainty scenarios.