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

Innovative Scheduling Systems, Inc., Gainesville FL

Investigators

Abstract

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.