Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem
EXPERT SYSTEMS WITH APPLICATIONS, vol.61, pp.28-38, 2016 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 61
- Publication Date: 2016
- Doi Number: 10.1016/j.eswa.2016.05.023
- Journal Name: EXPERT SYSTEMS WITH APPLICATIONS
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Page Numbers: pp.28-38
- Keywords: Capacitated vehicle routing problem, Hybrid meta-heuristic, Large neighbourhood search, Ant colony optimization
- Dokuz Eylül University Affiliated: Yes
Abstract
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. (C) 2016 Elsevier Ltd. All rights reserved.