A hybrid approach of ALNS with alternative initialization and acceptance mechanisms for capacitated vehicle routing problems

Kuyu Y. C., Vatansever F.

CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS, cilt.27, sa.10, ss.13583-13606, 2024 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 27 Sayı: 10
  • Basım Tarihi: 2024
  • Doi Numarası: 10.1007/s10586-024-04643-9
  • Dergi Adı: CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC
  • Sayfa Sayıları: ss.13583-13606
  • Anahtar Kelimeler: Adaptive large neighborhood search, Capacitated vehicle routing, Matching algorithm, Saving algorithm, Sequential route-building algorithm, Sweep algorithm
  • Bursa Uludağ Üniversitesi Adresli: Evet

Özet

The vehicle routing problem (VRP) with capacity constraints is a challenging problem that falls into the category of non-deterministic polynomial-time hard (NP-hard) problems. Finding an optimal solution to this problem is difficult as it involves numerous possible route combinations and constraints. The Adaptive Large Neighborhood Search (ALNS) has been widely employed to solve VRPs by searching for optimal solutions using a variety of dynamic destroy and repair operators, which gradually improve the initial solution. This study investigates six alternative initialization mechanisms and one distinct acceptance criterion for ALNS as the selection of an initial solution in ALNS is a crucial factor affecting the efficiency of the search for feasible regions. The process combines ALNS with the aforementioned procedures, resulting in a hybrid of seven methods. To evaluate the performance of the initialization mechanism and acceptance criterion in ALNS, 50 capacitated vehicle routing benchmark instances are employed. High-dimensional problems are also included for more comprehensive analysis. The improvement in the accuracy of the solutions achieved by each variant is reported.