Despite this observation, in the practice of planning public transportation, only a few months ago OR decision support has still been limited to operations planning (vehicle scheduling, duty scheduling, crew rostering). The present thesis describes the optimization techniques that were deployed in computing the very first optimized timetable that went into daily service: the 2005 timetable of Berlin Underground. Compared to the former timetable, with the authors timetable the passengers of Berlin Underground are offered simultaneously improvements in three key criteria, which typically are conflicting: transfer waiting time, dwell time of trains, and number of trains that are required for the operation. The basic graph model, the periodic event scheduling problem (PESP), is known for 15 years and it had attracted many research groups. Nevertheless, this thesis collects significant progress that has been made only recently on issues like solution strategies or modeling capabilities. The latter include additional timetabling modeling features (train coupling/train sharing, bundling of lines of similar speed in order to increase track capacity), theoretical evidence that the symmetry requirement for periodic timetables cannot be expressed by only using (integer-valued) PESP constraints, and even the integration of further planning tasks in public transport, such as line planning. On the theory side, a more precise notion of the asymptotical complexity of the PESP is given, by providing a MAXSNP-hardness proof as a kind of negative result. On the positive side, the design of more efficient algorithms gave rise to a much deeper understanding of cycle bases of graphs, another very hot topic in discrete mathematics during the last three years. In 2005, this culminated in both, drawing the complete map for the seven relevant classes of cycle bases, and the design of the fastest algorithms for the minimum directed cycle basis problem and for the minimum 2-basis problem. These theoretical considerations are complemented by an exhaustive computational study. For the first time, the performance of a cut-and-branch algorithm, constraint programming, and even a genetic algorithm was compared for periodic timetable optimization. The cut-and-branch algorithm and the genetic algorithm turned out to be most convincing. On the one hand, the genetic algorithm has a slight advantage with respect to independence of parameter settings. On the other hand, the quality of the solutions obtained by the cut-and-branch algorithm was somewhat better.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Periodic timetable optimization in public transport


    Weitere Titelangaben:

    Periodische Fahrplanoptimierung im öffentlichen Verkehr


    Beteiligte:

    Erschienen in:

    Dissertation.de. ; 1250 ; 1-333


    Erscheinungsdatum :

    2006


    Format / Umfang :

    333 Seiten, Bilder, Tabellen, Quellen



    Medientyp :

    Hochschulschrift


    Format :

    Print


    Sprache :

    Englisch




    Periodic timetable optimization in public transport

    Liebchen, Christian | TIBKAT | 2006




    Performance of Algorithms for Periodic Timetable Optimization

    Liebchen, Christian / Proksch, Mark / Wagner, Frank H. | Springer Verlag | 2008


    User perspectives in public transport timetable optimisation

    Parbo, Jens / Nielsen, Otto Anker / Prato, Carlo Giacomo | Elsevier | 2014