Algorithms for Scheduling of Train Maintenance

Abstract

In this thesis we will develop algorithms for the scheduling of train maintenance at NedTrain facilities. We present a detailed analysis of the maintenance process at NedTrain. The problem of scheduling train maintenance is formalized and expressed using linear inequalities. We show that the Simple Temporal Problem can be used to find schedules that satisfy the temporal constraints of the scheduling problem. However, when resource constraints are added, the STP is no longer sufficient. The problem can still be expressed using the Disjunctive Temporal Problem but this cannot be efficiently solved. Two algorithms are presented: a zero/one integer linear programming approach and an STP-based approach. In the STP-based approach we start with an STP that describes the temporal constraints. The STP is then iteratively updated until its earliest start time assignment corresponds to a valid solution to the scheduling problem. Experiments show that the ILP method is fast enough to produce optimal base schedules whereas the heuristic method is well suited to updating schedules with little disruption when changes have occurred.