Using Randomisation into Iterated Greedy algorithm in order to Solve Capacitated Vehicle Routing Problem

Abstract

In this paper, we develop a heuristic algorithm for solving a Capacitated Vehicle Routing Problem (CVRP). In general, VRP is a well-known problem in which a number of vehicles are located at a central depot; each vehicle has a limited capacity and has to serve a number of geographically dispersed customers whose actual demands are known in advance. The contribution of the paper is to implement the Clarke and Wright Saving (CWS) algorithm and Iterated Greedy (IG) algorithm that used in the research efforts. Our results show that both CWS and IG combined with randomisation is a powerful algorithm for the well-known benchmark instances problem. Also, the proposed methodology is capable of finding useful trade-off solutions for the problem. We report the best solutions for 55 instances. Therefore, the results obtained are quite competitive when compared to the other algorithms found. Also, the results at best have been highly promising and useful for decision makers.