Solving Capacitated Vehicle Routing Problem by Iterated Greedy (IG) algorithm

Abstract

One of most significant logistics problems in the field of transportation and distribution is the Capacitated Vehicle Routing Problem (CVRP). The VRP has received particular attention for many years. In general, the problem considers the vehicles routing with limited capacity from a central depot to a set of geographically dispersed customers, where real (actual) demand of each customer is independent and known in advance. To the best of our knowledge, there is no research reported in the literature that combines CWS and IG in order to solve the CVRP. Also, safety stock and reloading/restocking have been considered in order to minimize the total cost of the problem. The contribution of the paper is to compare the CWS with IG. Also, the methodology includes two stages. In the first stage, optimal a-priori routes are generated using CWS and then the methodology has been extended by applying IG algorithm. In addition, when a vehicle capacity is exceeded, recourse actions have to be planned/designed to ensure the feasibility of solutions in case of route failure. In conclusion, our computational experiments on benchmark instances show that the IG is able to generate better solutions than CWS.