- November 20, 2007 - 16:00
- ZLC, Lecture Room A1
Prof. Oli Madsen
Centre for Traffic and Transport, at the Technical University of Denmark
“Time Window Constrained Vehicle Routing Problems – Survey and Recent Developments”
This paper surveys some recent optimization 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. We assume that the time window is hard, i.e. if a vehicle arrives too early, the vehicle must wait until the time window opens, and it is not allowed to arrive late. In the case of soft time windows these can be violated, but then a penalty is imposed. The VRPTW appears in many real life situations, for example deliveries to supermarkets, bank and postal deliveries, industrial refuse collection, school bus routing, security patrol service, and urban newspaper distribution. Approximate methods such as metaheuristics will be mentioned but focus will be on exact methods such as decomposition, Lagrangean relaxation, and Branch and Cut. 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 the director of and professor at Centre for Traffic and Transport (CTT) 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 received a senior doctorate degree (dr.technices) in Transport Optimisation from DTU.
Professor Madsens main research interests lies within optimisation of transport systems in particular multi modal transport systems, vehicle routing, crew scheduling, and maritime logistics.
Apart from DTU Oli B.G. Madsen has spent a few semesters teaching and doing research at Massachusetts Institute of Technology (USA) and at University of Auckland (New Zealand).