Optimising locomotive requirements for a pre-planned train schedule

Abstract

Every rail operator wishes to minimise the size of their locomotive fleet in order to reduce costs. This minimum fleet size problem requires a rail operator to allocate locomotives to the trains in a predefined train schedule so that the total number of locomotives required is minimised. The key to this is deciding how and when to transfer locomotives to where they can be better utilised. The rail operator for this hypothetical problem runs approximately 7,200 trains per week involving movements between 780 locations. An integer programming formulation was developed based on the work by Ahuja, Liu, Orlin, Sharma and Shughart (2002)¹ and a solver applied this formulation to a train schedule to find the optimal solution. As the solution process was highly computationally intensive, the largest partial train schedule that was able to be solved by the integer programming solver was 21% of the size of the full train schedule, taking 2½ hours to converge on the optimal solution. An alternative algorithm, called the work unit levels algorithm, was developed. This algorithm schedules locomotives by identifying all valid ways to transfer locomotives between trains, then allocating the train schedule in an order dependent on the possible interconnections between trains. When this algorithm was applied to the largest partial train schedule that could be solved by the integer programming solver, it arrived at a similar solution in 6 seconds. The algorithm took 13 minutes to solve the full problem.