Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand

Sheng Wang, Yuan Sun, Christopher Musco, Zhifeng Bao

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


In this paper, we make a first attempt to incorporate both commuting demand and transit network connectivity in bus route planning (CT-Bus), and formulate it as a constrained optimization problem: planning a new bus route with k edges over an existing transit network without building new bus stops to maximize a linear aggregation of commuting demand and connectivity of the transit network. We prove the NP-hardness of CT-Bus and propose an expansion-based greedy algorithm that iteratively scans potential candidate paths in the network. To boost the efficiency of computing the connectivity of new networks with candidate paths, we convert it to a matrix trace estimation problem and employ a Lanczos method to estimate the natural connectivity of the transit network with a guaranteed error bound. Furthermore, we derive upper bounds on the objective values and use them to greedily select candidates for expansion. Our experiments conducted on real-world transit networks in New York City and Chicago verify the efficiency, effectiveness, and scalability of our algorithms.
Original languageEnglish
Title of host publicationACM Special Interest Group on Management of Data Conference (SIGMOD) 2021
EditorsGuoliang Li, Zhanhuai Li, Stratos Idreos, Divesh Srivastava
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages14
ISBN (Print)9781450383431
Publication statusPublished - 18 Jun 2021

Cite this