Modelling and solving the integrated locomotive scheduling and driver assignment problem with an extension to graph 2-list-colouring problem with compatibility constraints

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.