Heuristic methods for routing and scheduling

A locomotive assignment is one of the subproblems in railway scheduling domain. In this report present general mathematical model of this specific subproblem and describe how methods known from other problems domain like traveling salesman problem, operation research and constraint programming can be used to solve it. We concentrate especially on method known as {\it k--interchange} for traveling salesman problem with time windows and give an outline how it can be adopted to locomotive assignment problem. Further, while turning from one trip to another a locomotive must often be reallocated from one station to another. This can be performed in two ways. A locomotive can be driven from one place to another not performing any specific trip and exclusively using track resource, i.e. performs so called deadhead transport, or can be attached to any other transport and passively drown to another station, i.e. perform so called passive transport. Because the cost of passive transport is much lower then cost of a deadhead it is advantageous to, if possible, replace any deadhead by passive transport. In this report we describe a method of converting deadheads into passive transports, describe conversion algorithm, its implementation and report computational result of the algorithm. Finally, we give directions for future research in locomotive planning problem domain