文献类型：期刊文献

英文题名：A bilevel hybrid iterated search approach to soft-clustered capacitated arc routing problems

作者：Zhou, Yangming[1,2];Qu, Chenhui[3];Wu, Qinghua[3];Kou, Yawen[4];Jiang, Zhibin[1,2];Zhou, Mengchu[5]

机构：[1]Shanghai Jiao Tong Univ, Data Driven Management Decis Making Lab, Shanghai 200030, Peoples R China;[2]Shanghai Jiao Tong Univ, Sino US Global Logist Inst, Antai Coll Econ & Management, Shanghai 200030, Peoples R China;[3]Huazhong Univ Sci & Technol, Sch Management, Wuhan 430074, Peoples R China;[4]East China Univ Sci & Technol, Dept Comp Sci & Engn, Shanghai 200237, Peoples R China;[5]New Jersey Inst Technol, Dept Elect & Comp Engn, Newark, NJ 07102 USA

年份：2024

卷号：184

外文期刊名：TRANSPORTATION RESEARCH PART B-METHODOLOGICAL

收录：;EI(收录号：20242016099990);WOS:【SSCI(收录号:WOS:001242435400001)，SCI-EXPANDED(收录号:WOS:001242435400001)】；

基金：We would like to thank the anonymous referees for their helpful comments and suggestions, which helped us to improve the presentation of the work. This work was partially sponsored by the Major Projects of the National Social Sciences Fund of China (Grant No. 21&ZD128), the National Natural Science Foundation of China [Grant No. 72371157, 72122006], and the Shanghai Pujiang Programme [Grant No. 23PJC069].

语种：英文

外文关键词：Capacitated arc routing; Metaheuristic; Variable neighborhood search; Iterated local search

摘要：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 backbonebased 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.