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 |
| _version_ | 1819237767667777536 |
|---|---|
| author | Hadi Karimi Abbas Seifi |
| author_facet | Hadi Karimi Abbas Seifi |
| author_sort | Hadi Karimi |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-23T13:25:34Z |
| format | Article |
| id | doaj.art-2acb428ba8164083a8aa313d19fe53a0 |
| institution | Directory Open Access Journal |
| issn | 2008-4889 2345-363X |
| language | English |
| last_indexed | 2024-12-23T13:25:34Z |
| publishDate | 2012-11-01 |
| publisher | Iran University of Science & Technology |
| record_format | Article |
| series | International Journal of Industrial Engineering and Production Research |
| spelling | doaj.art-2acb428ba8164083a8aa313d19fe53a02022-12-21T17:45:18ZengIran University of Science & TechnologyInternational Journal of Industrial Engineering and Production Research2008-48892345-363X2012-11-01234309315Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time WindowsHadi Karimi0Abbas Seifi1 Amirkabir Uni. Amirkabir Uni. 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.http://ijiepr.iust.ac.ir/browse.php?a_code=A-10-536-1&slc_lang=en&sid=1lagrangian relaxation vehicle routing problem with time windows analytic center cutting plane method |
| spellingShingle | Hadi Karimi Abbas Seifi Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows International Journal of Industrial Engineering and Production Research lagrangian relaxation vehicle routing problem with time windows analytic center cutting plane method |
| title | Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows |
| title_full | Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows |
| title_fullStr | Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows |
| title_full_unstemmed | Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows |
| title_short | Acceleration of Lagrangian Method for the Vehicle Routing Problem with Time Windows |
| title_sort | acceleration of lagrangian method for the vehicle routing problem with time windows |
| topic | lagrangian relaxation vehicle routing problem with time windows analytic center cutting plane method |
| url | http://ijiepr.iust.ac.ir/browse.php?a_code=A-10-536-1&slc_lang=en&sid=1 |
| work_keys_str_mv | AT hadikarimi accelerationoflagrangianmethodforthevehicleroutingproblemwithtimewindows AT abbasseifi accelerationoflagrangianmethodforthevehicleroutingproblemwithtimewindows |