  Reorganizing bus frequency to cater for the actual travel demand can save the
cost of the public transport system significantly. Many, if not all, existing
studies formulate this as a bus frequency optimization problem which tries to
minimize passengers' average waiting time. However, many investigations have
confirmed that the user satisfaction drops faster as the waiting time
increases. Consequently, this paper studies the bus frequency optimization
problem considering the user satisfaction. Specifically, for the first time to
our best knowledge, we study how to schedule the buses such that the total
number of passengers who could receive their bus services within the waiting
time threshold is maximized. We prove that this problem is NP-hard, and present
an index-based algorithm with $(1-1/e)$ approximation ratio. By exploiting the
locality property of routes in a bus network, we propose a partition-based
greedy method which achieves a $(1-\rho)(1-1/e)$ approximation ratio. Then we
propose a progressive partition-based greedy method to further improve the
efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ approximation ratio.
Experiments on a real city-wide bus dataset in Singapore verify the efficiency,
effectiveness, and scalability of our methods.
