Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem

One of the best heuristic algorithms for solving the capacitated vehicle routing problem is a hybrid genetic search. A critical component of the search is a splitting procedure, where a solution encoded as a giant tour of nodes is optimally split into vehicle routes using dynamic programming. However, the current state-of-the-art implementation of the splitting procedure assumes that the start of the giant tour is fixed as a part of the encoded solution. This paper examines whether the fixed starting point is a significant drawback. Results indicate that simple adjustments of the starting point for the splitting procedure can improve the performance of the genetic search, as measured by the average primal gaps of the final solutions obtained, by 3.9%.