چکیده:
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.
خلاصه ماشینی:
This paper presents a simple and effective metaheuristic algorithm for the Split Delivery Vehicle Routing Problem (SDVRP).
(2010), is based on an algorithm that combines column and cut generation approaches and improves many of the best known lower bounds found by the two previous methods.
For the arc routing version (the Split Delivery Capacitated Arc Routing Problem, SDCARP), an adaptation of the SDVRP heuristic of Dror and Trudeau for the SDCARP with time windows was proposed by Mullaseril et al.
4. General presentation of the solution approach The metaheuristic proposed in this study is an enhanced version of a new method called hybrid GRASP × ELS that was applied successfully to the classical Vehicle Routing Problem by Prins in 2009.
The GRASP is a simple metaheuristic proposed by Feo and Bard (1989) in which each iteration consists of two phases: constructing a greedy randomized solution and improving it with a local search procedure.
Its application to the Capacitated Arc Routing Problem with Split Deliveries has resulted in high-quality solutions compared with those obtained from a memetic algorithm.
The enhancement proposed by the method sketched in Algorithm 3 consists of replacing the greedy randomized heuristic in the first phase by a procedure that modifies the best solution achieved so far, inspired by the strategy used in the shaking phase of the Variable Neighborhood Search (VNS).
A tabu search algorithm for the split delivery vehicle routing problem.