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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A branch-first, cut-second approach for locomotive assignment


    Beteiligte:
    Koorush Ziarati (Autor:in) / Soumis, F. (Autor:in) / Desrosiers, J. (Autor:in) / Solomon, M.M. (Autor:in)

    Erschienen in:

    Management Science ; 45 , 8 ; 1156-1168


    Erscheinungsdatum :

    1999


    Format / Umfang :

    13 Seiten, 2 Bilder, 5 Tabellen, 20 Quellen




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch




    An extended branch-and-bound method for locomotive assignment

    Rouillon, Stéphane | Online Contents | 2006


    An extended branch-and-bound method for locomotive assignment

    Rouillon, Stéphane / Desaulniers, Guy / Soumis, François | Elsevier | 2005


    The importance of locomotive assignment

    Titus, H.J. | Engineering Index Backfile | 1927


    The importance of locomotive assignment

    Titus, H.J. | Engineering Index Backfile | 1927


    The importance of locomotive assignment

    Engineering Index Backfile | 1927