A Hybrid K-Means and Particle Swarm Optimization Approach for Multi-Vehicle Routing Problems

The Vehicle Routing Problem (VRP) is one of the most fundamental and widely studied combinatorial optimization problems in transportation. It focuses on determining optimal routes for a fleet of vehicles to serve a set of geographically dispersed customers while satisfying operational constraints such as vehicle capacity, travel time, and service requirements. As an NP-hard problem, VRP becomes computationally intractable for large-scale instances, making meta-heuristic optimization techniques an effective and widely adopted solution. In this paper, a hybrid framework for solving the multi-vehicle routing problem is presented, which is developed based on spatial clustering and a particle swarm optimization algorithm with random key representation. In the proposed method, first, customers are divided into several clusters according to their location using the K-Means algorithm. Then, for each cluster, the customer visit route is determined independently using the PSO algorithm. To increase the quality of the responses, local search strategies have been used to improve the routes within each route and also between different routes. The objective function is defined as a multi-criteria one and includes factors such as total route length, time delay, and energy cost, while vehicle capacity constraints are also considered in the problem-solving process. To evaluate the performance of the proposed algorithm, the Solomon benchmark dataset is used. The results indicate that the proposed method is able to produce routes with satisfactory quality and acceptable convergence behavior. Overall, this framework can be used as an efficient and reliable approach for fleet planning in logistics and intelligent transportation systems.