Wang X.TSAN MING CHOILi Z.Shao S.2022-05-302022-05-302020https://www.scopus.com/inward/record.uri?eid=2-s2.0-85096648620&doi=10.1109%2fTSMC.2019.2938298&partnerID=40&md5=0df18f4522e7ecafd33f11fdebc93b36https://scholars.lib.ntu.edu.tw/handle/123456789/612167The 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. ? 2013 IEEE.Humanitarian aid; local search; multidepot cumulative capacitated vehicle routing problem (MDCCVRP); perturbing operatorBenchmarking; Disasters; Routing algorithms; Vehicle routing; Capacitated vehicle routing problem; Computational studies; Computational time; Local search algorithm; Local search operators; Natural disasters; Statistically significant difference; Wilcoxon rank sum test; Local search (optimization)journal article10.1109/TSMC.2019.29382982-s2.0-85096648620