General edge assembly crossover driven memetic search for split delivery vehicle routing
Pengfei He  1@  , Jin-Kao Hao  2, 3@  
1 : Laboratoire dÉtudes et de Recherche en Informatique dÁngers
Université d'Angers, Université d'Angers : EA2645
2 : LERIA
David Lesaint : DavidLesaint, David Lesaint
3 : Université d'Angers
LERIA

The split delivery vehicle routing problem is a variant of the well-known vehicle routing problem, where each customer can be visited by several vehicles. The problem has many practical applications, but is computationally challenging. This paper presents an effective memetic algorithm for solving the problem with a fleet of limited or unlimited vehicles. The algorithm features a general edge assembly crossover to generate promising offspring solutions from the perspective of assembling suitable edges and an effective local search to improve each offspring solution. The algorithm is further reinforced by a feasibility-restoring procedure, a diversification-oriented mutation and a quality-and-distance pool updating technique. Extensive experiments on 324 benchmark instances indicate that our algorithm is able to update 143 best upper bounds in the literature and match the best results for 156 other instances. Additional experiments are presented to obtain insights into the roles of the key search ingredients of the algorithm. The method was ranked second at the 12th DIMACS Implementation Challenge on Vehicle Routing - SDVRP Track.


Personnes connectées : 160 Vie privée
Chargement...