Solving soft and hard-clustered vehicle routing problems: A bi-population collaborative memetic search approach

Yangming Zhou, Lingheng Liu, Una Benlic, Zhi-Chun Li and Qinghua Wu

European Journal of Operational Research, 2025, vol. 324, issue 3, 825-838

Abstract: The soft-clustered vehicle routing problem is a natural generalization of the classic capacitated vehicle routing problem, where the routing decision must respect the already taken clustering decisions. It is a relevant routing problem with numerous practical applications, such as packages or parcels delivery. Population-based evolutionary algorithms have already been adapted to solve this problem. However, they usually evolve a single population and suffer from early convergence especially for large instances, resulting in sub-optimal solutions. To maintain a high diversity so as to avoid premature convergence, this work proposes a bi-population collaborative memetic search method that adopts a bi-population structure to balance between exploration and exploitation, where two populations are evolved in a cooperative way. Starting from an initial population generated by a data-driven and knowledge-guided population initialization, two heterogeneous memetic searches are then performed by employing a pair of complementary crossovers (i.e., a multi-route edge assembly crossover and a group matching-based crossover) to generate offspring solutions, and a bilevel variable neighborhood search to explore the solution space at both cluster and customer levels. Once the two evolved new populations are obtained, a cooperative evolution mechanism is applied to obtain a new population. Extensive experiments on 404 benchmark instances show that the proposed algorithm significantly outperforms the current state-of-the-art algorithms. In particular, the proposed algorithm discovers new upper bounds for 16 out of the 26 large-sized benchmark instances, while matching the best-known solutions for the remaining 9 large-sized instances. Ablation experiments are conducted to verify the effectiveness of each key algorithmic module. Finally, the inherent generality of the proposed method is verified by applying it to the well-known (hard) clustered vehicle routing problem.

Keywords: Combinatorial optimization; Vehicle routing; Memetic computation; Cooperative evolution; Metaheuristic (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725001444
Full text for ScienceDirect subscribers only

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:eee:ejores:v:324:y:2025:i:3:p:825-838

DOI: 10.1016/j.ejor.2025.02.021

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().