Production of locomotive rosters for a multi-class multi-locomotive problem

This paper describes a problem faced by the Public Transport Corporation (PTC) in the Australian State of Victoria. It involved the allocation of locomotives to the freight trains operated by the Corporation. Such a problem can be classified as a multi-class multi-locomotive problem since different types (or classes) of locomotive are available to pull the trains and some of the trains are heavy enough to require more than one locomotive. Because of the features of the services operated by the PTC, formulation of this problem as a pure integer program is straightforward, provided the objective function can be linearised. However, obtaining the optimal solution from this formulation is not. Large optimality gaps remained after various attempts to tighten the problem. Other authors have reported similar difficulties with similar problems. The original problem was therefore reformulated using special ordered covering sets of type 1. After reformulation, the optimal solution was obtained in less than a second of CPU time. This enabled alternative methods of linearising the objective function to be evaluated, resulting eventually in the decision to extend the concept of minimal covering sets so that each integer variable in the problem was expressed as a linear sum of a special ordered covering set of binary variables. In this way, the objective function was both exact and linear and the model, although much larger, still solved in under a second of CPU time. The methods of solution proposed in this paper should be capable of extension to more general resource allocation problems exhibiting similar features.