We study two variants of the shortest path problem. Given an integer , the -color-constrained and the -interchange-constrained shortest path problems, respectively, seek a shortest path that uses no more than colors and one that makes no more than alternations of colors. We show that the former problem is NP-hard, when the latter is tractable. The study of these problems is motivated by some limitations in the use of diameter-based metrics to evaluate the topological structure of transit networks. We notably show that indicators such as the diameter or directness of a transit network fail to adequately account for travel convenience in measuring the connectivity of a network and propose a new network indicator, based on solving the -interchange-constrained shortest path problem, that aims at alleviating these limitations.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    The k-interchange-constrained diameter of a transit network: a connectedness indicator that accounts for travel convenience


    Beteiligte:

    Erschienen in:

    Transportation Letters ; 12 , 3 ; 197-201


    Erscheinungsdatum :

    2020-03-15


    Format / Umfang :

    5 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Interchange - international travel/traffic information exchange

    Davies, P. / Booth, J. / Planning and Transport Research and Computation | British Library Conference Proceedings | 1994


    Influence of Urban Rail Transit Interchange Station Location on Passenger Interchange Route Selection

    Li JIANG / Jiayao BAO / Ming GAO et al. | DOAJ | 2024

    Freier Zugriff

    The interchange of pan-European travel information

    Davies, P. / Marsh, D. / Planning and Transport Research and Computation International Association; European Transport, Highways and Planning | British Library Conference Proceedings | 1993


    Pan-european travel information exchange:the interchange project

    Davies,P. / Marsh,D. / Castle Rock Consultants,GB et al. | Kraftfahrwesen | 1993


    Data-driven study of transit and bicycle interchange

    Wu, Fei / Zhang, Meng / Zhang, Mengmeng et al. | British Library Conference Proceedings | 2022