Title: Engine Assignment Problem for Railway Transportation: Models and Solutions

In this talk we consider the engine assignment problem of railway transportation.
Let us assume that a railway network and the timetable of trains on that network is given. The task is to assign engines to those trains listed in the timetable so, that each train has to be pulled by at least one but at most two engines. After an engine arrives at a final station, it can be assigned to the next train after some minutes. Each engine has to go for maintenance to its home-station before running 60 hours.
The task is not only to find some feasible assignments, but to find optimal ones using different objectives like minimal energy consumption or using minimal number of engines to serve all trains in a period of modelling etc.
We show that the problem can be formalized as a 0-1 programming model in a natural way. It is a bit large model but it describes the whole problem in details including the maintenance constraint as well. The maintenance constraint makes the problem NP-complete. Therefore, it is important to find some kind of relaxation of the model.
If we do not take into consideration the maintenance constraint, then we can build a relaxed model using concepts of graph theory. This combinatorial optimization model can be solved efficiently. Furthermore, the necessary time for the maintenance of engines can be placed in the task lists of each engine using an elementary analyzing routine in most of the practical cases that we have solved.