A New Family of Route Formulations for Split Delivery Vehicle Routing Problems

Isaac Balster (), Teobaldo Bulhões (), Pedro Munari (), Artur Alves Pessoa () and Ruslan Sadykov ()
Additional contact information
Isaac Balster: Inria Centre at the University of Bordeaux, Talence 33405, France
Teobaldo Bulhões: Centro de Informática, Departamento de Computação Científica, Universidade Federal da Paraíba, 58055-000 João Pessoa, Brazil
Pedro Munari: Production Engineering Department, Federal University of São Carlos, 13565-905 São Carlos-SP, Brazil
Artur Alves Pessoa: Engenharia de Produção, Universidade Federal Fluminense, 24210-240 Niterói-RJ, Brazil
Ruslan Sadykov: Inria Centre at the University of Bordeaux, Talence 33405, France

Transportation Science, 2023, vol. 57, issue 5, 1359-1378

Abstract: We propose a new family of formulations with route-based variables for the split delivery vehicle routing problem with and without time windows. Each formulation in this family is characterized by the maximum number of different demand quantities that can be delivered to a customer during a vehicle visit. As opposed to previous formulations in the literature, the exact delivery quantities are not always explicitly known in this new family. The validity of these formulations is ensured by an exponential set of nonrobust constraints. Additionally, we explore a property of optimal solutions that enables us to determine a minimum delivery quantity based on customer demand and vehicle capacity, and this number is often greater than one. We use this property to reduce the number of possible delivery quantities in our formulations, improving the solution times of the computationally strongest formulation in the family. Furthermore, we propose new variants of nonrobust cutting planes that strengthen the formulations, namely limited-memory subset-row covering inequalities and limited-memory strong k -path inequalities. Finally, we develop a branch-cut-and-price (BCP) algorithm to solve our formulations enriched with the proposed valid inequalities, which resorts to state-of-the-art algorithmic enhancements. We show how to effectively manage the nonrobust cuts when solving the pricing problem that dynamically generates route variables. Numerical results indicate that our formulations and BCP algorithm establish new state-of-the-art results for the variant with time windows, as many benchmark instances with 50 and 100 customers are solved to optimality for the first time. Several instances of the variant without time windows are solved to proven optimality for the first time.

Keywords: vehicle routing; time windows; split delivery; branch-cut-and-price; nonrobust cuts (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.0085 (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:57:y:2023:i:5:p:1359-1378

Access Statistics for this article

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