General Edge Assembly Crossover-Driven Memetic Search for Split Delivery Vehicle Routing

Pengfei He () and Jin-Kao Hao ()
Additional contact information
Pengfei He: Laboratoire d’Etude et de Recherche en Informatique d’Angers, Université d’Angers, 49045 Angers, France
Jin-Kao Hao: Laboratoire d’Etude et de Recherche en Informatique d’Angers, Université d’Angers, 49045 Angers, France

Transportation Science, 2023, vol. 57, issue 2, 482-511

Abstract: 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 it 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 insight into the roles of the key search ingredients of the algorithm. The method was ranked second in the SDVRP track at the 12th DIMACS Implementation Challenge on Vehicle Routing Problems.

Keywords: split delivery vehicle routing; vehicle routing; heuristics; edge assembly crossover; hybrid search (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1180 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:57:y:2023:i:2:p:482-511

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().