NEIGHBORHOOD SEARCH METHODS DESIGNED FOR SPLIT DELIVERY VEHICLE ROUTING PROBLEMS

Abstract

Split delivery vehicle routing problem (SDVRP), which allows the demand of a customer to be split and delivered by multiple vehicles, is a variant of conventional vehicle routing problem (VRP). The potential savings due to the split delivery has proved to be as much as 50%. However, until recently, most studies in solving SDVRP did not involve neighborhood search methods tailor-made for split deliveries. In this article, we present two new neighborhood search methods, i.e. 2-opt** and Ejection-chain*, and an innovative construction algorithm designed for SDVRP. We have tested the new methods on two sets of benchmark problems with a variable neighborhood descent approach. It is found that our proposed approach has obtained 3 new best solutions for the 57 benchmark instances tested. Such results indicate a great potential of further applications of our proposed local search methods for SDVRP.