A matheuristic approach for the split delivery vehicle routing problem: an efficient set covering-based model with guided route generation schemes

The split delivery vehicle routing problem (SDVRP) is a relaxed  version of the classical VRP where customers can be visited more  than once. The SDVRP is also applicable for problems where one or  more of the customers require a demand larger than the vehicle  capacity. Constructive heuristics adapted from the parallel savings  and the sweep methods are first proposed to generate a set of  solutions which is then used in the new and more efficient set  covering-based formulation which we put forward. An effective repair  mechanism to remedy any infeasibility due to the set covering  problem is presented. A reduced set of promising routes is used in our model, instead of the original set of routes, proposing and using well defined reduction schemes. This set covering-based approach is  tested on large datasets from the literature with encouraging results. In brief, seven best solutions including ties are found among the 137 SDVRP instances.