A Route Clustering and Search Heuristic for Large-Scale Multidepot-Capacitated Arc Routing Problem
针对大规模多车场容量受限弧路径问题，提出一种迭代改进启发式算法，通过路径切割与聚类分解为单车场子问题并求解，在大型算例上显著优于现有方法。
The capacitated arc routing problem (CARP) has attracted much attention for its many practical applications. The large-scale multidepot CARP (LSMDCARP) is an important CARP variant, which is very challenging due to its vast search space. To solve LSMDCARP, we propose an iterative improvement heuristic, called route clustering and search heuristic (RoCaSH). In each iteration, it first (re)decomposes the original LSMDCARP into a set of smaller single-depot CARP subproblems using route cutting off and clustering techniques. Then, it solves each subproblem using the effective Ulusoy's split operator and local search. On one hand, the route clustering helps the search for each subproblem by focusing more on the promising areas. On the other hand, the subproblem solving provides better routes for the subsequent route cutting off and clustering, leading to better problem decomposition. The proposed RoCaSH was compared with the state-of-the-art MDCARP algorithms on a range of MDCARP instances, including different problem sizes. The experimental results showed that RoCaSH significantly outperformed the state-of-the-art algorithms, especially for the large-scale instances. It managed to achieve much better solutions within a much shorter computational time.