Optimizing the Number of Trucks for Handling the Capacited VRP Using the Max Stable Set Problem and Elbow Method

Determining the number of trucks used in the formulation of Capacitated Vehicle Routing Problem (CVRP) requires a thorough assessment of various factors, including cost, vehicle capacities, and problem-specific optimization objectives. In this work, we propose a new approach to determine the best number of trucks which is a parameter key used in the CVRP formulation before solving it. Within this approach, we aim to specify, for each CVRP problem, the suitable number of trucks which take into account several operational considerations such as capacity and cost of each truck... This approach is based mainly on the Maximum Stable Set Problem and an improved K-means algorithm. Compared with the classical solving method on a real data, this approach is consistently outperforms the classical method which use original data regarding the optimal value of the objective, quality of the solution, and the execution time of the solving algorithm.