Two-phase heuristic for Capacitated Vehicle Routing Problem

Vehicle Routing Problem (VRP) is a NP-complete problem and has important practical value. The Capacitated Vehicle Routing Problem (CVRP) constrained by the capacity of a vehicle is the extension of VRP. In this paper, a two-phase heuristic to address CVRP is proposed. The proposed heuristic has two stages. First, search feasible solution in the global scope using GA. Second, employ local search method to seeking the close-to-optimal solution in local scope. Through combining the global optimization ability of GA with the probability sudden jumping of local search algorithm, two-phase heuristic can solve the CVRP effectively. Furthermore, a set of well-known benchmarks were utilized to verify the performance of the proposed heuristic. The experimental results show that the best-so-far solution of the most of the test instances can be found.