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.

Bus scheduling is a crucial component for public transport service. Inefficient shift arrangement leads to poor vehicle loading rate or crowd inboard. In this paper, we consider a crowdsourced bus service system (on a fixed route) that receives user requests as input and computes a 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. Then we propose the Optimized Departure Time (ODT) algorithm that computes an optimal scheduling, which is built on an innovative reduction of the problem to a variant of the k-clustering problem, and an efficient application of dynamic programming. On top of ODT, we propose the Optimized Departure Time with Skip-Stop (ODTS) algorithm, which further improves the effectiveness of the solution by utilizing skip-stop. Our experimental results demonstrate that ODT and ODTS dramatically improve the baseline solution and outperform existing algorithms for the bus scheduling problem, which are very close to the optimum.