Shuttle Bus Rerouting and Rescheduling Problem considering Daily Demand Fluctuation

In an urban shuttle system, shuttle buses need to pick up passengers waiting at predetermined stops according to their planned schedules (routes and timetables). However, in practice, passenger demand is unstable and has fluctuations, which means that passenger demand at a specific stop is likely to increase or decrease, causing low service quality, long passenger waiting times, and imbalanced utilization of bus capacity. Therefore, we introduce the shuttle bus rerouting and rescheduling strategy, based on which the operator can change the visited stops and arrival times of the shuttle buses and can operate backup buses to handle the passenger demand fluctuations. A three-dimensional space-time-state network is formulated to depict shuttle routes, timetables, and passenger-loading states, and the proposed problem can be formulated as a multicommodity network-flow optimization problem. To solve the model efficiently, we adopt the alternating direction method of multipliers (ADMM) decomposition method to decompose the original problem into several single shuttle routing subproblems. We test the model and algorithm in the 9-node network with three stops, and a larger scale Chicago sketch network is also adopted to demonstrate the effectiveness and efficiency of the proposed model and algorithm. The rerouting and rescheduling results for the Chicago case represent a 5.7% improvement relative to the results with the planned schedules.