A Heuristic to Find Cyclical Planning Solution for Locomotives Assignment Problems

The problem of assigning locomotives to trains is very important for railway companies, in view of the high cost of operating locomotives. The problem considered is to provide sufficient power to pull trains on fixed schedules, using heterogeneous consists. The force required to pull a train is as the route segment on which it must travel. This force is often expressed in terms of horsepower rather than in terms of number of engines. This complicates the solution process of the integer programming formulation and usually creates a large integrality gap. Finally, locomotives requiring inspection must be sent to appropriate shops within a given time limit. Railroads face two types of problems the planning problem and the operational problem. The planning problem is defined on a representative week of the planning horizon and it consists in determining the optimal cyclic solutions of locomotives assignments. The operational problem was modeled as a multicommodity flow problem with supplementary variables and constraints [16]. This formulation is defined on a non-cyclical time-space network (typically a one-week horizon) where each commodity is seen as a locomotive type. The model is solved by using Dantzig-Wolfe decomposition (or column generation) procedure embedded in a branch-and-bound search tree. The operational problem was solved a few years ago. However, a general method to solve the cyclical problem for locomotive assignment problem has not been proposed until today. In this paper we design a method to solve the planning cyclical problem. A first cyclical solution is obtained by using a heuristic based on the shortest path problem algorithm in each network commodity. The solution is a set of cyclical paths which make a cyclical network. Then we use these paths to find the target constrains for each sub-problem overlapping. Actually we obtain a non-cyclical locomotive assignment problem which could be solved by overlapping column generation method used for operational problems.

Keywords:

Integer Linear Programming , Branching , Planning , Railway , Decomposition , Scheduling , Cyclic