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

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

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.