Solving Real-Life Railroad Blocking Problems
United States railroad companies transport millions of freight cars a year over their network. Railroad companies rely on their network to move shipments from city to city and state to state. Each railroad company has a service-design department which coordinates the movement of railcars, crew, and locomotives over the railroad’s network. Creating an operating plan for the system is a challenging task because train scheduling consists of designing train routes, days of operation, timings, and routing blocks to minimize cost.
The operating plan is responsible for the flow of the three important railroad assets: crew, locomotives, and cars. The expense to maintain all three commodities runs in billions of dollars. Developing a plan requires several months of preparation time by a team of experienced service designers. The railroad industry is losing a significant amount of experienced employees due to retirement. Railroad companies are in need of software tools to decrease their dependence on people. Ravindra Ahuja, Krishna Jha, and Jian Liu created algorithms to solve the railroad blocking and train scheduling problems.
Reducing railroad blocking is critical for the railroad industry in order to save cost. A shipment can travel through many train yards on its way from its starting point to its destination. An Incoming shipment is sorted and grouped for placement on outgoing trains. However, the reclassification process of the shipment delays the movement. To prevent a shipment from being reclassified at every train yard it travels through, shipments are grouped together to form a block. Blocking is a problem in the rail industry, postal and package delivery, trucking, and the airline industry.
Mathematically, the railroad blocking issue is a multicommodity-flow, network-design, and routing problem. To solve it, the developers designed an underlying blocking network and then routed different commodities on the blocking to reduce cost. Modeling and solving the real life blocking problems, the developers used an emerging technique known as a very large-scale neighborhood search. The algorithm solved the problems to near optimality using one to two hours of computer time. The computation was done on a standard workstation computer.
Three railroad companies (CSX, Norfolk Southern Corporation, and Burlington Northern Santa Fe) used the computational program to create their operating plans. The developers expect the computational code to replace the manual process which takes months of effort. A train company may transport over 50,000 shipments and about one million potential blocks, the number of changeable variables for routing is more than 100 billion. If CSX moves five million cars every year, the average number of miles traveled is over 450 miles.
The developers believe the program could reduce intermediate handling costs by 5 to 10 percent which equals to a savings of tens of million dollars. For each of the major train companies, there are success stories. CSX Transportation used the algorithm to create an operating plan with the assistance of the developers. The company shared their railroad data and the developers provided consulting services. Norfolk Southern Corporation licensed the algorithm to develop their operating plan and to generating blocking plans.
Burlington Northern Santa Fe licensed the algorithm and integrated it with their information system. In conclusion, blocking is a problem in the rail industry, airline, trucking, and telecommunications network. The techniques used to solve the blocking issues are critical in solving other consolidation concerns. The developing team noted each industry has unique features that distinguish it from other consolidation matters. In future research, the developers of the algorithm plan to continue to develop solutions to solve these challenges, not just for railroads, but of other industries.
