Optimization Algorithms for Vehicle Routing

运输成本占美国国民生产总值的15%。 产品 运输的一个主要因素涉及管理， 车队的路线和调度，如学校的路线 公共汽车和运送消费品的卡车的调度， 供应快餐店或及时交付给工业 厂商 优化卡车车队利用的进展 运营可以带来非常显著的经济回报。 进一步 然而，进步取决于新的强大的发展， 组合优化算法 该奖项将支持 研究开发和验证几种车辆的这种算法 路由问题。 该研究借鉴了最新的方法学进展 在Langragian松弛中，旅行商问题优化 和多项式算法来解决某些图形问题。 所得 模型将在大型卡车车队上进行测试和验证 几家大公司的业务。

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.