Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

9-2020

Abstract

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 − ρ)(1 − 1/e) approximation ratio. Then we propose a progressive partition-based greedy method to further improve the efficiency while achieving a (1 − ρ)(1 − 1/e − ε) approximation ratio. Experiments on a real city-wide bus dataset in Singapore verify the efficiency, effectiveness, and scalability of our methods

Keywords

bus frequency scheduling optimization, user waiting time minimization, approximate algorithm.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

DASFAA 2020: Proceedings of the 25th International Conference on Database Systems for Advanced Applications, Jeju, South Korea, September 24–27

Volume

12113

First Page

192

Last Page

208

ISBN

9783030594169

Identifier

10.1007/978-3-030-59416-9_12

Publisher

Springer

City or Country

Cham

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/978-3-030-59416-9_12

Download

Share

COinS