Group for Research in Decision Analysis

G-2019-39

A large neighborhood search for the vehicle routing problem with multiple time windows

, , , and

User-centered logistics aiming at customer satisfaction are gaining importance due to growing e-commerce and home deliveries. Customer satisfaction can be strongly increased by offering narrow delivery time windows. However, there is a tradeoff for the logistics provider because user-friendly delivery time windows might decrease the operational flexibility. Against this background, we study the Vehicle Routing Problem with Multiple Time Windows (VRPMTW) that determines a set of optimal routes such that each customer is visited once within one out of several time windows. We present a large neighborhood search based metaheuristic for the VRPMTW that contains a dynamic programming component to optimally select a time window for each customer on a route, and we present computationally efficient move descriptors for all search operators. We evaluate the performance of our algorithm on the Belhaiza instance set and provide new best known solutions for 26 out of 48 instances with improvements of up to 25.3% and 1.5% on average. Furthermore, we design new benchmark instances that reflect planning tasks in user-centered last mile logistics. Based on these, we present managerial studies that show the benefit of our algorithm for practitioners and allow to derive insights on how to offer time windows to customers. We show that offering multiple time windows can be economically beneficial for the logistics service providers and increases customer flexibility simultaneously.

, 33 pages