Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem

This paper presents a new hybrid algorithm that executes large neighbourhood search algorithm in combination with the solution construction mechanism of the ant colony optimization algorithm (LNS-ACO) for the capacitated vehicle routing problem (CVRP). The proposed hybrid LNS-ACO algorithm aims at enhancing the performance of the large neighbourhood search algorithm by providing a satisfactory level of diversification via the solution construction mechanism of the ant colony optimization algorithm. Therefore, LNS-ACO algorithm combines its solution improvement mechanism with a solution construction mechanism. The performance of the proposed algorithm is tested on a set of CVRP instances. The hybrid LNS-ACO algorithm is compared against two other LNS variants and some of the formerly developed methods in terms of solution quality. Computational results indicate that the proposed hybrid LNS-ACO algorithm has a satisfactory performance in solving CVRP instances.