Replicating and extending meta heuristics for the capacity separation problem in the CVRP

An important step in approaching optimal solutions for the Capacitated Vehicle Routing Problem (CVRP) is finding a strong lower bound. The tabu search method provided by Augerat et al. (1998) was presented to be powerful heuristic when applied to solve the capacity separation problem in the cutting plane algorithm which iteratively solves a relaxed sub problem of the complete formulation of the CVRP. Our research verifies their computational findings can be replicated to a strong degree and confirms the methods presented in their paper. Furthermore, we propose another meta heuristics to tackle the capacity separation problem based on the Non- dominated Sorting Genetic Algorithm (NSGA). Although the algorithm does not turn out to outperform previous heuristics, we do find that when combined with the constructive heuristic, it matches the performance of the tabu heuristics requiring a smaller number of cuts. Finally, we change the cutting plane algorithm from an iterative solver to a dynamic variant in which the cut graphs of candidate solutions are passed to the separation phase through callback functions. This alternative approach leads improved lower bounds at a lower computation cost.