The Vehicle Routing Problem with Time Windows

This paper surveys some recent solution methods and results in connection with the vehicle routing problem with time windows (VRPTW). The VRPTW is an extension of the classical capacity constrained vehicle routing problem. In the VRPTW the service at each customer must start within an associated time window. Both approximate and exact solution methods such as metaheuristics, decomposition, Lagrangean relaxation, and Branch and Cut will be mentioned. The computational results will be based on the Solomon test problems and the extended Solomon test problems with problem sizes up to 1000 customers.

Oli B.G. Madsen is director of and professor at CTT - Centre for Traffic and Transport - at the Technical University of Denmark (DTU). He obtained his M.Sc. in Electrical Engineering and Operations Research from DTU in 1967, and a Ph.D. in Operations Research from DTU in 1973. In 1998 he got a senior doctorate degree in Transport Optimisation from DTU. His main interests are optimisation of transport systems, vehicle routing, crew scheduling, and airline operations research. Apart from DTU Oli B.G. Madsen has spent a few semesters teaching and doing research at Massachusetts Institute of Technology and at University of Auckland.