Bilevel Memetic Search Approach to the Soft-Clustered Vehicle Routing Problem

Yangming Zhou (), Yawen Kou () and MengChu Zhou ()
Additional contact information
Yangming Zhou: Data-Driven Management Decision Making Lab, Shanghai Jiao Tong University, Shanghai 200030, China; Sino-US Global Logistics Institute, Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, China; Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China
Yawen Kou: Department of Computer Science and Engineering, East China University of Science and Technology, Shanghai 200237, China
MengChu Zhou: Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China; Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, New Jersey 07102

Transportation Science, 2023, vol. 57, issue 3, 701-716

Abstract: This work addresses a soft-clustered vehicle routing problem that extends the classical capacitated vehicle routing problem with one additional constraint, that is, customers are partitioned into clusters and all customers of the same cluster must be served by the same vehicle. Its potential applications include parcel delivery in courier companies and freight transportation. Due to its NP-hard nature, solving it is computationally challenging. This paper presents an efficient bilevel memetic search method to do so, which explores search space at both cluster and customer levels. It integrates three distinct modules: a group matching-based crossover (to generate promising offspring solutions), a bilevel hybrid neighborhood search (to perform local optimization), and a tabu-driven population reconstruction strategy (to help the search escape from local optima). Extensive experiments on three sets of 390 widely used public benchmark instances are conducted. The results convincingly demonstrate that the proposed method achieves much better overall performance than state-of-the-art algorithms in terms of both solution quality and computation time. In particular, it is able to find 20 new upper bounds for large-scale instances while matching the best-known upper bounds for all but four of the remaining instances. Ablation studies on three key algorithm modules are also performed to demonstrate the novelty and effectiveness of the proposed ideas and strategies.

Keywords: vehicle routing problem; bilevel optimization; heuristic; memetic search; variable neighborhood 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.1186 (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:3:p:701-716

Access Statistics for this article

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