Abstract
The recently proposed Scalable Approach Based on Hierarchical Decomposition (SAHiD) has shown its superiority on large-scale capacitated arc routing problems (CARP) in terms of both computational efficiency and solution quality. The main idea of SAHiD is that the underlying Hierarchical decomposition (HD) scheme is able to efficiently obtain a good permutation of tasks for CARP in a hierarchical divide-and-conquer way, where both the number and size of subproblems can be kept in tractable for large-scale problems with thousands of tasks. Motivated by the frequent observations of the similarity between CARP and Capacitated Vehicle Routing Problem (CVRP), the HD scheme and SAHiD algorithm are expected to work well on CVRPs. This paper applies SAHiD to large-scale CVRPs and discovers that SAHiD does not work as well as expected on large-scale CVRP. Possible reasons for this are given after extensive experimental studies. Two directions for improving SAHiD on large-scale CVRP are pointed out. © 2019 IEEE.
| Original language | English |
|---|---|
| Title of host publication | 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 1195-1202 |
| Number of pages | 8 |
| ISBN (Print) | 9781728121536 |
| DOIs | |
| Publication status | Published - Jun 2019 |
| Externally published | Yes |
Bibliographical note
This work was supported by National Key R&D Program of China (Grant No. 2017YFC0804003), the Natural Science Foundation of China (61806090 and 61672478), Shenzhen Peacock Plan (Grant No. KQTD2016112514355531), the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008), and the Science and Technology Innovation Committee Foundation of Shenzhen (Grant Nos. JCYJ20170307105521943, JCYJ20170817112421757, JCYJ20180504165652 917).Keywords
- Capacitated vehicle routing problem (CVRP)
- comparative study
- hierarchical decomposition