Beta 1


Title A Vehicle Routing Problem with Time Windows and Shift Time Limits
Author Kupriyanova, Irina
Supervisor Larsen, Jesper (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2006
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.
Imprint Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU : DK-2800 Kgs. Lyngby, Denmark
Pages 148
Keywords Vehicle routing; time windows; shift time limits; Lagrangian relaxation; set covering; set packing.
Fulltext
Original PDF imm4650.pdf (1.00 MB)
Admin Creation date: 2006-10-06    Update date: 2012-12-18    Source: dtu    ID: 191649    Original MXD