Optimising locomotive requirements for a pre-planned train schedule: a dissertation submitted in partial fulfilment of the requirements for the degree of Bachelor of Applied Computing with Honours at Lincoln University
Citations
Altmetric:
Authors
Date
2005
Type
Dissertation
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.
Permalink
Source DOI
Rights
https://researcharchive.lincoln.ac.nz/pages/rights