An Experimental Study of Large-scale Capacitated Vehicle Routing Problems

Zhuo, Er; Deng, Yunjie; Su, Zhewei; Yang, Peng; Yuan, Bo; Yao, Xin

10.1109/CEC.2019.8790042

2019

978-1-7281-2154-3

2019 IEEE Congress on Evolutionary Computation, CEC 2019

1195-1202

10-13 June 2019

Wellington, New zealand

345 E 47TH ST, NEW YORK, NY 10017 USA

Institute of Electrical and Electronics Engineers Inc.

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.

Capacitated vehicle routing problem (CVRP) hierarchical decomposition comparative study

第一 ; 通讯

英语

EI ; CPCI-S

Science and Technology Innovation Committee Foundation of Shenzhen[JCYJ20170307105521943]

Engineering ; Mathematical & Computational Biology

Engineering, Electrical & Electronic ; Mathematical & Computational Biology

WOS:000502087101029

20193507373835

Computational efficiency ; Vehicles

EV Compendex

Shenzhen Key Laboratory of Computational Intelligence, University Key Laboratory of Evolving Intelligent Systems of Guangdong Province, Southern University of Science and Technology, Shenzhen; 518055, China

Zhuo, Er,Deng, Yunjie,Su, Zhewei,et al. An Experimental Study of Large-scale Capacitated Vehicle Routing Problems[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:Institute of Electrical and Electronics Engineers Inc.,2019:1195-1202.