Relaxation induced methods based on column generation for vehicle routing problems

We address an hybrid method for the vehicle routing problem that combines column generation, branch-and-bound and relaxation based heuristics. In particular, we combine the hybrid linear programming based algorithm proposed by Hanafi and Wilbaut [3] for mixed integer programming problems with branch-and-price. The heuristics proposed in [3] are convergent. They consist of solving iteratively the linear relaxation of the problem, and in deriving lower and upper bounds. The linear relaxation model within the proposed exact algorithm corresponds to the well-known column generation model. Preliminary computational results are reported