SBIR Phase I: Dynamic Locomotive Assignment: Algorithms for Real Time Decision Support

This Small Business Innovation Research Phase I research project entails the development of new algorithms for assigning locomotives to trains in a real-time environment. Locomotive assignment consists of optimally assigning a set of locomotives to trains satisfying a variety of business constraints and minimizing the total cost of assignment. Everyday, railroad managers must assign thousands of locomotives to thousands of different trains. The data and information the managers must consider are quite voluminous. As operations unfold across a 30,000 plus mile rail network, the managers must assess each piece of new data and determine how the current locomotive plan should be adjusted to ensure efficient use of resources while maximizing on-time operations of trains and protecting the fluidity of the network. A typical railroad company has several billions of dollars of investment in locomotives and using this resource effectively is of critical importance. The locomotive assignment problems are notoriously difficult discrete optimization problems that have not yet been solved satisfactorily. This proposal is to develop a new set of dynamic data driven algorithms for real-time locomotive assignment problems. The research focuses on algorithm development, analysis, and testing and includes: (i) developing approaches for generating detailed routing plans for each individual locomotive; (ii) developing optimization algorithms with the objective of recovering a prescribed locomotive cycling plan; (iii) improving our understanding of real time data sources, systems architecture, and user requirements; (iv) developing assignment algorithms that take network-wide view to balance and correct the flow of locomotives into each terminal and also take advantage of dynamic data updates to keep the plan current; and (v) designing a comprehensive simulation tool to test the efficacy of our series of algorithms. The proposed research will use the latest advances in network flows, heuristic optimization, algorithm design and implementation, and simulation to solve these mathematically challenging problems. The proposed research is motivated by the need to develop effective and practical solution techniques for large-scale and complex optimization problems arising in real time management of railroad networks and to incorporate these solutions in software products that railroad management personnel can use in their daily decision-making processes. The proposed research will also establish the value of using dynamic data driven decision support network methodologies to solve tactical transportation management problems. The success of this project and the use of these software products in industry will lead to a greater acceptance of optimization models and optimization-based software in the railroad industry. It will additionally pave the way for new software products for several other equally important railroad scheduling problems in crew management, terminal management, and dynamic trip planning. In the long run, this will lead to improved capacity utilization, increased productivity, and superior reliability of America's railroad infrastructure.