The problem of assigning locomotives to trains consists of selecting the types and number of engines that minimize the fixed and operational locomotive costs resulting from providing sufficient power to pull trains on fixed schedules. The force required to pull a train is often expressed in terms of horsepower and tonnage requirements 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. Furthermore, the solution of the linearly relaxed problem is strongly fractional. To obtain integer solutions, a novel branch-and-cut approach is proposed. The core of the method consists of branching decisions that define on one branch the projection of the problem on a low-dimensional subspace. There, the facets of the polyhedron describing a restricted constraint set can be easily derived. This approach is called branch-first, cut-second. It is first derived facets when at most two types of engines are used. The branching rule is then extended to cases involving additional locomotive types. It has been conducted computational experiments using actual data from the Canadian National railway company. Simulated test-problems involving two or more locomotive types were solved over 1-, 2-, and 3-day rolling horizons. The cuts were successful in reducing the average integrality gap by 52 % for the two-type case and by 34 % when more than 25 types were used. Furthermore, the branch-first, cut-second approach was instrumental in improving the best known solution for an almost 2000-leg weekly problem involving 26 locomotive types. It reduced the number of locomotives by 11, or 1.1 %, at an equivalent savings of 3000000 USD per unit. Additional tests on different weekly data produced almost identical results.
A branch-first, cut-second approach for locomotive assignment
Management Science ; 45 , 8 ; 1156-1168
1999
13 Seiten, 2 Bilder, 5 Tabellen, 20 Quellen
Aufsatz (Zeitschrift)
Englisch
An extended branch-and-bound method for locomotive assignment
Online Contents | 2006
|An extended branch-and-bound method for locomotive assignment
Elsevier | 2005
|The importance of locomotive assignment
Engineering Index Backfile | 1927
|The importance of locomotive assignment
Engineering Index Backfile | 1927
|The importance of locomotive assignment
Engineering Index Backfile | 1927