A Novel Movement Planner System for Dispatching Trains

Srinivas Bollapragada, Randall Markley, Heath Morgan, Erdem Telatar, Scott Wills, Mason Samuels, Jerod Bieringer, Marc Garbiras, Giampaolo Orrigo, Fred Ehlers, Charlie Turnipseed, Jay Brantley, A Novel Movement Planner System for Dispatching Trains, Interfaces, Volume 48, Issue 1, January-February 2018, pp. 57–69.

General Electric Company (GE) partnered with Norfolk Southern Railroad (NS) to create and implement an optimization algorithm-based software system that dispatches thousands of trains in real time, increases their average speed, and allows NS to realize annual savings in the hundreds of millions of dollars. NS handles a range of rail traffic that includes intermodal, automobile transport, manifest freight, and passenger, all with unique priorities and scheduling requirements. Previously, dispatching for each geographic area was managed manually from regional dispatch centers and did not encompass a view of the entire rail network. The algorithm that we developed incorporates data about the properties of the rail networks (e.g., track layout, speed restrictions, height and weight restrictions), data about the trains (e.g., schedules, operating costs, train characteristics), and additional activities associated with train dispatching, such as crew changes and inspections. In doing so, we created a novel system to manage all train dispatching, increased the average speed of trains by two miles per hour, and decreased operating costs, while significantly improving schedule adherence and crew expirations. Every mile-per hour increase in average speed translates to $200 million savings in capital and operational expenses annually for NS. GE is currently implementing this system at two other railroads and is gaining additional important benefits from the project.

Difficulty:

However, mathematical formulations of even simple approximations of real-world problems over partial regions of the rail network result in mixed-integer linear programs with millions of integer variables. Such formulations are too large to be solved using state-of-the-art integer program solvers. 

Approach:

Using a detailed model of the track topology, our algorithm systematically searches the feasible space to develop a good movement plan that meets all real-world requirements while performing significantly better than any manually generated solution. It employs a hybrid combination of heuristic methods, local optimization techniques, and backtracking methods to reduce the search space in developing the plan.