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

这个小型企业创新研究（SBIR）的第二阶段项目需要开发一个决策支持系统来解决列车时刻表设计问题，这是货运铁路运输最重要的优化问题之一。列车调度是铁路运营计划的重要组成部分，它保证了铁路车辆的高效运行。设计这样的作业计划是一个非常大规模和非常复杂的多目标优化问题，迄今为止还没有解决方案。因此，铁路运营计划的制定是一个冗长的、手工的、繁琐的过程，可能需要五到十个人在三到六个月的时间里完成。Innovative Scheduling利用尖端的运筹学技术，正在开发一种软件产品，该产品可以在两到三名员工的情况下，在两周内获得一份新的运营计划，每年可为典型的美国一级铁路节省5000多万美元。列车时刻表设计问题决定了：运行多少列火车；每列火车的始发地、目的地和路线；每站列车到达和离开的时间；每列火车的每周运行时间表；以及将汽车街区分配给火车。列车时刻表必须满足许多实际约束和业务规则，并达到最低的运输成本。该问题是一个包含数万亿决策变量的非常大规模的多目标整数规划问题。拟议的研究将开发基于分解的定制算法，使用最先进的网络优化和启发式技术，以便在工作站的两个小时内解决这个问题。这些算法将被打包到一个基于网络的决策支持系统中，该系统具有具有吸引力和友好的图形和地理界面，将允许充分的用户控制。拟议的研究和开发需要在建模、算法和实施技术方面取得重大进展，并将为全球货运列车调度提供急需的软件。本研究将进一步扩展到开发旅客列车调度决策支持系统。BNSF铁路是美国一级铁路公司，是该项目的开发合作伙伴，并提供补充资金，数据和人力。列车调度决策支持系统有可能被所有货运铁路在其运营计划制定过程中使用。计算机化的列车调度方法将使铁路对交通变化反应更灵敏，并使其能够经常更改时刻表。优化和及时的列车时刻表将提高系统效率并显著降低成本。此外，最优的火车时刻表需要更少的火车里程、机组工作时间、机车工作时间和铁路车辆工作时间来运输相同的货物，从而提高了我们国家的能源效率并减少了污染。该产品的成功将导致模型和运筹学技术在铁路规划和调度中的更大接受度。预计铁路将采用运筹学模型，并在各种业务流程（包括战术操作和商业战略）中引入决策支持系统。届时，铁路行业的生产率将达到一个新的水平，从而降低终端用户的运费，使美国的产品在世界市场上更具竞争力。

This Small Business Innovation Research (SBIR) Phase II project entails developing a decision support system for the train schedule design problem, one of the freight railroad transportation's most significant optimization problems. Train scheduling is an important part of a railroad's operating plan that enables efficient movement of railcars. Designing such an operating plan is a very large-scale and very complex multi-objective optimization problem that, to date, has defied solution. Consequently, operating plan development at railroads is a lengthy, manual, and cumbersome process that may involve five to ten persons for a period of three to six months. Using cutting-edge operations research techniques, Innovative Scheduling, is developing a software product that can obtain a new operating plan within two weeks using two-three employees and can save a typical Class I US railroad over $50M annually. The train schedule design problem determines: 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. The train schedule must satisfy numerous practical constraints and business rules and achieve the minimum cost of transportation. This problem is a very large-scale multi-objective integer-programming problem containing trillions of decision variables. The proposed research will develop decomposition-based 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. These algorithms will be packaged into a web-based decision support system with attractive and friendly graphical and geographical interfaces, which will allow sufficient user control. The proposed research and development requires significant advances in modeling, algorithmic, and implementation technologies and will provide much needed software to schedule freight trains worldwide. This research will further be extended to develop a decision support system for passenger train scheduling. BNSF Railway, a Class I US Railroad, which is a Development Partner in this project and is providing supplementary funds, data and manpower. The train scheduling decision support system is likely to be used by all freight railroads in their operating plan development process. A computerized method for train scheduling will make a railroad more responsive to traffic changes and enable it to change its schedule frequently. Optimal and timely train schedule will introduce greater efficiency in the system and significantly lower costs. Further, optimal train schedules require significantly less train miles, crew hours, locomotive hours, and railcar hours to transport the same set of shipments, thereby increasing our nation's energy efficiency and reducing pollution. The success of this product will lead to a greater acceptance of models and operations research techniques in railroad planning and scheduling. Railroads are then anticipated to embrace operations research models and introduce decision support systems in a variety of business processes including tactical operations and commercial strategy. The railroad industry will then be in a position to achieve a new level of productivity, resulting in lower freight charges for end users, and making America's products more competitive on the world market.