Title: A multi-start heuristic approach for the split-delivery vehicle routing problem with minimum delivery amounts
Authors: Han, Anthony Fu-Wha
Chu, Yu-Ching
運輸與物流管理系 註:原交通所+運管所
Department of Transportation and Logistics Management
Keywords: Vehicle routing;Split delivery;Minimal delivery amount;Variable neighborhood descent;Node-ejection chains;Heuristics
Issue Date: Apr-2016
Abstract: We propose a new multi-start solution approach for the split-delivery vehicle routing problem with minimum delivery amounts (SDVRP-MDA). Initial solutions are generated by both node-insertion and route-addition procedures with a single parameter to control the restart. These solutions are then improved by a variable neighborhood descent metaheuristic with a novel search operator inspired by node-ejection chains. We test the proposed approach with 32 benchmark instances for four different minimum delivery fractions. Using the proposed algorithm, out of 128 cases tested, we find 81 best known solutions and 34 new best solutions; overall, we find 43 new best solutions. (C) 2016 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tre.2016.01.014
http://hdl.handle.net/11536/133819
ISSN: 1366-5545
DOI: 10.1016/j.tre.2016.01.014
Journal: TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW
Volume: 88
Begin Page: 11
End Page: 31
Appears in Collections:Articles