The k-interchange-constrained diameter of a transit network: a connectedness indicator that accounts for travel convenience
Document Type
Journal Article
Publication Date
2020
Subject Area
planning - network design
Keywords
Graph theory, shortest path problem, computational complexity, transit networks, network indicators
Abstract
We study two variants of the shortest path problem. Given an integer k">kk, the k">kk-color-constrained and the k">kk-interchange-constrained shortest path problems, respectively, seek a shortest path that uses no more than k">kk colors and one that makes no more than k−1">k−1k−1 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 k">kk-interchange-constrained shortest path problem, that aims at alleviating these limitations.
Rights
Permission to publish the abstract has been given by Taylor&Francis, copyright remains with them.
Recommended Citation
Dehouche, N. (2020). The k-interchange-constrained diameter of a transit network: a connectedness indicator that accounts for travel convenience. Transportation Letters, Vol. 12(3), pp. 197-201.
