In this thesis, we have analyzed the complexity of different graph problems that are all motivated by problems that arise in public transport optimization. Precisely, we have regarded the integration of the Transfer Quality Maximization Problem and the Vehicle Scheduling Problem in a Variable Timetable for existing, but ill-synchronized, timetables. The resulting graph problems are located in the fields of MAXIMUM GENERALIZED Quasi-Assignment problems, Maximum Feasible Subsystem of Linear Relations problems and Minimum Set Cover problems. Our indepth analysis demonstrates that all these problems are NP-hard, even on very restricted, seemingly trivial structures. It is hence not surprising at all that even powerful commercial solvers fail to solve instances of larger sizes. It is more than justified to approach these problems with heuristics. For various special cases, we have been able to state algorithms with a proven approximation factor. Our numerical results cannot replace an in-depth computational study, but give an insight in the behavior of the considered algorithms. As long as the LP relaxation is efficiently computable, it is a good choice to approach the integrated problem IntPr as well as the Semi-integrated Problem MTQP-FVS with LP-rounding heuristics. With increasing problem sizes and shift variability, how ever, this is not an option anymore. For the MTQP-FVS, a dynamic programing algorithm heuristic DP, which we present, delivers good and fast results also on very large instances. Unfortunately, in contrast to the MIP-based methods or a Primal-Dual heuristic, which we introduce, DP provides less modeling power for real world constraints. It is an interesting open question how the efficiency of DP can be exploited within a realistic modeling framework.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Algorithms and complexity of timetable synchronization and vehicle scheduling problems in an integrated approach


    Contributors:

    Published in:

    Mathematik ; 1-322


    Publication date :

    2013


    Size :

    322 Seiten, Bilder, Tabellen, Quellen



    Type of media :

    Theses


    Type of material :

    Print


    Language :

    English




    Integrated public transport timetable synchronization with vehicle scheduling

    Liu, Tao / Ceder, Avishai (Avi) / Chowdhury, Subeh | Taylor & Francis Verlag | 2017


    The Complexity of Timetable Construction Problems

    Cooper, T. B. / Kingston, J. H. | British Library Conference Proceedings | 1995


    Timetable Synchronization for Buses

    Ceder, Avishai / Tal, Ofer | Springer Verlag | 1999


    Vehicle and Crew Scheduling with Flexible Timetable

    Keri, A. / Haase, K. / Gesellschaft fur Operations Research | British Library Conference Proceedings | 2007


    Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach

    Zekang Lan / Shiwei He / Rui Song et al. | DOAJ | 2019

    Free access