A new efficient approach for solving the capacitated Vehicle Routing Problem using the Gravitational Emulation Local Search Algorithm

Capacitated Vehicle Routing Problem (CVRP) is one of the most famous specialized forms of the VRP, which has attracted considerable attention from scientists and researchers. Therefore, many accurate, heuristic, and meta-heuristic methods have been introduced to solve this problem in recent decades. In this paper, a new meta-heuristic optimization algorithm is introduced to solve the CVRP, which is based on the law of gravity and group interactions. The proposed algorithm uses two of the four basic parameters of velocity and gravitational force in physics based on the concepts of random search and searching agents, which are a collection of masses that interact with each other based on Newtonian gravity and the laws of motion. The introduced method was quantitatively compared with the State-of-the-Art algorithms in terms of execution time and number of optimal solutions achieved in four well-known benchmark problems. Our experiments illustrated that the proposed method could be a very efficient method in solving CVRP and the results are comparable with the results using state-of-the-art computational methods. Moreover, in some cases our method could produce solutions with less number of required vehicles compared to the Best Known Solution (BKS) in a very efficient manner, which is another advantage of the proposed algorithm.