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

SBIR 第二阶段：列车时刻表设计问题的决策支持系统

• 批准号: 0548666
• 负责人: Ravindra Ahuja
• 金额: --
• 依托单位: Innovative Scheduling Systems, Inc.
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0548666&HistoricalAwards=false
• 关键词: SBIR; Phase; II; Decision; Support

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.

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