  Split procedures have been proved to be efficient within global framework
optimization for routing problems by splitting giant tour into trips. This is
done by generating optimal shortest path within an auxiliary graph built from
the giant tour. An efficient application has been introduced for the first time
by Lacomme et al. (2001) within a metaheuristic approach to solve the
Capacitated Arc Routing Problem (CARP) and second for the Vehicle Routing
Problem (VRP) by Prins (2004). In a further step, the Split procedure embedded
in metaheuristics has been extended to address more complex routing problems
thanks to a heuristic splitting of the giant tour using the generation of
labels on the nodes of the auxiliary graph linked to resource management.
Lately, Duhamel et al. (2010) defined a new Split family based on a depth first
search approach during labels generation in graph. The efficiency of the new
split method has been first evaluated in location routing problem with a GRASP
metaheuristic. Duhamel et al. (2010) provided full numerical experiments on
this topic.
