An Experimental Study of Large-scale Capacitated Vehicle Routing Problems

Er ZHUO, Yunjie DENG, Zhewei SU, Peng YANG, Bo YUAN, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

1 Citation (Scopus)


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 languageEnglish
Title of host publication2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Print)9781728121536
Publication statusPublished - Jun 2019
Externally publishedYes

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).


  • Capacitated vehicle routing problem (CVRP)
  • comparative study
  • hierarchical decomposition


Dive into the research topics of 'An Experimental Study of Large-scale Capacitated Vehicle Routing Problems'. Together they form a unique fingerprint.

Cite this