Library

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • ddc:080  (1)
Years
Keywords
Language
  • 1
    Publication Date: 2023-01-25
    Description: Die vorliegende Dissertation beschäftigt sich mit der Optimierung der Fahrzeugeinsatzplanung im öffentlichen Personennahverkehr. Dieses Problem ist für die meisten praxisrelevanten Fälle schwierig (Ar'P-schwer). In dieser Arbeit präsentieren wir Methoden der ganzzahligen linearen Programmierung zur Lösung dieses Planungsproblems. "Vernünftige" mathematische Formulierungen des Fahrzeugeinsatzplanungsproblems basieren auf Netzwerkfluß-Modellen und ent sprechenden ganzzahligen linearen Programmen (LP). Dies sind sogenannte bogenorientierte Mehrgüterfluß-Modelle bzw. pfadorientierte SetPartitioning-Modelle. Wir beschäftigen uns mit beiden Ansätzen, der Schwerpunkt liegt aber auf dem bogenorientierte Mehrgüterfluß-Modell Mathematisch bearbeiten wir diese Modelle mit Branch-und-Cut- bzw. Branch-und-Cutund-Price-Methoden. Reale Anwendungen fü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öglicht, LPs dieser Art mit rund 70 Millionen Variablen zu lösen. Für den bogenorientierten (Mehrgüter)Fluß-Zugang beschreiben wir ausführlich, wie Lagrange-Relaxationen sowie die LP-Relaxation effizient gelöst werden. Zusätzlich schlagen wir eine Heuristik vor, die schnell gute Lösungen erzeugt. Diese Heuristik beruht auf einem sog. Schedule-FirstClusterSecond-Ansatz. Eine zentrale Aufgabe bei der Lösung dieser primalen und dualen Probleme ist dabei die effiziente Behandlung von Problemen mit einem Depot. Wir zeigen, daß das bogenorientierte Mehrgüterfluß-Modell durch eine geeignete Anwendung der Dantzig-Wolfe-Dekomposition in ein pfadorientiertes SetPartitioning-Modell überführt werden kann. Der zweite Teil dieser Arbeit prä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ässig und stabil. Die mit diesen Verfahren durchgeführten Testläufe lieferten hervorragende Ergebnisse: Bis auf ein Problem können alle Beispiele optimal gelöst werden. Die Lösungen des Branch-and-Cut-Verfahrens wurden auch mit den Planungsergebnissen der in der Praxis gegenwärtig eingesetzten Verfahren verglichen: Wir konnten zusätzlich mehrere Fahrzeuge einsparen sowie eine Kostenreduktion von bis zu 10 % aufzeigen. Der mögliche Nutzen dieser Methoden ist enorm. Beispielsweise rechnet die BVG damit, den Planungsprozeß mit den von uns entwickelten Softwaretools deutlich straffen und jährlich Einsparungen in Höhe von rund 100 Millionen Mark erzielen zu kö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ür Informatik, Verkehrs und Umweltplanung mbH, Berlin) integriert. Darüber hinaus hat auch die Forschungsabteilung der SIEMENS AG in München dieses System erworben.
    Keywords: ddc:080
    Language: English
    Type: doctoralthesis , doc-type:doctoralThesis
    Format: application/pdf
    Format: application/postscript
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...