A proposed framework is specialized for large scale vehicle routing problems (VRPs) and based on problem decomposition and gradual restoration mechanisms to perform more efficiently search. First mechanism is used to break a large scale problem into small size sub-problems and second one is to restore these to original state gradually. These mechanisms having contradictory features can be expected to work efficiently in large scale problem having more than hundreds. Firstly, an original large scale problem is divided into some small sub-areas and optimal solutions in each sub-area are derived. When a best incumbent solution remains unchanged for a certain period, sub-problems are gradually integrated and new optimal solutions in a new integrated sub-problem are re-searched through use of the obtained solutions in previous sub problems. This gradual integration and optimization would be iterated until all sub-problems are integrated into the one (the original problem), and the optimal solution of original problem can be obtained in the overall integrated which is same as original problem. Through some typical test problems from Cordeau's instances, it was demonstrated that the proposed framework could derive better results more effectively than conventional one.