Towards an optimal bus frequency scheduling: When the waiting time matters

• Main Authors: MO, Songsong, BAO, Zhifeng, ZHENG, Baihua, PENG, Zhiyong
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: bus frequency scheduling optimization; user waiting time minimization; approximation algorithm; Databases and Information Systems; Theory and Algorithms; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/5895; https://ink.library.smu.edu.sg/context/sis_research/article/6898/viewcontent/19._Towards_an_Optimal_Bus_Frequency_Scheduling_When_the_Waiting_Time_Matters_IEEE_TKDE_Nov2020.pdf
• Institution: Singapore Management University

Reorganizing bus frequencies to cater for actual travel demands can significantly save the cost of the public transport system. 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 for that achieves a (1)(1 1/e) approximation ratio. Then we propose a progressive partition-based greedy method for to further boost the efficiency while achieving a (1)(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.