@inproceedings{BorndoerferLoebelWeider2002, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Verkehr}, series = {Heureka '02}, booktitle = {Heureka '02}, publisher = {Forschungsgesellschaft f{\"u}r Straßen- und Verkehrswesen}, address = {K{\"o}ln}, pages = {77 -- 98}, year = {2002}, language = {en} } @phdthesis{Loebel, author = {L{\"o}bel, Andreas}, title = {Optimal Vehicle Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10169}, abstract = {Die vorliegende Dissertation besch{\"a}ftigt sich mit der Optimierung der Fahrzeugeinsatzplanung im {\"o}ffentlichen Personennahverkehr. Dieses Problem ist f{\"u}r die meisten praxisrelevanten F{\"a}lle schwierig (Ar'P-schwer). In dieser Arbeit pr{\"a}sentieren wir Methoden der ganzzahligen linearen Programmierung zur L{\"o}sung dieses Planungsproblems. "Vern{\"u}nftige" mathematische Formulierungen des Fahrzeugeinsatzplanungsproblems basieren auf Netzwerkfluß-Modellen und ent sprechenden ganzzahligen linearen Programmen (LP). Dies sind sogenannte bogenorientierte Mehrg{\"u}terfluß-Modelle bzw. pfadorientierte SetPartitioning-Modelle. Wir besch{\"a}ftigen uns mit beiden Ans{\"a}tzen, der Schwerpunkt liegt aber auf dem bogenorientierte Mehrg{\"u}terfluß-Modell Mathematisch bearbeiten wir diese Modelle mit Branch-und-Cut- bzw. Branch-und-Cutund-Price-Methoden. Reale Anwendungen f{\"u}hren zu riesigen LPs mit einigen Millionen ganzzahligen Variablen. Die Behandlung solcher LPs erfordert Spalten-Erzeugungs- Verfahren (auch Column-Generation-Verfahren genannt). Basierend auf Lagrange-Relaxationen entwickeln wir hierzu neue Verfahren zur Auswahl der zu erzeugenden Spalten, die wir Lagrange-Pricing nennen. Lagrange-Pricing-Techniken haben es erstmalig erm{\"o}glicht, LPs dieser Art mit rund 70 Millionen Variablen zu l{\"o}sen. F{\"u}r den bogenorientierten (Mehrg{\"u}ter)Fluß-Zugang beschreiben wir ausf{\"u}hrlich, wie Lagrange-Relaxationen sowie die LP-Relaxation effizient gel{\"o}st werden. Zus{\"a}tzlich schlagen wir eine Heuristik vor, die schnell gute L{\"o}sungen erzeugt. Diese Heuristik beruht auf einem sog. Schedule-FirstClusterSecond-Ansatz. Eine zentrale Aufgabe bei der L{\"o}sung dieser primalen und dualen Probleme ist dabei die effiziente Behandlung von Problemen mit einem Depot. Wir zeigen, daß das bogenorientierte Mehrg{\"u}terfluß-Modell durch eine geeignete Anwendung der Dantzig-Wolfe-Dekomposition in ein pfadorientiertes SetPartitioning-Modell {\"u}berf{\"u}hrt werden kann. Der zweite Teil dieser Arbeit pr{\"a}sentiert die Rechenergebnisse zu den von uns entwickelten und implementierten Verfahren. Diese Untersuchungen basieren auf realen Testdaten von drei großen deutschen Nahverkehrsunternehmen. Die implementierten Codes arbeiten zuverl{\"a}ssig und stabil. Die mit diesen Verfahren durchgef{\"u}hrten Testl{\"a}ufe lieferten hervorragende Ergebnisse: Bis auf ein Problem k{\"o}nnen alle Beispiele optimal gel{\"o}st werden. Die L{\"o}sungen des Branch-and-Cut-Verfahrens wurden auch mit den Planungsergebnissen der in der Praxis gegenw{\"a}rtig eingesetzten Verfahren verglichen: Wir konnten zus{\"a}tzlich mehrere Fahrzeuge einsparen sowie eine Kostenreduktion von bis zu 10 \% aufzeigen. Der m{\"o}gliche Nutzen dieser Methoden ist enorm. Beispielsweise rechnet die BVG damit, den Planungsprozeß mit den von uns entwickelten Softwaretools deutlich straffen und j{\"a}hrlich Einsparungen in H{\"o}he von rund 100 Millionen Mark erzielen zu k{\"o}nnen, siehe den Artikel Auf Sparkurs zum Ziel im Rheinischer Merkur, Nummer 39, von Schmidt [1997] Teile der vorgestellten Methoden wurden bereits in die Planungssysteme BERTA (der Berliner Verkehrsbetriebe (BVG)) und MICROBUS II (der IVU Gesellschaft f{\"u}r Informatik, Verkehrs und Umweltplanung mbH, Berlin) integriert. Dar{\"u}ber hinaus hat auch die Forschungsabteilung der SIEMENS AG in M{\"u}nchen dieses System erworben.}, language = {en} }