A Comparative Analysis of Metaheuristic Algorithms for the Constrained Vehicle Routing Problem

Abstract

Introduction. Vehicle routing is aproblem in transportlogistics that boils down to finding optimal movement trajectories for afleet of vehicles from asingle depot. It belongs to the NP-hard class of problems, which makes exactalgorithms inapplicableas the number of customers grows. The goal of this study is to conductacomparativeanalysis of metaheuristic algorithms for the constrained vehicle routing problem and to find the optimal conditions for their application. Materials and Methods. The classical greedy algorithm, theant colony optimization algorithm, and amodified genetic algorithm with an adaptive mutation mechanism are compared. The testing is carried out on five scenarios of varying sizes, simulating real-world logistics conditions. The evaluation is based on three criteria: total distance, calculation time, and compliance with all constraints, which makes it possible to identify the strengths of each algorithm under different conditions. Results. On small and medium-sized problems, both metaheuristic methods achieved the same optimal result, with theant colony algorithm being faster on average. However, in the most complex scenario, the genetic algorithm with adaptive mutation outperformed theantalgorithm both in terms of routelength and computation time, demonstrating better scalability and stability under strict constraints. Conclusion. The greedy algorithm demonstrated the maximum speed, but in 40% of cases it violated the constraints. Theantalgorithm works quickly on small tasks, but slows down and performs poorly on complex tasks. The genetic algorithm showed 100% feasible routes in all scenarios, the shortest total length, and excellent scalability. Thus, theant colony algorithm is preferable for quickly solving small-scale problems, while the proposed modified genetic algorithm provides the best balance of speed and quality.