Engine Scheduling by Column Generation
This practically oriented thesis deals with the generation of short term schedules for switching engines at industrial in-plant railroads. The problem is related to the multiple-vehicle pickup and delivery problem with time windows. We consider combinatorial restrictions of the sequence of visited locations, introducing the concept of pattern concatenation. We show that the construction of schedules of minimal cost with respect to total travel time is NP-complete in the strong sense. Two models for the minimization problem are developed in this thesis. The first is an adaptation of a mixed integer program known from the literature. It is of polynomial size but the quality of its LP relaxation is provably poor. The second formulation is a set partitioning program where a variable corresponds to a feasible schedule for an engine, represented by the subset of visited requests. The number of variables is exponential in the size of the instance, and we propose to solve its LP relaxation by column generation. The pricing problem is a constrained shortest path problem and is proven to be NP-complete in the strong sense. A new lower bounding criterion is used to prune the search space of the princing dynamic programming algorithm. We extensively discuss our implementation and give computational results for practical problem instances. An investigation of the concept of patterns reveals its theoretical advantages as well. The large bibliography is intended to contribute in its own right and contains more than 100 references to column generation.
Diese praktisch orientierte Arbeit beschäftigt sich mit der Einsatzplanung von Rangierlokomotiven bei Industriebahnen. Das Problem ist verwandt mit dem multiple- vehicle pickup and delivery problem mit Zeitfenstern. Wir betrachten kombinatorische Einschränkungen in der Abfolge der zu besuchenden Orte. Hierzu führen wir das Konzept der Musterverkettung ein. Wir zeigen, dass das Erstellen eines Einsatzplans mit minimalen Kosten in bezug auf die Gesamtfahrzeiten NP-schwer im strengen Sinne ist. Zwei Modelle für das Minimierungsproblem werden vorgestellt. Das erste ist eine Anpassung eines aus der Literatur bekannten gemischt-ganzzahligen Programms. Es ist von polynomialer Größe, aber die Qualität seiner LP Relaxation ist beweisbar schlecht. Die zweite Formulierung ist ein Set Partitioning Programm, bei dem Variablen mit Einsatzplänen einer Lokomotive korrespondieren, repräsentiert durch die Teilmenge der besuchten Aufträge. Die Zahl der Variablen ist exponentiell in der Größe der Instanz und zur Lösung der LP Relaxation wird Spaltengenerierung vorgeschlagen. Das Pricingproblem ist ein eingeschränktes Kürzeste-Wege Problem und NP-schwer im strengen Sinne. Eine auf Dualvariablen basierende untere Schranke wird zur Reduzierung des Suchraums des zur Lösung verwendeten Dynamischen Programms eingesetzt. Wir diskutieren ausführlich unsere Implementation und geben Rechenergebnisse für praktische Instanzen an. Eine Untersuchung des Konzept der Musterverkettung zeigt auch deren theoretisch günstige Eigenschaften. Die lange Bibliographie, mit insbesondere über 100 Eintägen zur Spaltengenerierung, verstehen wir als Beitrag von eigenständiger Bedeutung.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved