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

Larioui, Sanae

doi:10.22034/2017.4.04

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

Document Type : Research Paper

Author

Sanae Larioui

ENSATE, University of Abdelmalek Essaadi, Mhannech II, Tetouan, Morocco

10.22034/2017.4.04

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.

Keywords

Main Subjects

logistics, transportation, distribution, and materials Handling

References

B.E. Gillett and L.R. Miller (1974). A heuristic algorithm for the vehicle dispatch problem. Operations Research, Vol. 22, pp. 340–349.

C. Archetti, M.W.P. Savelsbergh, and M.G. Speranza (2006). Worst-case analysis for split delivery vehicle routing problems. Transportation Science, Vol. 40(2), pp. 226–234.

C. Archetti, M.G. Speranza, and A. Hertz (2006). A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, Vol. 40(1), pp. 64–73.

C. Archetti, M.G. Speranza, and M.W.P. Savelsbergh. (2008) An optimization based heuristic for the split delivery vehicle routing problem. Transportation Science, Vol. 42(1), pp. 22–31.

C. Gu´eguen (1999). Exact solution methods for vehicle routing problems. PhD thesis, Central School of Paris, France, (in French).

C. Prins (2009). Bio-inspired Algorithms for the Vehicle Routing Problem, chapter A GRASP × evolutionary local search hybrid for the vehicle routing problem, pp. 35–53. Springer.

E. Mota, V. Campos, and A. Corber´an (2007). A new metaheuristic for the vehicle routing problem with split demands. In C. Cotta and J. Van Hemert, editors, Evolutionary computation in combinatorial optimization, Lecture Notes in Computer Science, Vol. 4446, pp. 121–129, Berlin, Springer.

G. Clarke and J.W Wright. (1964), Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, Vol. 12, pp. 568–581.

J.M. Belenguer, E. Benavent, N. Labadi, C. Prins, and M. Reghioui (2010). Split delivery capacitated arc-routing problem: Lower bound and metaheuristic. Transportation Science, Vol. 44(2), pp. 206–220.

J.M. Belenguer, M.C. Martinez, and E. Mota (2000). A lower bound for the split delivery vehicle routing problem. Operations Research, Vol. 48(5), pp. 801–810.

L. Moreno, M. Poggi de Arag˜ao, and E. Uchoa (2010). Improved lower bounds for the split delivery vehicle routing problem. Operations Research Letters, Vol. 38, pp. 302–306.

M. Boudia, C. Prins, andM. Reghioui (2007). An effective memetic algorithm with population management for the split-delivery vehicle routing problem. In T. Bartz- Beielstein et al., editor, Hybrid Metaheuristics, Lecture Notes in Computer Science, Vol. 4771, pp. 16–30, Berlin. Springer.

M. Dror and P. Trudeau (1989). Savings by split delivery routing. Transportation Science, Vol. 23(2), pp. 141–145.

M. Dror and P. Trudeau (1990). Split delivery routing. Naval Research Logistics, Vol. 37, pp. 383–402.

M. Dror, G. Laporte, and P. Trudeau (1994). Vehicle routing with split deliveries. Discrete Applied Mathematics, Vol. 50, pp. 239–254.

M. Gendreau, P. Dejax, D. Feillet, and C. Gueguen (2006). Vehicle routing with time windows and split deliveries. Technical Report 2006–851, Laboratoire d’Informatique d’Avignon.

M. Jin, K. Liu, and R. Bowden (2007). A two stage algorithm with valid inequalities for the split delivery vehicle routing problem. International Journal of Production Economics, Vol. 105, pp. 228–242.

M. Jin, K. Liu, and B. Eksioglu (2008). A column generation approach for the split delivery vehicle routing problem. Operations Research Letters, Vol. 36, pp. 265–270.

M. Reghioui. Vehicle routing problems with time windows or split deliveries. PhD thesis, University of Technology of Troyes, 2008 (in French).

N. Mladenovi´c and P. Hansen (1997). Variable neighborhood search. Computers & Operations Research, Vol. 24(11), pp. 1097–1100.

P.A. Mullaseril, M. Dror, and J. Leung (1997). Split-delivery routing heuristics in livestock feed distribution. Journal of the Operational Research Society, Vol. 48(2), pp. 107–116.

P.W. Frizzell and J.W. Giffin( 1995). The split delivery vehicle scheduling problem with time windows and grid network distances. Computers and Operations Research, Vol. 22(6), pp. 655–667.

S. Chen, B.L. Golden, and E. Wasil (2007). The split delivery vehicle routing problem: applications, algorithms, test problems and computational results. Networks, Vol. 49 (4), pp. 318–329.

S.C. Ho and D. Haugland (2004). A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers and Operations Research, Vol. 31, pp.1947–1964.

S. Wolf and P. Merz (2007). Evolutionary local search for the super-peer selection problem and the p-hub median problem. In T. Bartz-Beielstein et al., editor, Hybrid Metaheuristics, Lecture Notes in Computer Science, Vol. 4771, pp. 1–15, Berlin,. Springer.

T.A. Feo and J. Bard (1989). Flight scheduling and maintenance base planning. Management Science, Vol. 35(12), pp. 1415–1432.

R.E. Aleman, X. Zhang, and R.R. Hill (2010). An adaptive memory algorithm for the split delivery vehicle routing problem. Journal of Heuristics, Vol. 16 (3), pp. 441–473.