A Large Neighborhood Search for the Vehicle Routing Problem with Multiple Time Windows

Hendrik Schaap (), Maximilian Schiffer (), Michael Schneider () and Grit Walther ()
Additional contact information
Hendrik Schaap: Chair of Operations Management, School of Business and Economics, RWTH Aachen University, 52072 Aachen, Germany
Maximilian Schiffer: School of Management & Munich Data Science Institute, Technical University of Munich, 80333 Munich, Germany
Michael Schneider: Deutsche Post Chair – Optimization of Distribution Networks, School of Business and Economics, RWTH Aachen University, 52072 Aachen, Germany
Grit Walther: Chair of Operations Management, School of Business and Economics, RWTH Aachen University, 52072 Aachen, Germany

Transportation Science, 2022, vol. 56, issue 5, 1369-1392

Abstract: User-centered logistics that aim at customer satisfaction are gaining importance because of 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 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 for the objectives of minimizing traveled distance and duration. For the former objective, we provide new best-known solutions for 9 of 48 instances, and for the latter, we provide new best-known solutions for 13 of 48 instances. Overall, our algorithm provides the best average solution quality over the full benchmark set among all available algorithms. 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.

Keywords: vehicle routing; multiple time windows; efficient route evaluation; dynamic programming (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1120 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:56:y:2022:i:5:p:1369-1392

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().