Towards an Optimal Bus Frequency Scheduling: When the Waiting Time Matters
| Autor: | Baihua Zheng, Songsong Mo, Zhifeng Bao, Zhiyong Peng |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Mathematical optimization
Schedule Optimization problem Linear programming Heuristic (computer science) Computer science Approximation algorithm 02 engineering and technology Computer Science Applications Scheduling (computing) Bus network Computational Theory and Mathematics 020204 information systems 11. Sustainability 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Greedy algorithm Information Systems |
| Zdroj: | IEEE Transactions on Knowledge and Data Engineering. 34:4484-4498 |
| ISSN: | 2326-3865 1041-4347 |
| DOI: | 10.1109/tkde.2020.3036573 |
| Popis: | Reorganizing bus frequencies to cater for actual travel demands can signicantly save the cost of the public transport system. This paper studies the bus frequency optimization problem considering the user satisfaction. Specically, for the rst 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 efciently, we rst 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 efciency 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 efciency, effectiveness, and scalability of our methods in addressing FAST and FASTCO. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|