An Effective Local Search Algorithm for the Multidepot Cumulative Capacitated Vehicle Routing Problem
Journal
IEEE Transactions on Systems, Man, and Cybernetics: Systems
Journal Volume
50
Journal Issue
12
Pages
4948-4958
Date Issued
2020
Author(s)
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. ? 2013 IEEE.
Subjects
Humanitarian aid; local search; multidepot cumulative capacitated vehicle routing problem (MDCCVRP); perturbing operator
Other Subjects
Benchmarking; 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)
Publisher
Institute of Electrical and Electronics Engineers Inc.
Type
journal article