The multi-depot split delivery vehicle routing problem: An integer programming-based heuristic, new test problems, and computational results

The multi-depot split delivery vehicle routing problem combines the split delivery vehicle routing problem and the multiple depot vehicle routing problem. We define this new problem and develop an integer programming-based heuristic for it. We apply our heuristic to 30 instances to determine the reduction in distance traveled that can be achieved by allowing split deliveries among vehicles based at the same depot and vehicles based at different depots. We generate new test instances with high-quality, visually estimated solutions and report results on these instances.

► We propose a new variant of the vehicle routing problem (VRP).
► Our variant combines split deliveries and multiple depots.
► We develop an integer programming-based heuristic.
► Our heuristic produces high-quality solutions to a wide range of test instances.