A Survey on Genetic Algorithm for Vehicle Routing Problem

Abstract: A Vehicle routing problem (VRP) attracts much attention due to the increased interest in various geographical solutions and technologies as well as their usage in logistics and transportation. Many researches on different heuristic approaches can be found for the solution of the vehicle routing problem, where specific situations and constraints are analyzed. The common genetic algorithm approaches involve additional repair and improvement methods that are designed for a specific constraint to keep the generated solutions in the feasible search space. The usage of the repair and improvement methods designed for specific constraints or genetic operators specially designed for a specific problem can produce an inadequate result when they are applied to different problems. In this research we investigate genetic algorithm approaches for solving vehicle routing problem with different constraints. Due to stochastic characteristics, genetic algorithms generate solutions in the whole search space including the infeasible space. We propose a genetic algorithm based on a random insertion heuristics for the vehicle routing problem with constraints. The random insertion heuristic is used to construct initial solutions and to reconstruct the existing ones. The process of random insertion preserves stochastic characteristics of the genetic algorithm and preserves feasibility of generated individuals.

Keywords: Vehicle routing problem (VRP), genetic algorithm, VRPTW, VRPPD, MDVRP.