We propose a matheuristic approach to solve split delivery variants of the vehicle routing problem (VRP). The proposed method is based on the use of several mathematical programming components within an Iterated Local Search metaheuristic framework. In addition to well-known VRP local search heuristics, we include new types of improvement and perturbation strategies that are tailored for split delivery VRPs. Moreover, we enhance the solution improvement phase by also calling a local search procedure based on a mixed-integer programming model, and resorting to state-of-the-art exact and heuristic libraries, including a tailored branch-and-cut method. To verify the performance of the proposed approach, we run computational experiments using the benchmark instances provided in the 12th DIMACS Implementation Challenge.
Technical Report, Operations Research Group, Production Engineering Department, Federal University of São Carlos. January, 2022