PMID- 33531309
OWN - NLM
STAT- PubMed-not-MEDLINE
LR  - 20220720
IS  - 2168-2275 (Electronic)
IS  - 2168-2267 (Linking)
VI  - 52
IP  - 8
DP  - 2022 Aug
TI  - A Route Clustering and Search Heuristic for Large-Scale Multidepot-Capacitated 
      Arc Routing Problem.
PG  - 8286-8299
LID - 10.1109/TCYB.2020.3043265 [doi]
AB  - 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.
FAU - Zhang, Yuzhou
AU  - Zhang Y
FAU - Mei, Yi
AU  - Mei Y
FAU - Huang, Shihua
AU  - Huang S
FAU - Zheng, Xin
AU  - Zheng X
FAU - Zhang, Cuijuan
AU  - Zhang C
LA  - eng
PT  - Journal Article
DEP - 20220719
PL  - United States
TA  - IEEE Trans Cybern
JT  - IEEE transactions on cybernetics
JID - 101609393
SB  - IM
EDAT- 2021/02/04 06:00
MHDA- 2021/02/04 06:01
CRDT- 2021/02/03 05:47
PHST- 2021/02/04 06:00 [pubmed]
PHST- 2021/02/04 06:01 [medline]
PHST- 2021/02/03 05:47 [entrez]
AID - 10.1109/TCYB.2020.3043265 [doi]
PST - ppublish
SO  - IEEE Trans Cybern. 2022 Aug;52(8):8286-8299. doi: 10.1109/TCYB.2020.3043265. Epub 
      2022 Jul 19.