Groupe d’études et de recherche en analyse des décisions

G-92-42

Time Constrained Routing and Scheduling

, , et

This survey paper describes the significant advances made in time constrained vehicle routing and crew scheduling problems. In terms of solution methodology capable of solving realistic size problems, this field has seen a natural progression from ad-hoc methods to simple heuristics, to optimization-based heuristics and recently optimal algorithms. The paper provides an extensive overview of the algorithms developed and focuses on optimization methods. It first addresses fixed schedule problems and develops in detail the Dantzig-Wolfe decomposition/column generation approach which can be applied to many of the other problem types.The paper treats next the traveling salesman problem with time windows and a variety of shortest path problems with time windows or resource intervals. These constitute important modules of more complex optimization models used for time constrained vehicle routing and crew scheduling problems. It then examines the vehicle routing problem with time windows and a number of its variants and generalizations including the pick-up and delivery problem. The paper finally presents a unified solution framework which is being successfully implemented in school-busing and urban transit areas, as well as in airline and railway industries.

, 152 pages

Ce cahier a été révisé en août 1994