SBIR Phase I: Dynamic Locomotive Assignment: Algorithms for Real Time Decision Support

SBIR 第一阶段：动态机车分配：实时决策支持算法

• 批准号: 0610868
• 负责人: Ravindra Ahuja
• 金额: $ 10万
• 依托单位: Innovative Scheduling Systems, Inc.
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-07-01 至 2006-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0610868&HistoricalAwards=false
• 关键词: SBIR; Phase; Dynamic; Locomotive; Assignment

This Small Business Innovation Research Phase I research project entails the development of new algorithms for assigning locomotives to trains in a real-time environment. Locomotive assignment consists of optimally assigning a set of locomotives to trains satisfying a variety of business constraints and minimizing the total cost of assignment. Everyday, railroad managers must assign thousands of locomotives to thousands of different trains. The data and information the managers must consider are quite voluminous. As operations unfold across a 30,000 plus mile rail network, the managers must assess each piece of new data and determine how the current locomotive plan should be adjusted to ensure efficient use of resources while maximizing on-time operations of trains and protecting the fluidity of the network. A typical railroad company has several billions of dollars of investment in locomotives and using this resource effectively is of critical importance. The locomotive assignment problems are notoriously difficult discrete optimization problems that have not yet been solved satisfactorily. This proposal is to develop a new set of dynamic data driven algorithms for real-time locomotive assignment problems. The research focuses on algorithm development, analysis, and testing and includes: (i) developing approaches for generating detailed routing plans for each individual locomotive; (ii) developing optimization algorithms with the objective of recovering a prescribed locomotive cycling plan; (iii) improving our understanding of real time data sources, systems architecture, and user requirements; (iv) developing assignment algorithms that take network-wide view to balance and correct the flow of locomotives into each terminal and also take advantage of dynamic data updates to keep the plan current; and (v) designing a comprehensive simulation tool to test the efficacy of our series of algorithms. The proposed research will use the latest advances in network flows, heuristic optimization, algorithm design and implementation, and simulation to solve these mathematically challenging problems. The proposed research is motivated by the need to develop effective and practical solution techniques for large-scale and complex optimization problems arising in real time management of railroad networks and to incorporate these solutions in software products that railroad management personnel can use in their daily decision-making processes. The proposed research will also establish the value of using dynamic data driven decision support network methodologies to solve tactical transportation management problems. The success of this project and the use of these software products in industry will lead to a greater acceptance of optimization models and optimization-based software in the railroad industry. It will additionally pave the way for new software products for several other equally important railroad scheduling problems in crew management, terminal management, and dynamic trip planning. In the long run, this will lead to improved capacity utilization, increased productivity, and superior reliability of America's railroad infrastructure.

这个小企业创新研究第一阶段的研究项目需要开发新的算法，用于在实时环境中将机车分配给列车。机车配车问题是指在满足各种业务约束条件的前提下，以最小化配车总成本为目标，将一组机车最优地配车。每天，铁路管理人员必须将数千辆机车分配给数千辆不同的列车。管理人员必须考虑的数据和信息是相当庞大的。随着运营在30，000多英里的铁路网络中展开，管理人员必须评估每一条新数据，并确定应如何调整当前的机车计划，以确保有效利用资源，同时最大限度地提高列车的准时运营并保护网络的流动性。一个典型的铁路公司在机车上有数十亿美元的投资，有效地利用这一资源至关重要。机车分配问题是一个非常困难的离散优化问题，至今尚未得到满意的解决。本文提出了一套新的动态数据驱动算法来解决实时机车配车问题。该研究的重点是算法开发，分析和测试，包括：（i）开发方法，为每个单独的机车产生详细的路由计划;（ii）开发优化算法，恢复规定的机车循环计划的目标;（iii）提高我们的理解真实的时间数据源，系统架构和用户需求;（iv）发展配车算法，从整个网络的角度出发，平衡和修正进入每个总站的机车流量，并利用动态数据更新，使计划保持最新;及（v）设计一个全面的模拟工具，以测试我们的一系列算法的功效。拟议的研究将使用网络流，启发式优化，算法设计和实现以及模拟的最新进展来解决这些数学上具有挑战性的问题。拟议的研究的动机是需要开发有效的和实用的解决方案技术，在铁路网络的真实的时间管理中产生的大规模和复杂的优化问题，并将这些解决方案的软件产品，铁路管理人员可以在日常决策过程中使用。拟议的研究还将建立使用动态数据驱动的决策支持网络方法来解决战术运输管理问题的价值。该项目的成功以及这些软件产品在行业中的使用将导致铁路行业更广泛地接受优化模型和基于优化的软件。此外，它还将为其他几个同样重要的铁路调度问题的新软件产品铺平道路，这些问题包括乘务员管理、终点站管理和动态行程规划。从长远来看，这将提高产能利用率，提高生产率，并使美国的铁路基础设施具有上级可靠性。