论文标题
运输网络的K-Interchange受限直径：一个交通便利的连接指标
The k-interchange-constrained diameter of a transit network: A connectedness indicator that accounts for travel convenience
论文作者
论文摘要
我们研究了最短路径问题的两个变体。鉴于整数K，k色限制和k-Interchange限制的最短路径问题分别寻求最短的路径，最短的路径不超过k颜色，而颜色不超过k-1的颜色交替。我们表明，当后者是可行的时候，前者是NP-HARD。这些问题的研究是由于使用基于直径的指标来评估过境网络拓扑结构的某些局限性。我们显然表明，诸如公交网络的直径或直接性的指标无法充分说明旅行方便，以衡量网络的连通性并提出新的网络指标，以解决k-Interchange构成的最短路径问题，旨在减轻这些限制。
We study two variants of the shortest path problem. Given an integer k, the k-color-constrained and the k-interchange-constrained shortest path problems, respectively seek a shortest path that uses no more than k colors and one that makes no more than k - 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-interchange-constrained shortest path problem, that aims at alleviating these limitations.
