|標題:||NEIGHBORHOOD SEARCH METHODS DESIGNED FOR SPLIT DELIVERY VEHICLE ROUTING PROBLEMS|
|作者:||Han, Anthony F.|
Chu, Herman Y.
Department of Transportation and Logistics Management
|關鍵字:||Split delivery;vehicle routing problem;ejection-chain;variable neighborhood descent|
|摘要:||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.|
|Appears in Collections:||Conferences Paper|