An Enhanced Evolutionary Local Search for the Split Delivery Vehicle Routing Problem

Abstract

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.