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

G-88-28

A Network Approach to a Simultaneous Origin-Destination Assignment and Vehicule Routing Problem

, et

The problem is to elaborate a minimum cost transportation plan by simultaneously solving the following two sub-problems: the assignment of available units at the origins to satisfy demand at the destinations and the design of vehicle tours, transporting the units, the vehicles having to be brought back to their departure point.

We present a solution method for this problem using a minimum cost flow model and heuristic procedures. This approach allows large problems to be solved quickly, with solutions being less than 0.5% from the optimum. Results are presented for a student transportation problem.

, 11 pages