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 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.