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 the vehicle routing problem with time windows (VRPTW) to accelerate lagrangian relaxation procedure for the problem. At fi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Iran University of Science & Technology
2012-11-01
|
| Series: | International Journal of Industrial Engineering and Production Research |
| Subjects: | |
| Online Access: | http://ijiepr.iust.ac.ir/browse.php?a_code=A-10-536-1&slc_lang=en&sid=1 |
| Summary: | 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 the vehicle routing problem with time windows (VRPTW) to accelerate lagrangian relaxation procedure for the problem. At first 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 of column generation (lagrangian relaxation). Both approaches are tested on a benchmark instance to demonstrate the advantages of proposed method in terms of computational time and lower bounds quality. |
|---|---|
| ISSN: | 2008-4889 2345-363X |