Browsing by Author "Chu, Herman Y."

Now showing 1 - 1 of 1

NEIGHBORHOOD SEARCH METHODS DESIGNED FOR SPLIT DELIVERY VEHICLE ROUTING PROBLEMS
(2011-01-01)
Han, Anthony F.
;
Cho, Yuh-Jen
;
Chu, Herman Y.
;
運輸與物流管理系註：原交通所+運管所
;
Department of Transportation and Logistics Management
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.