Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem |
| |
| Affiliation: | 1. Faculty of Electrical Engineering, Warsaw University of Technology, Koszykowa 75, Warsaw, Poland;2. Military Institute of Medicine, Szaserow 128, Warsaw, Poland;3. Military University of Technology, Kaliskiego 2, Warsaw, Poland;1. Faculty of Mathematics and Mechanics, Saint Petersburg State University, Universitetsky prospekt, 28, 198504 St. Petersburg, Russia;2. Faculty of Mathematics and Mechanics, and Research Laboratory for Analysis and Modeling of Social Processes, Saint Petersburg State University, Universitetsky prospekt, 28, 198504 St. Petersburg, Russia;3. Department of Probability and Statistics, Charles University, Prague, Czech Republic;4. Software Engineering Department, ORT Braude College of Engineering, Karmiel 21982, Israel |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
