An integer <i>L</i>-shaped algorithm for the capacitated vehicle routing problem with stochastic demands

作     者：Laporte, G Louveaux, F van Hamme, L 

作者机构：Ecole Hautes Etud Commerciales Montreal PQ H3T 1V6 Canada Univ Montreal Ctr Rech Transports Montreal PQ H3C 3J7 Canada Fac Univ Notre Dame Paix Dept Methodes Quantitat B-5000 Namur Belgium OM Partners B-2130 Brasschaat Belgium 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2002年第50卷第3期

页      面：415-423页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Vehicles Integers Vertices Vehicle capacity A priori knowledge Algorithms Determinism Heuristics Minimization of cost 

摘      要：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.