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.