Online and Real-Time Dispatching Problems

This thesis is concerned with real-time dispatching problems arising in transport and logistics. The main problem considered is the tram dispatch problem in depots of local transport companies. Based on the methods and results obtained for this problem, similar methods are presented for a locomotive dispatching problem in terminal stations and for the ship planning problem in container terminals. In the tram dispatch problem, arriving trams must be stored at a location in the depot and be assigned to a round trip of the next schedule period. For this stack sorting problem, linear and quadratic integer programs for minimizing two objectives are given: the required amount of shunting and the number of type mismatches for the assignment of trams to round trips. Both problems are shown to be NP-hard even for the subproblem in which the assignment of trams to locations is given. The real-world tram dispatch problem is an online problem that must be solved iteratively within a severe time bound. Caused for instance by delays, the trams usually arrive in an order differing substantially from the scheduled order. Since the gap between two arrivals is close, an assignment has to be computed fast. Computational experiments for real-world and random data show that the presented real-time algorithms based on combinatorial optimization models yield good and often optimal results. Competitive analysis for the online tram dispatch problem show a bad worst-case performance for deterministic and randomized online algorithms.Die vorliegende Arbeit beschäftigt sich mit Echtzeitdispositionsproblemen in Verkehr und Logistik. Das wesentliche Problem, welches in dieser Arbeit behandelt wird ist, das Tramdispositionsproblem in Betriebshöfen des ÖPNV. Basierend auf den Ergebnissen für dieses Problem werden analoge Methoden für ein Lokomotivendispositionsproblem in Kopfbahnhöfen und für ein Stauplanungsproblem in Containerterminals vorgestellt. Im Tramdispositionsproblem müssen einfahrende Trams Stellplätzen im Depot und Umläufen der nächsten Fahrplanperiode zugewiesen werden. Für dieses Stacksortierungsproblem werden ganzzahlige lineare und quadratische Programme für zwei Zielfunktionen vorgestellt: der Minimierung des Rangieraufwands und der Minimierung der Zuweisungen von Trams falschen Typs zu den Umläufen. Beide Probleme erweisen sich als NP-schwer selbst für den Fall, daß eine Zuweisung zu Depotpositionen gegeben ist. Das Echtzeit-Tramdispositionsproblem ist ein Online-Problem, welches iterativ innerhalb enger Zeitgrenzen gelöst werden muß. Beispielsweise aufgrund von Staus treffen die Trams in einer anderen Reihenfolge als vom Fahrplan vorgegeben im Depot ein. Da der Zeitraum zwischen zwei Einfahrten gering ist, muß eine Zuweisung schnell berechnet werden. Rechenergebnisse für reale und zufällige Daten zeigen, daß die vorgestellten Methoden der kombinatorischen Optimierung gute, oft optimal Ergebnisse liefern. Theoretische Ergebnisse einer kompetitiven Analyse zeigen, daß sowohl deterministische als auch randomisierte Online-Algorithmen schlechte Ergebnisse liefern