Publication Type

Journal Article

Version

acceptedVersion

Publication Date

9-2022

Abstract

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.

Keywords

bus frequency scheduling optimization, user waiting time minimization, approximation algorithm

Discipline

Databases and Information Systems | Theory and Algorithms | Transportation

Research Areas

Data Science and Engineering

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

34

Issue

9

First Page

4484

Last Page

4498

ISSN

1041-4347

Identifier

10.1109/TKDE.2020.3036573

Publisher

IEEE

Embargo Period

4-15-2021

Copyright Owner and License

LARC and Authors

Additional URL

https://doi.org/10.1109/TKDE.2020.3036573

Download

Share

COinS