Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints
The integrated treatment of planning problems which are usually considered separately and sequentially has been studied for a long time, due to the better solutions one may find in the extended decision space of an integrated problem. This thesis considers the integrated locomotive scheduling and dr...
Zapisane w:
| 1. autor: | |
|---|---|
| Format: | Online |
| Język: | angielski |
| Wydane: |
FAU University Press
2026
|
| Hasła przedmiotowe: | |
| Dostęp online: | ONIX_20260106T140303_9783961476503_54 |
| Etykiety: |
Nie ma etykietki, Dołącz pierwszą etykiete!
|
| _version_ | 1869521090571665408 |
|---|---|
| author | Staszek, Jonasz |
| author_browse | Staszek, Jonasz |
| author_facet | Staszek, Jonasz |
| author_sort | Staszek, Jonasz |
| collection | Directory of Open Access Books |
| description | The integrated treatment of planning problems which are usually considered separately and sequentially has been studied for a long time, due to the better solutions one may find in the extended decision space of an integrated problem. This thesis considers the integrated locomotive scheduling and driver assignment problem in rail freight transport. We also consider the generalization of this problem, which we call graph 2-list-colouring with compatibility constraints. The motivation to study this problem originates from our collaboration with DB Cargo Polska within the ROMSOC Programme. The thesis consists of two parts. Part I focuses on modelling and solving the integrated locomotive scheduling and driver assignment problem in rail freight transport. After a literature review, we present a novel optimization model for the problem studied and a way to improve its formulation. Next, we introduce the decomposition-based solution approach we derive for the problem. To ensure the global feasibility of the solutions to the decomposed subproblems, we devise four classes of valid inequalities. We also develop a presolve heuristic. We then test our algorithm against two sets of instances. In general, the methods presented enabled the creation of locomotive timetables and driver assignments in less than two hours. In Part II, we study a generalization of the integrated locomotive scheduling and driver assignment problem, which we call graph 2-list-colouring with compatibility constraints. We begin by defining the problem studied and putting it in the context of other, more famous combinatorial problems. Then we present two formulations for the problem and discuss how they may be tightened. We also study a case for which we may find a complete polyhedral description. Next, we present a decomposition-based solution approach which adapts the algorithm introduced in Part I. We then test the performance of our method against a set of standard instances drawn from the literature, which were appropriately modified. Altogether, our work is a practical contribution to the solvability of the integrated locomotive scheduling and driver assignment problem. We also show how the developed method may be extended to successful use in more general graph-theoretic contexts. |
| format | Online |
| id | doab-20.500.12854ir-170768 |
| institution | Directory of Open Access Books |
| language | eng |
| publishDate | 2026 |
| publishDateRange | 2026 |
| publishDateSort | 2026 |
| publisher | FAU University Press |
| publisherStr | FAU University Press |
| record_format | ojs |
| spelling | doab-20.500.12854ir-1707682026-01-07T05:08:16Z Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints Staszek, Jonasz Ganzzahlige Optimierung Diskrete Optimierung Graphfärbung Operations Research thema EDItEUR::P Mathematics and Science::PB Mathematics::PBU Optimization thema EDItEUR::P Mathematics and Science::PB Mathematics::PBV Combinatorics and graph theory thema EDItEUR::T Technology, Engineering, Agriculture, Industrial processes::TR Transport technology and trades::TRF Railway technology, engineering and trades The integrated treatment of planning problems which are usually considered separately and sequentially has been studied for a long time, due to the better solutions one may find in the extended decision space of an integrated problem. This thesis considers the integrated locomotive scheduling and driver assignment problem in rail freight transport. We also consider the generalization of this problem, which we call graph 2-list-colouring with compatibility constraints. The motivation to study this problem originates from our collaboration with DB Cargo Polska within the ROMSOC Programme. The thesis consists of two parts. Part I focuses on modelling and solving the integrated locomotive scheduling and driver assignment problem in rail freight transport. After a literature review, we present a novel optimization model for the problem studied and a way to improve its formulation. Next, we introduce the decomposition-based solution approach we derive for the problem. To ensure the global feasibility of the solutions to the decomposed subproblems, we devise four classes of valid inequalities. We also develop a presolve heuristic. We then test our algorithm against two sets of instances. In general, the methods presented enabled the creation of locomotive timetables and driver assignments in less than two hours. In Part II, we study a generalization of the integrated locomotive scheduling and driver assignment problem, which we call graph 2-list-colouring with compatibility constraints. We begin by defining the problem studied and putting it in the context of other, more famous combinatorial problems. Then we present two formulations for the problem and discuss how they may be tightened. We also study a case for which we may find a complete polyhedral description. Next, we present a decomposition-based solution approach which adapts the algorithm introduced in Part I. We then test the performance of our method against a set of standard instances drawn from the literature, which were appropriately modified. Altogether, our work is a practical contribution to the solvability of the integrated locomotive scheduling and driver assignment problem. We also show how the developed method may be extended to successful use in more general graph-theoretic contexts. 2026-01-07T05:08:15Z 2026-01-07T05:08:15Z 2026-01-06T13:13:30Z 2023 book ONIX_20260106T140303_9783961476503_54 https://library.oapen.org/handle/20.500.12657/109627 9783961476503 9783961476497 https://directory.doabooks.org/handle/20.500.12854/170768 eng open access image/jpeg Attribution 4.0 International https://library.oapen.org/bitstream/20.500.12657/109627/1/9783961476503.pdf FAU University Press 10.25593/978-3-96147-650-3 10.25593/978-3-96147-650-3 2c600dea-eece-4066-87be-da335e323fdb 9783961476503 9783961476497 AG Universitätsverlage 159 Erlangen open access |
| spellingShingle | Ganzzahlige Optimierung Diskrete Optimierung Graphfärbung Operations Research thema EDItEUR::P Mathematics and Science::PB Mathematics::PBU Optimization thema EDItEUR::P Mathematics and Science::PB Mathematics::PBV Combinatorics and graph theory thema EDItEUR::T Technology, Engineering, Agriculture, Industrial processes::TR Transport technology and trades::TRF Railway technology, engineering and trades Staszek, Jonasz Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints |
| title | Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints |
| title_full | Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints |
| title_fullStr | Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints |
| title_full_unstemmed | Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints |
| title_short | Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints |
| title_sort | modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2 list colouring problem with compatibility constraints |
| topic | Ganzzahlige Optimierung Diskrete Optimierung Graphfärbung Operations Research thema EDItEUR::P Mathematics and Science::PB Mathematics::PBU Optimization thema EDItEUR::P Mathematics and Science::PB Mathematics::PBV Combinatorics and graph theory thema EDItEUR::T Technology, Engineering, Agriculture, Industrial processes::TR Transport technology and trades::TRF Railway technology, engineering and trades |
| topic_facet | Ganzzahlige Optimierung Diskrete Optimierung Graphfärbung Operations Research thema EDItEUR::P Mathematics and Science::PB Mathematics::PBU Optimization thema EDItEUR::P Mathematics and Science::PB Mathematics::PBV Combinatorics and graph theory thema EDItEUR::T Technology, Engineering, Agriculture, Industrial processes::TR Transport technology and trades::TRF Railway technology, engineering and trades |
| url | ONIX_20260106T140303_9783961476503_54 |
| work_keys_str_mv | AT staszekjonasz modellingandsolvingtheintegratedlocomotiveschedulinganddriverassignmentproblemwithanextensiontograph2listcolouringproblemwithcompatibilityconstraints |