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 as well as humanitarian logistics. Previously, pure arc-based formulations have only provided relaxations for split delivery routing problems, 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 to solve them. We present compact formulations that avoid the use of variables indexed by vehicle or visit number and that can be used to 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 an extended formulation, and demonstrate its efficacy on a large set of benchmark instances. The algorithm solves 89 instances to proven optimality for the first time and improves the best known lower and/or upper bound for many other instances.
Citation
Technical Report MS01/2019, Operations Research Group, Production Engineering Department, Federal University of São Carlos, Brazil. 2019.