A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows
- PDF / 1,626,383 Bytes
- 24 Pages / 439.642 x 666.49 pts Page_size
- 68 Downloads / 206 Views
A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows Pedro Munari1
· Martin Savelsbergh2
Received: 10 March 2020 / Accepted: 4 September 2020 / © Springer Nature Switzerland AG 2020
Abstract The vehicle routing problem with time windows (VRPTW) is one of the most studied variants of routing problems. We consider the split delivery VRPTW (SDVRPTW), an extension in which customers can be visited multiple times, if advantageous. While this additional flexibility can result in significant cost reductions, it also results in additional modeling and computational challenges. Indeed, the branch-and-price algorithms used to successfully solve VRPTW instances require substantial modifications before they can be used to solve SDVRPTW instances, and then often exhibit inferior performance when compared with branch-and-cut algorithms for solving SDVRPTW instances (whereas branch-and-price algorithms tend to perform better than branch-and-cut algorithms for the VRPTW). We propose a new route-based formulation for the SDVRPTW that differs fundamentally from others presented in the literature. It is the first formulation in which the number of decision variables related to delivery quantities as well as the number of constraints is polynomial in the number of customers. We use this formulation as the basis for a column generationbased heuristic that produces high-quality solutions for a wide range of benchmark instances with 50 and 100 customers and vehicle capacity equal to 50 and 100. It finds many new best known solutions, and, for the first time, we report upper bounds for all 100-customer instances. Keywords Vehicle routing · Time windows · Split delivery · Column generation · Branch-and-cut
This article is part of the Topical Collection on Decomposition at 70 Pedro Munari
[email protected] Martin Savelsbergh [email protected] 1
Federal University of Sao Carlos, Sao Carlos, SP, Brazil
2
Georgia Institute of Technology, Atlanta, GA, USA
26
Page 2 of 24
SN Operations Research Forum
(2020) 1:26
1 Introduction Time-constrained routing and scheduling has been a popular, productive, important, and ever-expanding area of research. For an early, but still relevant, introduction and overview, see Desrosiers et al. [18]. Within this class of problems, the vehicle routing problem with time windows (VRPTW) is the most widely studied variant and generalizes the (capacitated) vehicle routing problem by restricting the time during which customers can be served. For introductions and overviews, see Cordeau et al. [14], Braysy and Gendreau [9, 10] and Baldacci et al. [7]. Desrochers et al. [17] were the first to propose an effective exact method for the VRPTW. The method uses the column generation (CG) technique, having a set partitioning formulation as the master problem, and a resource constrained shortest path problem (RCSPP) as the subproblem. The method is so powerful that after almost 30 years it remains the basis of current state-of-the-art exact appro
Data Loading...
