A three-stage hybrid heuristic algorithm for the capacitated vehicle routing problem. (c2016)

Abstract

In the Vehicle Routing Problem (VRP) we are given a set of demands that need to be delivered to a specified list of customers, and we are asked to assign vehicles to deliver the demands so that the corresponding cost of routes is minimized. The problem received great attention due to its many applications in various fields such as logistics and transportation. Different types of the VRP have been proposed such as the Capacitated Vehicle Routing Problem (CVRP), where a designated single depot contains identical vehicles and the objective is to minimize the number of vehicles and the time taken for delivery, provided the total demand of supplies per vehicle does not exceed its capacity. CVRP is a well-known NP-complete problem. We consider heuristic methods that are based on two-phase algorithms. Each such algorithm starts by clustering the underlining network before proceeding into the route construction phase. We propose a three-stage hybrid heuristic approach consisting of a mixture of five algorithms that are run in parallel, differing only in the clustering stage. Experimental results on different benchmark datasets show that the proposed hybrid algorithm can outperform other existing heuristic methods, both in terms of number of vehicles and total distances traveled. In some cases, our algorithm found solutions that are better than the current best-known results, thereby breaking the records reported for some of the well-known benchmarks.