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

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.