Optimization Algorithms for Vehicle Routing

车辆路径优化算法

• 批准号: 8812006
• 负责人: Marshall Fisher
• 金额: $ 15.23万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-08-01 至 1992-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8812006&HistoricalAwards=false
• 关键词: Optimization; Algorithms; Vehicle; Routing

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.

运输成本占美国国民生产总值的15%。运输的一个主要因素涉及车队的管理、路线和调度，例如校车的路线和运送消费品的卡车的调度，为快餐店供货或及时向工业制造商交货。在优化卡车车队运营利用率方面取得的进展可以带来非常显著的经济效益。然而，进一步的进展取决于新的强大的组合优化算法的发展。该合同将支持针对若干车辆路线问题开发和验证此类算法的研究。该研究借鉴了最近在朗格松弛、旅行推销员问题的优化和某些图问题的多项式算法方面的方法进展。所得到的模型将在几家大公司的大型卡车车队上进行测试和验证。