Refinements of the column generation process for the Vehicle Routing Problem with Time Windows |
Jesper Larsen
|
| Abstract | The Vehicle Routing Problem with Time Windows is a generalization of the well known capacity constrained Vehicle Routing Problem. A homogeneous fleet of vehicles has to service a set of the customers and fulfill their demands. The service of the customers can only start within a well-defined time interval denoted the time window. The objective is to determine routes for the vehicles that minimizes the accumulated cost (or distance) with respect to the above mentioned constraints. Currently the best approaches for determining optimal solutions are based on column generation and Branch-and-Bound, also known as Branch-and-Price. This paper presents two ideas for run-time improvements of the Branch-and-Price framework for the Vehicle Routing Problem with Time Windows. Both ideas reveal a significant potential for using run-time refinements when speeding up an exact approach without compromising optimality. |
| Keywords | Vehicle routing, time windows, column generation, shortest path, branch-and-bound |
| Type | Journal paper [With referee] |
| Journal | Journal of Systems Science and Systems Engineering |
| Year | 2004 Month September Vol. 13 No. 3 pp. 326-341 |
| ISBN / ISSN | ISSN 1004-3756 |
| BibTeX data | [bibtex] |
| IMM Group(s) | Operations Research |