A Scalable Approach to Capacitated Arc Routing Problems Based on Hierarchical Decomposition

Ke Tang, Juan Wang, Xiaodong Li, Xin Yao

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)
285 Downloads (Pure)


The Capacitated Arc Routing Problem (CARP) is a challenging optimization problem with lots of applications in the real world. Numerous approaches have been proposed to tackle this problem. Most of these methods, albeit showing good performance on CARP instances of small and median sizes, do not scale well to large-scale CARPs, e.g., taking at least a few hours to achieve a satisfactory solution on a CARP instance with thousands of tasks. In this paper, an efficient and scalable approach is proposed for CARPs. The key idea of the proposed approach is to hierarchically decompose the tasks involved in a CARP instance into sub-groups and solve the induced sub-problems recursively. The output of the sub-problems at the lower layer in the hierarchy is treated as virtual tasks and new sub-problems are formulated based on these virtual tasks using clustering techniques. By this means, the number of tasks (or virtual tasks) decreases rapidly from the bottom to the top layers of the hierarchy, and the sizes of all sub-problems at each layer can be kept tractable even for very large-scale CARPs. Empirical studies are conducted on CARP instances with up to 3584 tasks, which are an order of magnitude larger than the number of tasks involved in all CARP instances investigated in the literature. The results show that the proposed approach significantly outperforms existing methods in terms of scalability. Since the proposed hierarchical decomposition scheme is designed to obtain a good permutation of tasks in a CARP instance, it may also be generalized to other hard optimization problems that can be formulated as permutation-based optimization problems.
Original languageEnglish
Pages (from-to)1-13
JournalIEEE Transactions on Cybernetics
Issue number99
Early online date4 Aug 2016
Publication statusE-pub ahead of print - 4 Aug 2016


Dive into the research topics of 'A Scalable Approach to Capacitated Arc Routing Problems Based on Hierarchical Decomposition'. Together they form a unique fingerprint.

Cite this