We show in this paper how set partitioning formulation and column generation techniques can be used to model and solve to optimality large scale vehicle routing problems with special structure. Often it is possible to solve quite large instances of a classical problem, but the extension to the resolution of constrained version of these problems is very difficult. The main contribution of this paper is to show that the approach based upon the use of the set partitioning formulation and the column generation techniques yields very good results for complex and realistic vehicle routing problems.