Maintenance scheduling of rolling stock using a genetic algorithm

We have developed a genetic algorithm (GA) for the optimisation of maintenance overhaul scheduling of rolling stock (trains) at the Hong Kong Mass Transit Railway Corporation (MTRC). The problem is one of combinatorial optimisation. Genetic algorithms (GAs) belong to the class of heuristic optimisation techniques that utilise randomisation as well as directed smart search to seek the global optima. The workshop at MTRC does have difficulties in establishing good schedules for the overhaul maintenance of the rolling stock. Currently, an experienced scheduler at MTRC performs this task manually. In this paper, we study the problem in a scientific manner and propose ways in which the task can be automated with the help of an algorithm embedded in a computer program. The algorithm enables the scheduler to establish the annual maintenance schedule of the trains in an efficient manner; the objective being to satisfy the maintenance requirements of various units of the trains as closely as possible to their due dates since there is a cost associated with undertaking the maintenance tasks either ‘too early’ or ‘too late’. The genetic algorithm developed is found to be very effective for solving this intractable problem. Computational results indicate that the genetic algorithm consistently provides significantly better schedules than those established manually at MTRC. Moreover, we provide evidence that the algorithm delivers close to optimal solutions for randomly generated problems with known optimal solutions. We also propose a local search method to reconfigure the trains in order to improve the schedule and to balance the work load of the overhaul maintenance section of the workshop throughout the planning horizon. We demonstrate that the reconfiguration of trains improves the schedule and reduces cost significantly.