A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2024-01-01
|
| Series: | EURO Journal on Transportation and Logistics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192437624000207 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850260325637554176 |
|---|---|
| author | Andreas Bärmann Alexander Martin Jonasz Staszek |
| author_facet | Andreas Bärmann Alexander Martin Jonasz Staszek |
| author_sort | Andreas Bärmann |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-e35e8d1f7a204023aecef9dd0b961664 |
| institution | OA Journals |
| issn | 2192-4384 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Transportation and Logistics |
| spelling | doaj-art-e35e8d1f7a204023aecef9dd0b9616642025-08-20T01:55:40ZengElsevierEURO Journal on Transportation and Logistics2192-43842024-01-011310014510.1016/j.ejtl.2024.100145A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transportAndreas Bärmann0Alexander Martin1Jonasz Staszek2Lehrstuhl für Analytics & Mixed-Integer Optimization, Department of Data Science/Department Mathematik, Friedrich-Alexander-Universität Erlangen-Nürnberg, Cauerstraße 11, 91058 Erlangen, GermanyAnalytics and Optimization Lab, Technische Universität Nürnberg, Ulmenstr. 52, 90544 Nürnberg, GermanyAnalytics and Optimization Lab, Technische Universität Nürnberg, Ulmenstr. 52, 90544 Nürnberg, Germany; Corresponding author.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.http://www.sciencedirect.com/science/article/pii/S2192437624000207Integrated locomotive scheduling and driver assignmentRailway transportInteger programmingDecompositionCutting planes |
| spellingShingle | Andreas Bärmann Alexander Martin Jonasz Staszek A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport EURO Journal on Transportation and Logistics Integrated locomotive scheduling and driver assignment Railway transport Integer programming Decomposition Cutting planes |
| title | A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport |
| title_full | A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport |
| title_fullStr | A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport |
| title_full_unstemmed | A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport |
| title_short | A decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport |
| title_sort | decomposition approach for integrated locomotive scheduling and driver assignment in rail freight transport |
| topic | Integrated locomotive scheduling and driver assignment Railway transport Integer programming Decomposition Cutting planes |
| url | http://www.sciencedirect.com/science/article/pii/S2192437624000207 |
| work_keys_str_mv | AT andreasbarmann adecompositionapproachforintegratedlocomotiveschedulinganddriverassignmentinrailfreighttransport AT alexandermartin adecompositionapproachforintegratedlocomotiveschedulinganddriverassignmentinrailfreighttransport AT jonaszstaszek adecompositionapproachforintegratedlocomotiveschedulinganddriverassignmentinrailfreighttransport AT andreasbarmann decompositionapproachforintegratedlocomotiveschedulinganddriverassignmentinrailfreighttransport AT alexandermartin decompositionapproachforintegratedlocomotiveschedulinganddriverassignmentinrailfreighttransport AT jonaszstaszek decompositionapproachforintegratedlocomotiveschedulinganddriverassignmentinrailfreighttransport |