A bilevel hybrid iterated search approach to soft-clustered capacitated arc routing problems

Yangming Zhou, Chenhui Qu, Qinghua Wu, Yawen Kou, Zhibin Jiang and MengChu Zhou

Transportation Research Part B: Methodological, 2024, vol. 184, issue C

Abstract: This work studies a soft-clustered capacitated arc routing problem that extends the classical capacitated arc routing problem with an important constraint. The problem has a set of required edges (e.g., the streets to be serviced) that are partitioned into clusters. The constraint ensures that all required edges of the same cluster are served by the same vehicle. This problem can be found in a variety of practical applications, such as waste collection, postal delivery, snow plowing, and meter reading. Due to its non-deterministic polynomial-time hard nature, it is decomposed into capacitated vehicle routing problems at the cluster-level and rural postman problems at the edge-level, and then an effective bilevel hybrid iterated search method is proposed to solve it. The proposed method consists of a bilevel variable neighborhood search that sequentially executes a random order-based variable neighborhood descent at the cluster-level and a lower bound-guided variable neighborhood descent at the edge-level, and a similarity-driven hybrid perturbation that conditionally switches between a backbone-based directed perturbation and a destroy-repair random perturbation. Extensive evaluations on 611 existing benchmark instances show that the proposed method outperforms state-of-the-art algorithms in terms of both solution quality and computation time. Its excellent performance is also verified on 30 newly generated large instances that are derived from real-world road networks. Finally, ablation studies on key algorithmic components are performed to confirm their novelty and effectiveness.

Keywords: Capacitated arc routing; Metaheuristic; Variable neighborhood search; Iterated local search (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261524000687
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:transb:v:184:y:2024:i:c:s0191261524000687

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.102944

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().