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

G-83-26

Langragean Relaxation Methods for Vehicle Routing and Scheduling with Time Windows

In this article, two Lagrangean relaxations for the vehicle routing problem with time windeow constraints are examined. In the first case, the scheduling constraints are relaxed producing Lagrangean problems of a network type which are easy to solve, but the use of the Lagrangean method does not improve on the network relaxation. Furthermore, the bound obtained is weak when the constraints are binding. In the second case, constraints requiring that each trip be visited are relaxed, but the network structure is retained. Shortest path problems with time window constraints and integrality conditions must be solved. The bound produced is always excellent.

, 10 pages