In this work, we consider the integrated problem of locomotive scheduling and driver assignment in rail freight companies. Our aim is to compute an optimal simultaneous assignment of locomotives and drivers to the trains listed in a given order-book. Mathematically, this leads to the combination of a set-packing problem with compatibility constraints and a multi-commodity-flow problem. We develop a binary-programming formulation to model the given task and improve it by performing a clique-based tightening of the original set-packing inequalities. The objective function of this model makes sure that as many trains as possible are running. To handle the computational complexity of the problem, we introduce a novel decomposition approach which decomposes the problem into a master locomotive scheduling problem and a subproblem for driver assignment. It exploits the fact that the master problem is empirically much easier to solve than the subproblem. For any fixed solution of the master problem, we can use the subproblem to either confirm feasibility of the master solution or to derive valid inequalities from various constraint classes to cut the infeasible master solution off and reiterate. To further improve solution times, we also develop a presolve heuristic. We demonstrate the potential of the presented method by solving a large-scale real-world problem instance provided by our industry partner DB Cargo Polska S.A., as well as a set of derived realistic instances.


    Access

    Download


    Export, share and cite



    Title :

    A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport


    Contributors:


    Publication date :

    2024




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown




    Locomotive and Wagon Scheduling in Freight Transport

    Fügenschuh, Armin / Homfeld, Henning / Huck, Andreas et al. | BASE | 2006

    Free access

    Rail freight traffic assignment

    Lansdowne, Zachary F. | Elsevier | 1980


    Locomotive unit, freight locomotive and freight locomotive management method

    FAN YUNXIN / ZHOU ANDE / XIAO DIANXI et al. | European Patent Office | 2021

    Free access

    Locomotive maintenance scheduling and train assignment

    Desrosiers, Jacques / Soumis, François | TIBKAT | 1982


    Heavy freight locomotive

    Engineering Index Backfile | 1903