SBIR Phase I: A Decision Support System for the Train Schedule Design Problem

这个小企业创新研究（SBIR）的第一阶段项目需要开发一个决策支持系统来解决列车时刻表设计问题，这是货运铁路运输最重要的优化问题之一。铁路运输提出了丰富的优化问题集合；然而，这些问题的数学复杂性阻碍了优化算法的发展。结果，铁路没有从优化领域的进步中受益。他们仍然依靠人工决策过程来满足大多数计划和调度需求。该项目旨在实现重要铁路决策过程的自动化。铁路规划过程的第一步是确定阻塞计划。该计划将从一个地点出发但前往不同目的地的轨道车辆整合到一个街区，以减少车辆的处理。一旦铁路确定了阻塞计划，它必须设计一个列车时刻表，以便火车能够有效地将阻塞从起点运送到目的地。列车时刻表设计问题决定了以下几点：运行多少列列车；每列火车的始发地、目的地和路线；每站列车到达和离开的时间；每列火车的每周运行时间表；以及将汽车街区分配给火车。所有这些都是在保持运输总成本最低的情况下完成的。该问题是一个包含数万亿决策变量的大规模整数规划问题。这项研究将使用最先进的网络优化和启发式技术开发定制算法，以便在工作站的两个小时计算机时间内解决这个问题。它需要在建模、算法和实现技术方面取得重大进展，并将提供急需的软件来安排全球货运列车。两家美国铁路公司BNSF和诺福克南方铁路公司已经同意通过提供数据和分享他们的见解和经验来协助这个项目。他们还将在他们的环境中验证、验证和实现算法获得的解决方案。预计该软件的使用将使美国各主要铁路的运营成本每年减少1200万至2000万美元。这项研究的动机是需要开发基于网络流的启发式解决技术，以解决铁路调度中出现的大规模和复杂的优化问题。在铁路管理人员可以在日常决策实践中使用的软件产品中合并这些技术也是一个重要的需求。因此，本研究将建立有效的网络优化和启发式方法来解决铁路调度问题。该项目的成功以及这些软件产品在工业中的使用将导致铁路行业对优化模型和基于优化的软件的更大接受。它将为解决其他几个同样重要的铁路调度问题的新软件产品铺平道路。从长远来看，这项研究将提高美国铁路的效率和盈利能力。

This Small Business Innovation Research (SBIR) Phase I project entails developing a decision support system for the train schedule design problem, one of freight railroad transportation's most significant optimization problems. Railroad transportation presents a rich collection of optimization problems; however, the mathematical complexity of these problems has precluded the development of optimization algorithms for solving them. As a result, the railroads have not benefited from the advances taking place in the field of optimization. They are still relying on manual decision-making processes for most of their planning and scheduling needs. This project is intended to automate an important railroad decision process. The first step in the railroad planning process is to determine a blocking plan. This plan consolidates rail cars originating at one location but heading for different destinations into a single block, so as to reduce the car handlings. Once a railroad has identified a blocking plan, it must design a train schedule so that trains can efficiently carry blocks from their origins to their destinations. The train schedule design problem determines the following: how many trains to run; the origin, destination, and route of each train; the train arrival and departure times for each station at which it stops; the weekly operating schedule for each train; and the assignment of blocks of cars to trains. All of this is accomplished while keeping the total cost of transportation at a minimum. This problem is a very large-scale integer programming problem containing trillions of decision variables. This research will develop customized algorithms using state-of-the-art network optimization and heuristic techniques so that this problem can be solved within two hours of computer time on a workstation. It requires significant advances in modeling, algorithmic, and implementation technologies, and it will provide much needed software to schedule freight trains worldwide. Two US railroads, BNSF and Norfolk Southern, have agreed to assist in this project by providing data and sharing their insights and experiences. They will also verify, validate, and implement the solutions obtained by the algorithms within their environment. It is anticipated that the use of this software will reduce operational costs from between $12-$20 million annually for each of the major US railroads.This research is motivated by the need to develop network flow based heuristic solution techniques for large-scale and complex optimization problems that arise in railroad scheduling. There is also a significant need to incorporate these techniques in software products that railroad management personnel can use in their daily decision-making practices. This research will therefore establish the efficacy of network optimization and heuristic methodology to solve railroad scheduling problems. The success of this project and the use of these software products in industry will lead to a greater acceptance of the optimization models and optimization-based software in the railroad industry. It will pave the way for new software products for several other equally important railroad scheduling problems. In the long run, this research will lead to more efficient US railroads with improved profitability.