Strategic, tactical and real-time planning of locomotives at Norfolk Southern using approximate dynamic programming

Locomotive planning has been a popular application of classical optimization models for decades, but with very few success stories. There are a host of complex rules governing how locomotives should be used. In addition, it is necessary to simultaneously manage locomotive inventories by balancing the need for holding power against the need for power at other yards. At the same time, we have to plan the need to return foreign power, and move power to maintenance facilities for scheduled FRA appointments. An additional complication arises as a result of the high level of uncertainty in transit times and delays due to yard processing, and as a result we may have to plan additional inventories in order to move outbound trains on time despite inbound delays. We describe a novel modeling and algorithmic strategy known as approximate dynamic programming, which can also be described as a form of "optimizing simulator" which uses feedback learning to plan locomotive movements in a way that closely mimics how humans plan real-world operations. This strategy can be used for strategic and tactical planning, and can also be adapted to real-time operations. We describe the strategy, and summarize experiences at Norfolk Southern with a strategic planning system.