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

International Journal of Supply and Operations Management

Sanae Larioui¹ 

[1] ENSATE, University of Abdelmalek Essaadi, Mhannech II, Tetouan, Morocco;

关键词: vehicle routing problem;    split delivery;    variable neighborhood search;    evolutionary local search;    variable neighborhood descent;   

DOI  :  10.22034/2017.4.04

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown