The Simultaneous Origin-Destination Assignment and Vehicle Routing Problem

The problem we consider is that of preparing a minimum cost transportation plan by simultaneously solving the following two subproblems: 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 been shown to be 1% or 2% from the optimum. Results are presented for a problem involving the transport of 24,000 students working on an environmental cleanup project.