An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands
An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands
复制标题
DOI：
10.1287/opre.50.3.415.7751
复制
发表时间：
2002-05-01
影响因子：
2.7
通讯作者：
van Hamme, L
中科院分区：
文献类型：
--
作者：
Laporte, G;Louveaux, F;van Hamme, L
经典的车辆路径问题包括确定相同车辆的最优路径，从仓库出发，离开，这样每个客户只访问一次。在容量限制型（CVRP）中，沿沿着收集的总需求不能超过车辆容量。这意味着在到达客户之前，每个客户的需求水平是未知的。在某些情况下，即使沿着路线的预期需求不超过车辆容量，车辆也可能因此不能装载客户的需求。这种情况被称为失败。容量限制的车辆路径问题与随机需求（SVRP），然后由最小化的总成本的计划路线和预期的失败，在这里，失败的惩罚对应于返回到仓库。车辆首先返回车辆段卸货，然后按原计划继续行驶。本文研究了SVRP精确解的一种实现方法-抛物线形法。它开发了新的下限的预期惩罚失败。此外，它还提供了SVRP的最优性切割的变体，这些变体也适用于分数解。数值实验表明，一些情况下，涉及多达100个客户和少量的车辆可以解决的最优性在一个相对较短的计算时间。
The classical Vehicle Routing Problem consists of determining optimal routes for in identical vehicles, starting and leaving at the depot, such that every customer is visited exactly once. In the capacitated version (CVRP) the total demand collected along a route cannot exceed the vehicle capacity, This article considers the situation where some of the demands are stochastic. This implies that the level of demand at each customer is not known before arriving at the customer. In some cases, the vehicle may thus be unable to load the customer's demand, even if the expected demand along the route does not exceed the vehicle capacity. Such a situation is referred to as a failure. The capacitated vehicle routing problem with stochastic demands (SVRP) then consists of minimizing the total cost of the planned routes and of expected failures, Here, penalties for failures correspond to return trips to the depot. The vehicle first returns to the depot to unload, then resumes its trip as Originally planned. This article studies an implementation of the Integer L-shaped method for the exact solution of the SVRP. It develops new lower bounds on the expected penalty for failures. In addition, it provides variants of the optimality cuts for the SVRP that also hold at fractional solutions. Numerical experiments indicate that some instances involving up to 100 customers and few vehicles can be solved to optimality within a relatively short computing time.