A New Method for Generating Initial Solutions of Capacitated Vehicle Routing Problems

Abstract

In vehicle routing problems, the initial solutions of the routes are important for improving thequality and solution time of the algorithm. For a better route construction algorithm, theobtained initial solutions must be basic, fast, and flexible with reasonable accuracy. In thisstudy, initial solutions are introduced to improve the final solution of the Capacitated VehicleRouting Problem based on a method from the literature. Using a different formula foraddressing the gravitational forces, a new method is introduced and compared with the previousphysics inspired algorithm. By using the initial solutions of the proposed method and usingthem as the initial routes of the Record-to-Record and Simulated Annealing algorithms, it isseen that better results are obtained when compared with various algorithms from the literature.Also, in order to fairly compare the algorithms executed on different machines, a newcomparison scale for the solution quality of vehicle routing problems is proposed that dependson the solution time and the deviation from the best known solution. The obtained initialsolutions are then input to Record-to-Record and Simulated Annealing algorithms to obtainfinal solutions. Various test instances and CVRP solutions from the literature are used forcomparison. The comparisons with the proposed method have shown promising results.