A Vehicle Routing Problem with Time Windows and Shift Time Limits | Irina Kupriyanova
| | Abstract | In this thesis a vehicle routing problem with time windows and shift time limits is investigated. An additional specific feature of the problem is a non homogeneous fleet with a limited number of vehicles of each type.
A two-phase solution method is developed and implemented. The first phase deals with construction of a large set of good quality routes. In the second phase a Lagrangian heuristic is used to solve a mixed set covering/packing problem where columns of the constraint matrix correspond to the routes generated in the first phase.
The developed solution approach is tested on a number of problems of different size. The computational results show that optimal solutions can be found for the set covering/packing problems of small size, i.e. 120 rows and up to 500 columns. As the problem size increases the performance of the Lagrangian heuristic becomes worse. | | Keywords | Vehicle routing, time windows, shift time limits, Lagrangian relaxation, set covering, set packing. | | Type | Master's thesis [Academic thesis] | | Year | 2006 | | Publisher | Informatics and Mathematical Modelling, Technical University of Denmark, DTU | | Address | Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby | | Series | IMM-Thesis-2006-33 | | Note | Supervised by Jesper Larsen, IMM. | | Electronic version(s) | [pdf] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|