A meta-genetic algorithm for solving the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is a widely studied, NP-hard problem with many real-world applications. Exact approaches are infeasible for solving large problem instances, due to the superpolynomial time complexity. Therefore, most solution approaches over the years have been metaheuristics, such as the Genetic Algorithm (GA). This paper presents a Hybrid GA, which incorporates problem-specific heuristics and domain knowledge into the algorithm. This causes the parameter settings to behave slightly different from regular GAs. To take care of the parameterization, an additional GA is used, acting on the Hybrid GA. This will be referred to as the Meta-GA. In addition to solving all known problems optimally or within 1% of the optimum, it manages to find a new best result within research literature for M-n200-k16, one of the largest problem instances.