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

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.