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 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. Die integrierte Behandlung von Planungsproblemen, die bislang getrennt und sequentiell betrachtet werden, wird schon seit Längerem untersucht, da im erweiterten Entscheidungsraum eines integrierten Problems bessere Lösungen gefunden werden können. In dieser Arbeit wird das integrierte Lokomotivplanungs- und Lokführerzuweisungsproblem im Schienengüterverkehr untersucht. Wir betrachten auch die Verallgemeinerung dieses Problems, das wir Problem der 2-Listen-Färbung von Graphen mit Kompatibilitätsnebenbedingungen nennen. Diese Arbeit ist in zwei Teile gegliedert. Teil I befasst sich mit der Modellierung und Lösung des integrierten Lokomotivplanungs- und Lokführerzuweisungsproblems im Schienengüterverkehr. Nach einem Literaturüberblick stellen wir ein neuartiges Optimierungsmodell für das vorliegende Problem und einen Ansatz zur Verbesserung seiner Formulierung vor. Anschließend leiten wir einen dekompositionsbasierten Lösungsansatz für das Problem her. Um die globale Zulässigkeit der Lösungen für die dekomponierten Teilprobleme zu gewährleisten, präsentieren wir vier Klassen von gültigen Ungleichungen. Außerdem entwickeln wir eine Presolve-Heuristik. Anschließend testen wir unseren Algorithmus anhand zweier Sätze von Benchmark-Instanzen. Im Allgemeinen ermöglichten die vorgestellten Methoden eine Erstellung von Lokomotivfahrplänen und Lokführerzuweisungen in weniger als zwei Stunden. In Teil II untersuchen wir eine Verallgemeinerung des integrierten Lokomotivplanungs- und Lokführerzuweisungsproblems, das wir als Problem der 2-Listen-Färbung von Graphen mit Kompatibilitätsnebenbedingungen (G2LC-CC) bezeichnen. Wir beginnen unsere Überlegungen mit der Definition des untersuchten Problems und stellen es in den Kontext anderer, bekannterer kombinatorischer Probleme. Anschließend stellen wir zwei Formulierungen für das Problem vor und erörtern, wie sie verbessert werden können. Wir untersuchen auch einen Fall, für den eine vollständige polyedrische Beschreibung gegeben werden kann. Anschließend stellen wir einen dekompositionsbasierten Lösungsansatz vor, der eine Anpassung des in Teil I vorgestellten Algorithmus darstellt. Anschließend testen wir die Leistungsfähigkeit unserer Methode anhand einer Reihe von Standardinstanzen aus der Literatur, die entsprechend modifiziert wurden. Insgesamt ist unsere Arbeit ein praktischer Beitrag zur Lösbarkeit des integrierten Lokomotivfahrplanungs- und Lokführerzuordnungsproblems. Wir zeigen auch, wie die von uns entwickelte Methode für einen erfolgreichen Einsatz in allgemeineren graphentheoretischen Kontexten erweitert werden kann.