Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand

Sheng Wang, Yuan Sun, Christopher Musco, Zhifeng Bao

    Research output: Contribution to journalConference articlepeer-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 (US)
    Pages (from-to)1906-1919
    Number of pages14
    JournalProceedings of the ACM SIGMOD International Conference on Management of Data
    StatePublished - 2021
    Event2021 International Conference on Management of Data, SIGMOD 2021 - Virtual, Online, China
    Duration: Jun 20 2021Jun 25 2021


    • bus route planning
    • commuting demand
    • trajectory
    • transit connectivity

    ASJC Scopus subject areas

    • Software
    • Information Systems


    Dive into the research topics of 'Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand'. Together they form a unique fingerprint.

    Cite this