| With the development of urbanization,the population gradually gathers in developed cities,which further leads to an increase in the number of urban vehicles.With the increase in the number of motor vehicles,the proportion of car trips has also increased significantly.This has led to increasingly serious urban traffic congestion.Therefore,solving the traffic congestion has become one of the important tasks of urban management.As an important way to solve urban traffic congestion,public transportation has attracted widespread attention from the government and academia.Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system.Many,if not all,previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time.On the other hand,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 can be maximized.We propose two variants of the problem,FAST and FASTCO,to cater for different application needs and prove that both are NP-hard.To solve FAST effectively and efficiently,we first present an index-based(1-1/e)-approximation algorithm.By exploiting the locality property of routes in a bus network,we further propose a partition-based greedy method that achieves a(1-p)(1-1/e) approximation ratio.Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a(1-p)(1-1/e-ε)approximation ratio.For the FASTCO problem,two greedy-based heuristic methods are proposed.Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency,effectiveness,and scalability of our methods in addressing FAST and FASTCO respectively.Besides,we demonstrate a satisfaction-boosting bus scheduling assistant,which assists users to find an optimal bus schedule.This system performs bus scheduling based on the constraints specified by the user in either a coarse-grained or a fine-grained manner,supports different explorations with a varying number of constraints,and provides analysis to quantify the performance of bus schedules and presents the results in a visually pleasing way. |
