An Application of a Modified Metaheuristic Algorithm for Solving Capacitated Vehicle Routing Problems

Source abstract

The vehicle routing problem is one of the most often studied optimization problems. In this study, an improved artificial bee colony (ABC) algorithm is proposed which is structured specifically to address the capacitated vehicle routing problem (CVRP), a significant challenge in combinatorial optimization. The proposed algorithm integrates several novel features to improve its performance on CVRP instances. These include a unique initialization strategy that spreads non-repeated customers during initialization, an innovative dual group strategy in the employed bee phase, and an improved scout bee phase with perturbation techniques. Additionally, the proposed algorithm effectively handles infeasible solutions using a novel penalty function formula. The Chebyshev Minkowski’s distance is utilized for route evaluation, enhancing spatial relationship representation over traditional Euclidean distances. Moreover, the classical CVRP model is extended by introducing new variables and constraints to capture changing demand at each customer location within a route. The algorithm’s efficiency was extensively evaluated using benchmark data sets comprising 73 instances from data sets A, B, and P sourced from the VRP instances library site. This rigorous testing enables comprehensive assessments and meaningful comparisons with other algorithms. Overall, the proposed ABC algorithm offers a promising solution for addressing CVRP challenges, providing advancements in solution quality, robustness, and adaptability. Finally, the optimal results are compared in terms of their statistical significance using Friedman and Wilcoxon rank tests with three well-known optimizer algorithms in the literature.