Efficient frameworks for greedy split and new depth first search split procedures for routing problems

International audienceSplit procedures have proven their efficiency within global optimization frameworks for routing problems by splitting giant tours into trips. This is done by generating an optimal shortest path within an auxiliary graph constructed from the giant tour. This article provides a state of the art of split practice in routing problems and gives its key features. The efficiency of the method critically depends on the node-splitting procedure and on the upper and lower bound approximations. Suitable complexity can be obtained using a new depth first search procedure which is introduced here and provides a new algorithm that is specially designed for large scale problems with resource constraints. Experiments show that the depth first search split procedure introduced in this article, used as an evaluation function in a global framework, can improve the results obtained by the use of the “classical” split procedure on the Location-Routing Problem and the Heterogeneous Vehicle Routing Problem. The Location-Routing Problem is also used to provide further analysis and a fair comparative study between the two split versions