Optimization Online


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

Andreas Bärmann (andreas.baermann***at***math.uni-erlangen.de)
Alexander Martin (alexander.martin***at***fau.de)
Jonasz Staszek (jonasz.staszek***at***fau.de)

Abstract: 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.

Keywords: Integrated Locomotive Scheduling and Driver Rostering, Railway Transport, Integer Programming, Decomposition, Cutting Planes

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Integer Programming (0-1 Programming )

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 = {•}}

Download: [PDF]

Entry Submitted: 08/28/2021
Entry Accepted: 08/28/2021
Entry Last Modified: 08/30/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society