Near-Optimal Scheduling for Crowdsourced Transit System With Skip-Stop Tactic

Efficient bus scheduling is a crucial component for the improvement of public transit services. Without systematic optimization and efficient shift arrangement, the bus scheduling system may suffer from poor vehicle loading rate or crowd onboard, resulting in wasted energy and passenger dissatisfact...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2023-11, Vol.35 (11), p.1-12
Main Authors: Li, Hanlin, Wu, Xiaowei, Hou U, Leong, Kou, Kun Pang
Format: Article
Language:English
Subjects:
Algorithms
Clustering
Costs
Crowdsourcing
Dynamic programming
Effectiveness
Heuristic algorithms
Loading rate
Mobile applications
Near-optimal scheduling
Optimal scheduling
Optimization
Public transportation
QR codes
Schedules
Scheduling
Scheduling algorithms
skip-stop
Travel time
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Efficient bus scheduling is a crucial component for the improvement of public transit services. Without systematic optimization and efficient shift arrangement, the bus scheduling system may suffer from poor vehicle loading rate or crowd onboard, resulting in wasted energy and passenger dissatisfaction. In this paper, we consider a crowdsourced bus service system (on a fixed route) that receives user requests as input and computes the scheduling of buses with flexible departure time and skip-stop to minimize the travel time of users. We first show that the general problem of computing the optimal scheduling is NP-hard. On the other hand, for the case when skip-stop is not adopted, we propose the Optimized Departure Time (ODT) algorithm that computes optimal scheduling. Our algorithm is built on an innovative reduction of the problem to some variants of the k-clustering problem and an efficient application of dynamic programming. On top of ODT, we further improve the effectiveness of the solution by utilizing the power of skip-stop tactic, named ODTS. Our experimental results demonstrate that ODT and ODTS dramatically outperform existing algorithms for the bus scheduling problem in terms of effectiveness and efficiency. Moreover, the solutions given by ODTS are very close to the optimum.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2022.3223553