Download PDFOpen PDF in browserA GRASP Hybrid Genetic Algorithm for the Capacitated Vehicle Routing ProblemEasyChair Preprint 461116 pages•Date: November 19, 2020AbstractThe vehicle routing problem is an interesting and challenging combinatorial problem, study for over more than fifty years since Dantzig and Ramser. Several researches have been conducted on this problem and its variants generating many approaches including the population-based one. In this study, we present a Grasp Hybrid Genetic Algorithm (GHGA) to solve the Capacitated Vehicle Routing Problem (CVRP). Our approach combines the efficiency of the well-known Travel Salesman Problem crossovers with a proposed Partial Intensification Mechanism (PIM), which is a combination of a modified 2-opt local movement and the Split algorithm. Additionally, we present the Neighborhood Perturbation Mechanism (NEP). Inspired in the perturbation phase of the Large Neighborhood Search, we inserted destroy-repair operators with an adaptive use of degradation ratio. Experiments were conducted on well-known Christofides et al. benchmark supporting that our approach has interesting points and it is a promising approach Keyphrases: Capacitated Vehicle Routing Problem, Metaheuristic, Optimization, hybrid genetic algorithm
|