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.
The k-interchange-constrained diameter of a transit network: a connectedness indicator that accounts for travel convenience
Transportation Letters ; 12 , 3 ; 197-201
2020-03-15
5 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Interchange - international travel/traffic information exchange
British Library Conference Proceedings | 1994
|DOAJ | 2024
|The interchange of pan-European travel information
British Library Conference Proceedings | 1993
|Pan-european travel information exchange:the interchange project
Kraftfahrwesen | 1993
|Data-driven study of transit and bicycle interchange
British Library Conference Proceedings | 2022
|