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

G-89-20

The simultaneous origin-destination assignment and vehicle routing problem

, et

The problem we consider is that of preparing a minimum cost transportation plan by simultaneously solving the following two sub-problems: first the assignment of units available at a series of origins to satisfy demand at a series of destinations and second, the design of vehicle tours to transport these units, when the vehicles have to be brought back to their departure point. We present a solution method for this problem using a minimum cost flow model followed by heuristic tour construction and improvement procedures. This approach allows large problems to be solved quickly, and solutions to large test problems have shown to be 1% or 2% from the optimum. Results are presented for a problem involving the transport of 24000 students working on an environmental cleanup project.

, 27 pages

Ce cahier a été révisé en avril 1990