Compact Formulations for Split Delivery Routing Problems

Pedro Munari () and Martin Savelsbergh ()
Additional contact information
Pedro Munari: Production Engineering Department, Federal University of Sao Carlos, Sao Carlos, SP 13561-353, Brazil
Martin Savelsbergh: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Transportation Science, 2022, vol. 56, issue 4, 1022-1043

Abstract: Split delivery routing problems are concerned with serving the demand of a set of customers with a fleet of capacitated vehicles at minimum cost, where a customer can be served by more than one vehicle if beneficial. They generalize traditional variants of routing problems and have applications in commercial and humanitarian logistics. Previously, formulations involving only commonly used arc-based variables have provided only relaxations for split delivery variants, as the possibility of visiting customers more than once introduces modeling challenges. The only known compact formulations are based on variables indexed by vehicle or by visit number and perform poorly when using general-purpose integer programming software. We present compact formulations that avoid the use of these types of variables and that can model split delivery routing problems with and without time windows. Computational experiments demonstrate their superior performance over existing compact formulations. We also develop a branch-and-cut algorithm that balances the efficiency derived from a relaxed formulation with the strength derived from one of the proposed formulations and demonstrate its efficacy on a large set of benchmark instances. The algorithm solves 95 instances to proven optimality for the first time and improves the best known lower and/or upper bound for many other instances.

Keywords: vehicle routing; split delivery; compact models; branch-and-cut (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.1106 (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:4:p:1022-1043

Access Statistics for this article

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