A railway maintenance scheduling problem with customer costs

An important aspect of infrastructure management is the scheduling of maintenance tasks, which implies the allocation of tasks to different crews or machines and the determination of an execution order. To this end, different aspects have to be considered. On the one hand, the maintenance operator is interested in reducing direct maintenance costs, e.g. travel costs. On the other hand, priorities must be considered by scheduling maintenance tasks. Often, this is done by urgency rules, an inflexible method that resolves prioritised tasks first. In this paper, another approach is discussed. Instead of urgency rules, the maintenance tasks are afflicted with penalty costs that have to be paid for every day until the task is resolved. Then, the later the execution time of such a job, the higher are the penalty costs. By minimising the sum of penalty costs and travel costs, a solution with small overall costs can be found. The resulting scheduling problem is a multi-depot vehicle routing problem with travel and customer costs. For this extension of a vehicle routing problem, different formulations as mixed-integer linear program are developed. For small instances, these formulations are compared with respect to their computation time in a solution method that uses a commercial solver.