Paper Info
Title
An Effective Local Search Algorithm for the Multidepot Cumulative Capacitated Vehicle Routing Problem
Abstract
The cumulative capacitated vehicle routing problem (CCVRP) focuses on minimizing the sum of arrival times at the customers. An important application of the CCVRP arises in the procurement of humanitarian aid when natural disasters occur. In this article, the multidepot CCVRP (MDCCVRP) is investigated, and its mathematical model is developed. Moreover, an effective perturb-based local search (PLS) algorithm is proposed to solve the problem. The proposed PLS algorithm starts from having a feasible solution. Regarding the PLS, the perturbing operators help to explore the searching space, while the six local search operators help to exploit the best solution within each searching basin. To test the performance, the proposed PLS is applied to a set of standard benchmark instances and compared with the recently published algorithms. Extensive computational studies reveal that the proposed PLS algorithm is able to attain better solutions with less computational time for most testing instances, and thus competes very favorably with the previously proposed approaches. A stability analysis is also presented to shed light on the robust behavior of the proposed algorithm. The results of the two-sided Wilcoxon rank sum tests clearly show that the algorithms (our PLS and other published methods) have performed with statistically significant differences.
Year
DOI
Venue
2020
10.1109/TSMC.2019.2938298
IEEE Transactions on Systems, Man, and Cybernetics: Systems
Keywords
DocType
Volume
Humanitarian aid,local search,multidepot cumulative capacitated vehicle routing problem (MDCCVRP),perturbing operator
Journal
50
Issue
ISSN
Citations 
12
2168-2216
1
PageRank 
References 
Authors
0.35
0
4
Name
Order
Citations
PageRank
Zhigang Yu171.80
Tsan-Ming Choi2104075.03
Zhiying Li310.35
Shuai Shao471.10