A GRASP Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem

EasyChair Preprint 4611

Abstract

The 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

@booklet{EasyChair:4611,
  author    = {Alexander F. Rego and Aurora T. R. Pozo},
  title     = {A GRASP Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem},
  howpublished = {EasyChair Preprint 4611},
  year      = {EasyChair, 2020}}