  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.
