A hybrid VND method for the split delivery vehicle routing problem

The split delivery vehicle routing problem (SDVRP) is a variant of the classical vehicle routing problem in which a customer's demand can be split among several vehicles. For this NP-hard problem we have shown that there exists an optimal solution which can be encoded by a permutation of customers. As a result, we divide the SDVRP into two subproblems: find the best permutation and find the best vehicle routes for arbitrary permutation. Based on this approach, we design a hybrid metaheuristic which combines the Variable Neighborhood Decent and Stochastic Tabu Search methods for the first subproblem, and two fast decoding heuristics for the second subproblem. Computational results indicate that the proposed method is competitive. It improves 23 best known solutions on the 95 available test instances with number of customers up to 288.