A ring-based diversification scheme for routing problems (Q843395)

Summary: The split delivery vehicle routing problem (SDVRP) relaxes the classical vehicle routing problem (VRP) by allowing multiple vehicles to supply the demand of individual customers thereby potentially reducing costs. This article provides an up-to-date review of the SDVRP literature and presents a new solution diversification scheme based on concentric rings centred at the depot that partitions the original problem. The resulting subproblems are then solved using a constructive approach. Different ring settings produce varied partitions and thus different solutions to the original problem are obtained and improved via a variable neighbourhood descent. Computational results on available test problems demonstrate the effectiveness of the proposed algorithm and present new best solutions to some of the tested problems.