# Where to Split in Hybrid Genetic Search for the Capacitated Vehicle Routing Problem
###### Abstract  
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%. vehicle routing problem; genetic algorithm; open source; genetic operator +
Footnote †: journal:  
0000  
0000-0001-581-581X]L.M. hybrid genetic search for solving the CVRP [10]. This implementation, and in particular how it deals with the splitting operator for converting a giant tour representation into feasible vehicle routes, is the focus of this paper. The implementation by [PERSON] [10] uses an order crossover (OX) to combine two existing solutions, represented as giant tours, and create a new solution represented as a giant tour. The operator works by randomly selecting two cutting points, splitting the combined giant tours into two segments. In the new solution, one segment is copied directly from the first combined giant tour, before completing the new giant tour by inserting the remaining customers in the order in which they appear in the second combined giant tour. [PERSON] [11] argued that this process is ineffective, as the order crossover inserts the remaining customers starting from the location in the second giant tour corresponding to the location where the copying of the first solution stopped. An adjusted order crossover (AOX) was proposed, where the insertion starts from the location in the second giant tour corresponding to the location of the customer that was last copied from the first giant tour. Figures 1 and 2 show a simple example of combining two giant tours with eight customers using the OX crossover and the AOX crossover, respectively. The grey area is the segment selected from the first combined giant tour. In the regular OX crossover, the next customer inserted in the new giant tour, following 3 and 4, is 8 (as it immediately follows the corresponding segment in the second giant tour), but with the AOX operator, the next customer inserted is 5, since it follows 4 in the second giant tour. This minor change led to an improved performance of the overall heuristic, reducing the primal gaps by 4.2%. After applying the order crossover, the next step is to consider the splitting procedure that takes as input the giant tour and provides as output a solution in the form of a set of vehicle routes. The splitting procedure is an example of the route-first cluster-second idea, and has become common when solving vehicle routing problems [12]. While [PERSON] [6] used it to solve CVRPs, it has been applied for a wide range of different vehicle routing problems, including with capacity and duration limits and time windows [8], with selection of customers to visit [13], or for heterogeneous fleets [14]. [PERSON] et al. [15] explored several variants of the splitting procedure for both the CVRP and the capacitated arc routing problem. The splitting procedure is typically implemented on an auxiliary graph where nodes correspond to customers and arcs correspond to routes. A standard dynamic program  
Figure 1: Example of the OX crossover applied to two permutation vectors (**left**), providing a new permutation vector (**right**). Figure 2: Example of the adjusted order crossover operator applied to two permutation vectors (**left**), providing a new permutation vector (**right**).