an enhanced evolutionary local search for the split delivery vehicle routing problem

We present a simple and effective metaheuristic algorithm for the split delivery vehicle routing problem (sdvrp). the sdvrp is a relaxation of the classical vehicle routing problem in which a customer demand may be serviced by more than one vehicle. the objective is to find a set of least cost trips for a fleet of identical vehicles to service geographically scattered customers with or without splitting. the proposed method is a hybridization between a variable neighborhood search (vns), an evolutionary local search (els) and a variable neighborhood descent (vnd). it combines the multi-start approach of vns and els and the vnd intensification and diversification strategies. this new method is tested on three sets of instances from literature containing a total of 77 benchmark problems. the obtained results show that the algorithm outperforms all previously published metaheuristics. 62 instances out of 77 are improved