In this paper we investigate the Locomotive Scheduling Problem, i.e., the optimization of locomotive utilization with prior known transports that must be performed. Since railway timetables are typically planned a year in advance, the aim is to assign locomotives to trains such that the locomotive utilization is maximized while maintenance constraints are taken into account. We model this optimization problem on a sparse weighted directed graph that defines the input variables for our proposed Mixed Integer Linear Program (MILP). We consider two different objective functions: First we minimize over the number of deadhead kilometers, i.e., kilometers from a locomotive driven without pulling a train, and second, over the number of locomotives used. In a further step, we combine the two suggested objective functions, i.e., we minimize over the weighted sum of them. Finally, we conduct a computational study to compare the performance of our MILP with the different proposed objective functions and show how the MILP can be used within a rolling horizon approach.

## Citation

TR-AAUK-M-O-18-09-10, Alpen-Adria-UniversitĂ¤t Klagenfurt, Mathematics, Optimization Group, September 2018