H. Karimi - Department of Industrial Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran
A. Seifi - Department of Industrial Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran

The analytic center cutting plane method (ACCPM) is one of successful methods to solve nondifferentiable optimization problems. In this paper, ACCPM is used to accelerate Lagrangian relaxation procedure for solving a vehicle routing problem with time windows (VRPTW). First, a basic cutting plane algorithm and its relationship with a column generation technique is clarified. Then, the proposed method based on ACCPM is explained as a stabilization technique for Lagrangian relaxation. Both approaches are tested on a benchmark instance to demonstrate the advantages of the proposed method in terms of computational time and quality of lower bounds.

lagrangian relaxation, vehicle routing problem with time windows, analytic center cutting plane method