Diversification and reoptimization procedures in column generation for the resolution of the acyclic vehicle routing problem with time windows

International audienceThis paper focuses on accelerating strategies in a Column Generation (CG) algorithm. In order to decrease the total number of generated columns and then, master problems resolution time, pricing problems solutions are made of task-disjoint columns. This can be achieved by diversification methods. Another way to improve CG computing time is to use reoptimization approaches to solve efficiently the pricing problems. We show in this work that diversification approaches are more efficient when applied on the first iterations to build efficiently a good approximation of pricing problems convex hull and that reoptimization methods are more efficient when applied on the last iterations when the dual variables are close. We combine a diversification technique and a reoptimization procedure in a CG scheme to improve the global resolution time. This study is validated on the Vehicle Routing Problem with Time Windows (VRPTW), defined on acyclic networks