Highlights Models the scheduling problem as an optimization problem with congruence constraints. Proposes a new graph representation of the problem. Provides optimal inapproximability results for the optimization problem. Exposes the close bounds that relate this problem with the MAX DICUT problem. Customizes and applies approximation algorithms for MAX DICUT in real case studies.

    Abstract This paper aims to synchronize timetables in a transit network so as to minimize the total passenger transfer waiting time. Assuming a fixed headway for each line, we first formulate the problem as an optimization problem with congruence constraints. We show that the problem is NP-hard, and investigate several special cases of the problem that are solvable in polynomial time. Furthermore, we show that the local search for the general problem is equivalent to the well-studied maximum directed cut problem. As such, we use an approximation algorithm for the maximum directed cut problem to solve the timetable synchronization problem. We assess the quality of the algorithm on a real-world case study, and show that our algorithm significantly outperforms the state-of-the-art in the literature. Lastly, we relax the fixed headway assumption, and propose an efficient recursive quasi-linear time algorithm to minimize the total transfer waiting time in this general setting.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Transit timetable synchronization for transfer time minimization


    Beteiligte:
    Abdolmaleki, Mojtaba (Autor:in) / Masoud, Neda (Autor:in) / Yin, Yafeng (Autor:in)


    Erscheinungsdatum :

    2019-12-05


    Format / Umfang :

    17 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Optimizing Timetable Synchronization for Rail Mass Transit

    Wong, Rachel C.W. | Online Contents | 2008


    Optimizing Timetable Synchronization for Rail Mass Transit

    Wong, R.C.W. / Yuen, T.W.Y. / Fung, K.W. et al. | British Library Online Contents | 2008


    XML-Based Transit Timetable System

    Sun, W. / Bernstein, D. / Transportation Research Board | British Library Conference Proceedings | 2002


    XML-Based Transit Timetable System

    Sun, Wu / Bernstein, David | Transportation Research Record | 2002


    XML-Based Transit Timetable System

    Sun, Wu | Online Contents | 2002