Solving real-life locomotive-scheduling problems

In the locomotive-scheduling problem (or the locomotive-assignment problem) we must assign a consist (a set of locomotives) to each train in a preplanned train schedule so as to provide each train with sufficient locomotive power to pull the train from its origin to its destination. Locomotive-scheduling problems are among the most important problems in railroad scheduling. In this paper, we report the results of a study on the locomotive-scheduling problem as it is faced by CSX Transportation, a major US railroad company. We consider the planning version of the locomotive-scheduling model (LSM) in which multiple types of locomotives exist, and we need to decide which set of locomotives should be assigned to each train. We present an integrated model that determines: the set of active and deadheaded locomotives for each train; the light-traveling locomotives from power sources to power sinks; and train-to-train connections (for which we specify which inbound trains and outbound trains can directly connect). An important feature of our model is that we explicitly consider consist bustings and consistency. A consist is said to be busted when a set of locomotives coming on an inbound train is broken into subsets to be reassigned to two or more outbound trains. A solution is consistent over a week if a train receives the same locomotive assignment each day it runs. We will provide a mixed-integer programming (MIP) formulation of the locomotive-assignment problem. However, an MIP of this size cannot be solved to optimality or near optimality in acceptable running times using commercially available software. Using problem decomposition, integer programming, and very large-scale neighborhood search, we have developed a solution technique to solve this problem within 30 minutes of computation time on a Pentium III computer. Our solution obtained a potential savings of over 400 locomotives over the solution obtained by the in-house software developed by CSX.