A Column Generation-Based Heuristic for the Split Delivery Vehicle Routing Problem with Time Windows

Pedro Munari () and Martin Savelsbergh ()
Additional contact information
Pedro Munari: Federal University of Sao Carlos
Martin Savelsbergh: Georgia Institute of Technology

SN Operations Research Forum, 2020, vol. 1, issue 4, 1-24

Abstract: 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 generation-based 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 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s43069-020-00026-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:snopef:v:1:y:2020:i:4:d:10.1007_s43069-020-00026-z

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-020-00026-z

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().