Time constrained routing and scheduling. (English) Zbl 0861.90052

Desrosiers, Jacques; Dumas, Yvan; Solomon, Marius M.; Soumis, François

Ball, M. O. (ed.) et al., Network routing. Amsterdam: North-Holland. Handb. Oper. Res. Manage. Sci. 8, 35-139 (1995).

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.
For the entire collection see [Zbl 0829.00010].

Reviewer: N.Paradis (Montreal, Canada)

MSC:

90B06	Transportation, logistics and supply chain management
90B35	Deterministic scheduling theory in operations research
90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C27	Combinatorial optimization
90C39	Dynamic programming
90B10	Deterministic network models in operations research

Keywords:

survey; time constrained vehicle routing; crew scheduling; traveling salesman; time windows; pick-up and delivery problem