A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands

作     者：Salavati-Khoshghalb, Majid Gendreau, Michel Jabali, Ola Rei, Walter 

作者机构：Univ Montreal Dept Informat & Rech Operat Montreal PQ H3C 3J7 Canada Ctr Interuniv Rech Reseaux Entreprise Logist & Tr Montreal PQ H3C 3J7 Canada Polytech Montreal Dept Math & Genie Ind Montreal PQ H3C 3J7 Canada Politecn Milan Dipartimento Elettron Informaz & Bioingn I-20133 Milan Italy Univ Quebec Montreal Dept Management & Technol Ecole Sci Gest Montreal PQ H3C 3P8 Canada 

出 版 物：《TRANSPORTATION SCIENCE》 (运输科学)

年 卷 期：2019年第53卷第5期

页      面：1334-1353页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0823[工学-交通运输工程] 

基　　金：Natural Sciences and Engineering Research Council of Canada 

主　　题：threshold-based recourse policies operational rules vehicle routing problem with stochastic demands partial route integer L-shaped algorithm lower bounding functionals 

摘      要：In this paper we consider the vehicle routing problem with stochastic demands (VRPSD). We consider that customer demands are only revealed when a vehicle arrives at customer locations. Failures occur whenever the residual capacity of the vehicle is insufficient to serve the observed demand of a customer. Such failures entail that recourse actions be taken to recover route feasibility. These recourse actions usually take the form of return trips to the depot, which can be either done in a reactive or proactive fashion. Over the years, there have been various policies defined to perform these recourse actions in either a static or a dynamic setting. In the present paper, we propose policies that better reflect the fixed operational rules that can be observed in practice and that also enable implementing preventive recourse actions. We define the considered operational rules and show how, for a planned route, these operational rules can be implemented using a fixed threshold-based policy to govern the recourse actions. An exact solution algorithm is developed to solve the VRPSD under the considered policies. Finally, we conduct an extensive computational study, which shows that significantly better solutions can be obtained when using the proposed policies compared with solving the problem under the classic recourse definition.