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


Using Column Generation to Solve the Vehicle Routing Problem with Time Windows

, et

The vehicle routing problem (VRP) involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicles which services a set of customers with known demands. Each customer is serviced exactly once and, furthermore, all the customers must be assigned to vehicles such that the vehicle capacities are not exceeded. The vehicle routing problem with time windows (VRPTW) is a generalization of the VRP involving the added complexity of allowable service times, or time windows. In this paper we present the development of a new optimization algorithm for a set covering type formulation of the VRPTW solved by column generation. Preliminary results show that the algorithm was capable of optimally solving problems of size six times larger than any attempted to date by other research.

, 13 pages