Transportation costs account for 15% of the U.S. Gross National Product. A major element of transportation involves the management, routing and scheduling of vehicle fleets such as the routing of school buses and the dispatching of trucks delivering consumer goods, supplying fast food restaurants or just in time delivery to industrial manufacturers. Progress on optimizing the utilization of truck fleet operations can have very significant economic payoffs. Further progress, however, depends on the development of new powerful combinatorial optimization algorithms. This award will support research to develop and validate such algorithms for several vehicle routing problems. The research draws on recent methodological advances in Langragian relaxation, optimization of travelling salesman problems and polynomical algorithms for certain graph problems. The resulting models will be tested and validated on very large truck fleet operations of several major corporations.
