Diese Arbeit beschreibt den Algorithmus IS-OPT, welcher der erste Algorithmus ist, der integrierte Umlauf- und Dienstplanungsprobleme für mittelgroße Verkehrsunternehmen löst und dabei alle betrieblichen Einzelheiten berücksichtigt. Seine Lösungen können daher direkt in den täglichen Betrieb übernommen werden. Im ersten Kapitel werden mathematische Modelle für verschiedenen Probleme aus dem Planungsprozess von Nahverkehrsunternehmen beschrieben. Es werden Ansätze zur Integration der einzelnen Probleme untersucht. In diesem Kapitel werden außerdem das Umlauf- und das Dienstplanungsproblem eingeführt. Kapitel 2 motiviert, warum Integration von Umlauf- und Dienstplanung hilfreich ist oder in welchen Fällen sie sogar unabdingbar ist; es gibt einen Überblick über die vorhanden Literatur zur integrierten Umlauf- und Dienstplanung und umreißt seinen Algorithmus IS-OPT. Die weiteren Kapitel behandeln die in IS-OPT verwendeten Methoden: In Kapitel 3 beschreibt der Autor, wie Spaltenerzeugung für lineare Programme mit Lagrange-Relaxierung und Subgradienten-Verfahren kombiniert werden kann. In Kapitel 4 wird seine Variante der proximalen Bündelmethode beschrieben. Diese wird benutzt um näherungsweise primale und duale Lösungen von lineare Programmen zu berechnen. Seine Variante ist angepasst, um auch mit ungenauer Funktionsauswertung und Epsilon-Subgradienten arbeiten zu können. Er zeigt die Konvergenz dieser Variante unter bestimmten Annahmen. Kapitel 5 behandelt das Erzeugen von Diensten für das Dienstplanungsproblem. Dieses Problem ist als ein Kürzeste-Wege-Problem mit nichtlinearen Nebenbedingungen und fast linearer Zielfunktion modelliert. Er löst es, indem zuerst Schranken für die reduzierten Kosten von Diensten, die bestimmte Knoten benutzen, berechnet werden. Diese Schranken werden benutzt, um in einem Tiefensuchalgorithmus den Suchbaum klein zu halten. Im Kapitel 6 präsentiert er die neu entwickelte Heuristik 'Rapid Branching', die eine ganzzahlige Lösung des integrierten Problems berechnet. Rapid Branching kann als eine spezielle Branch-and-Bound-Heuristik gesehen werden, welche die Bündelmethode benutzt. In den Knoten des Suchbaums können mehrere Variablen auf einmal fixiert werden, die mit Hilfe einer Perturbationsheuristik ausgewählt werden. In Kapitel 7 schließlich zeigt er, daß er mit IS-OPT auch große Probleminstanzen aus der Praxis lösen können und dabei bis zu 5% der Fahrzeug- und Dienstkosten sparen können.

    This thesis describes the algorithm IS-OPT that integrates scheduling of vehicles and duties in public bus transit. IS-OPT is the first algorithm which solves integrated vehicle and duty scheduling problems arising in medium sized carriers such that its solutions can be used in daily operations without further adaptions. This thesis is structured as follows: The first chapter highlights mathematical models of the planning process of public transit companies and examines their potential for integrating them with other planning steps. It also introduces descriptions of the vehicle and the duty scheduling problem. Chapter 2 motivates why it can be useful to integrate vehicle and duty scheduling, explains approaches of the literature, and gives an outline of his algorithm IS-OPT. The following chapters go into the details of the most important techniques and methods of IS-OPT: In Chapter 3 the author describes how he uses Lagrangean relaxation in a column generation framework. Next, in Chapter 4, he describes a variant of the proximal bundle method (PBM) that is used to approximate linear programs occurring in the solution process. He introduces here a new variant of the PBM which is able to utilize inexact function evaluation and the use of epsilon-subgradients. He also shows the convergence of this method under certain assumptions. Chapter 5 treats the generation of duties for the duty scheduling problem. This problem is modeled as a resourceconstraint- shortest-path-problem with non-linear side constraints and nearly linear objective function. It is solved in a two-stage approach. At first he calculates lower bounds on the reduced costs of duties using certain nodes by a new inexact label-setting algorithm. Then he uses these bounds to speed up a depth-first-search algorithm that finds feasible duties. In Chapter 6 he presents the primal heuristic of IS-OPT that solves the integrated problem to integrality. He introduces a new branch-and-bound based heuristic which he calls rapid branching. Rapid branching uses the proximal bundle method to compute lower bounds, it introduces a heuristic node selection scheme, and it utilizes a new branching rule that fixes sets of many variables at once. The common approach to solve the problems occurring in IS-OPT is to trade inexactness of the solutions for speed of the algorithms. This enables, as he shows in Chapter 7, to solve large real world integrated problems by IS-OPT. The scheduled produced by IS-OPT save up to 5% of the vehicle and duty cost of existing schedules of regional and urban public transport companies.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Integration of vehicle and duty scheduling in public transport


    Weitere Titelangaben:

    Integration der Umlauf- und Dienstplanungsprobleme in öffentlichen Verkehrsunternehmen


    Beteiligte:

    Erscheinungsdatum :

    2007


    Format / Umfang :

    214 Seiten, Bilder, Tabellen, Quellen



    Medientyp :

    Hochschulschrift


    Format :

    Print


    Sprache :

    Englisch




    Integration of vehicle and duty scheduling in public transport

    Weider, Steffen | GWLB - Gottfried Wilhelm Leibniz Bibliothek | 2007


    Integration of vehicle and duty scheduling in public transport

    Weider, Steffen | TIBKAT | 2007

    Freier Zugriff