论文标题
随机车辆路由问题的分解整数L形方法
The disaggregated integer L-shaped method for the stochastic vehicle routing problem
论文作者
论文摘要
本文提出了一种新的整数L形方法，用于求解两阶段随机整数程序，其第一阶段的解决方案可以将其分解为不相交组件，每个组件具有单调求程功能。在最小化问题中，单调性属性规定，组件的追索成本必须始终高或等于其任何子组件的费用。该方法利用了在此属性下有效的新型最佳削减和下限功能。随机车辆路由问题特别适合通过这种方法解决，因为它的解决方案可以分解为一组路线。我们考虑了具有随机需求的变体，在这种变体中，在车辆没有足够的能力满足新实现的客户需求的能力时，追索权的政策包括进行返回仓库。这项工作表明，该策略可以导致非单调求助功能，但是当客户需求由几个常用概率分布的家族建模时，单调性就会达到。我们还在追索过程中提出了新的特定问题的下限，从而增强了下限功能并显着加快分辨率的速度。关于文献实例的计算实验表明，新方法可实现最新的结果。
This paper proposes a new integer L-shaped method for solving two-stage stochastic integer programs whose first-stage solutions can decompose into disjoint components, each one having a monotonic recourse function. In a minimization problem, the monotonicity property stipulates that the recourse cost of a component must always be higher or equal to that of any of its subcomponents. The method exploits new types of optimality cuts and lower bounding functionals that are valid under this property. The stochastic vehicle routing problem is particularly well suited to be solved by this approach, as its solutions can be decomposed into a set of routes. We consider the variant with stochastic demands in which the recourse policy consists of performing a return trip to the depot whenever a vehicle does not have sufficient capacity to accommodate a newly realized customer demand. This work shows that this policy can lead to a non-monotonic recourse function, but that the monotonicity holds when the customer demands are modeled by several commonly used families of probability distributions. We also present new problem-specific lower bounds on the recourse that strengthen the lower bounding functionals and significantly speed up the resolution process. Computational experiments on instances from the literature show that the new approach achieves state-of-the-art results.
