Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem

AKPINAR Ş.

EXPERT SYSTEMS WITH APPLICATIONS, cilt.61, ss.28-38, 2016 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 61
  • Basım Tarihi: 2016
  • Doi Numarası: 10.1016/j.eswa.2016.05.023
  • Dergi Adı: EXPERT SYSTEMS WITH APPLICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.28-38
  • Anahtar Kelimeler: Capacitated vehicle routing problem, Hybrid meta-heuristic, Large neighbourhood search, Ant colony optimization, ANT COLONY OPTIMIZATION, GENETIC ALGORITHM, HEURISTICS, DEPOT
  • Dokuz Eylül Üniversitesi Adresli: Evet

Özet

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.