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

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

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.