Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem

Abstract

One of the most often researched optimization issues is the vehicle routing problem. It is categorized as an NP-hard problem with high time complexity. In this study, a novel hybrid technique, named as GA-RR, is developed to tackle capacitated vehicle routing problem. The algorithm is developed by hybridizing two well-known techniques: ruin and recreate algorithm as well as genetic algorithm. The algorithm aims at generating high-quality solutions for different test instances of vehicle routing problem. The suggested algorithm's performance is evaluated on 34 benchmark instances. The outcomes are also compared with some of the other state-of-the-art techniques. The proposed algorithm performance is superior compared to the state-of-the-art algorithms on the existing benchmark instances. The reason behind the superior performance of GA-RR is that the solutions produced by the genetic algorithm are further refined during the ruin and recreate phase of the hybridized approach. Additionally, this study analyzes the exploration-exploitation balance of the suggested algorithm.

Keywords

• Genetic algorithm
• Ruin and recreate
• Vehicle routing problem
• Optimization