The k-interchange-constrained diameter of a transit network: a connectedness indicator that accounts for travel convenience
- 30 January 2019
- journal article
- research article
- Published by Taylor & Francis in Transportation Letters
- Vol. 12 (3) , 197-201
Abstract
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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Rapid transit network design for optimal cost and origin–destination demand captureComputers & Operations Research, 2013
- Applications of Graph Theory and Network Science to Transit Network DesignTransport Reviews, 2011
- Geographic information systems and science: today and tomorrowAnnals of GIS, 2009
- Characterizing metro networks: state, form, and structureTransportation, 2009
- Transit network design and scheduling: A global reviewTransportation Research Part A: Policy and Practice, 2008
- Simulated Annealing–Genetic Algorithm for Transit Network OptimizationJournal of Computing in Civil Engineering, 2006
- Compared Analysis of Metro Networks Supported by Graph TheoryNetworks and Spatial Economics, 2005
- Formal-Language-Constrained Path ProblemsSIAM Journal on Computing, 2000
- Vertex coverings by monochromatic cycles and treesJournal of Combinatorial Theory, Series B, 1991
- A heuristic approach to hard constrained shortest path problemsDiscrete Applied Mathematics, 1985