A graph theoretic approach to rapid transit network design

Abstract

Designing rapid transport networks that maximise ridership or coverage is a critical challenge in transportation planning. However, this is an NPhard problem, and given the investment required to build these networks, designing the best network possible is a priority. In this research, we propose a novel data-driven approach to designing transport networks that automatically identifies station locations and constructs an optimised network that maximises ridership within a fixed budget. Our approach uses a combination of density based scanning, spatial partitioning, branch and bound, and genetic algorithms to construct an optimised network. We evaluate candidate solutions based on their expected modal shift, which measures the number of journeys the new network is expected to capture. Our approach is flexible and can also be applied to expand existing networks, optimise for a coverage goal, or design multimodal networks that integrate feeder networks with rapid transport stations. To evaluate the effectiveness of our approach, we present a method for generating synthetic datasets that can be used to test our algorithm and other network design algorithms. Our approach was successful in testing, designing networks that achieved good expected modal shift on both synthetic datasets and in a case study on the city of Bogotá, Colombia. On the Bogotá dataset one solution with a e200 million budget achieved an expected modal shift of 4.87%. Overall, our approach represents a contribution to the field of transportation planning by providing a data-driven method which can design complete networks given only travel survey data. Additionally we show how the problem can be framed using graph theory and parts of the problem can be mapped to the heaviest subgraph problem and the travelling salesman problem. Future work could build on our method by improving evaluation accuracy using agent based simulation or using graph neural networks in place of branch and bound.