Preemptive depot returns for dynamic same-day delivery

作     者：Ulmer, Marlin W. Thomas, Barrett W. Mattfeld, Dirk C. 

作者机构：Tech Univ Carolo Wilhelmina Braunschweig Braunschweig Germany Univ Iowa Iowa City IA USA 

出 版 物：《EURO JOURNAL ON TRANSPORTATION AND LOGISTICS》 (EURO运输和物流杂志)

年 卷 期：2019年第8卷第4期

页      面：327-361页

核心收录：

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

主　　题：Stochastic dynamic vehicle routing Same-day delivery Preemptive depot returns Approximate dynamic programming 

摘      要：In this paper, we explore same-day delivery routing and particularly how same-day delivery vehicles can better integrate dynamic requests into delivery routes by taking advantage of preemptive depot returns. A preemptive depot return occurs when a delivery vehicle returns to the depot before delivering all of the packages currently on-board the vehicle. In this paper, we assume that a vehicle serves requests in a particular delivery area. Beginning the day with some known deliveries, the vehicle seeks to serve the known requests as well as additional new requests that are received throughout the day. To serve the new requests, the vehicle must return to the depot to pick up the packages for delivery. In contrast to previous work on same-day delivery routing, in this paper, we allow the vehicle to return to the depot before serving all loaded packages. To solve the problem, we couple an approximation of the value of choosing any particular subset of requests for delivery with a routing heuristic. Our approximation procedure is based on approximate dynamic programming and allows us to capture both the current value of a subset selection decision and its impact on future rewards. Using extensive computational tests, we demonstrate the value of preemptive depot returns and the value of the proposed approximation scheme in supporting preemptive returns. We also identify characteristics of instances for which preemptive depot returns are most likely to offer improvement.