Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows

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

Keywords:

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