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, vol.27, no.10, pp.13583-13606, 2024 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 27 Issue: 10
  • Publication Date: 2024
  • Doi Number: 10.1007/s10586-024-04643-9
  • Journal Name: CLUSTER COMPUTING-THE JOURNAL OF NETWORKS SOFTWARE TOOLS AND APPLICATIONS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC
  • Page Numbers: pp.13583-13606
  • Keywords: Adaptive large neighborhood search, Capacitated vehicle routing, Matching algorithm, Saving algorithm, Sequential route-building algorithm, Sweep algorithm
  • Bursa Uludag University Affiliated: Yes

Abstract

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.