A scalable approach to capacitated arc routing problems based on hierarchical decomposition

Ke TANG, Juan WANG, Xiaodong LI, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

46 Citations (Scopus)

Abstract

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 subgroups and solve the induced subproblems recursively. The output of the subproblems at the lower layer in the hierarchy is treated as virtual tasks and new subproblems 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 subproblems 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. © 2013 IEEE.
Original languageEnglish
Article number7533424
Pages (from-to)3928-3940
Number of pages13
JournalIEEE Transactions on Cybernetics
Volume4.70E+01
Issue number11
Early online date4 Aug 2016
DOIs
Publication statusPublished - Nov 2017
Externally publishedYes

Keywords

  • Capacitated arc routing problem (CARP)
  • Clustering
  • combinatorial optimization
  • hierarchical decomposition (HD)
  • Scalability

Fingerprint

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