In this work, we consider the integrated problem of locomotive scheduling and driver rostering 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 as well as a commodity aggregation for the multi-commodity-flow part. 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 rostering. 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 our method by solving a large-scale real-world problem instance provided by our industry partner DB Cargo Polska S.A.
Citation
@Article{BaermannMartinStaszek2021, author = {Andreas Bärmann and Alexander Martin and Jonasz Staszek}, title = {A decomposition approach for integrated locomotive scheduling and driver rostering in rail freight transport}, journal = {•}, year = {2021}, OPTkey = {•}, OPTvolume = {•}, OPTnumber = {•}, OPTpages = {•}, OPTmonth = {•}, OPTannote = {•}}