01659525

Component

https://doi.org/10.1177/0361198118787803

In the school bus scheduling problem, the main contributing factor to the cost is the number of buses needed for the operations. However, when subcontracting the pupils’ transportation, unbalanced tours can increase the costs significantly as the lengths of some tours can exceed the daily fixed driving goal and will result in over-hour charges. This paper proposes a mixed integer programming (MIP) model and a matching-based heuristic algorithm to solve the “balanced” school bus scheduling problem with fixed start times in a multi-school setting. The heuristic solution always has the minimum number of buses as it starts with a minimal number of tours and does not alter the number of tours during its balancing stage. The effectiveness of the heuristic is tested by comparing its solutions with results from solving the MIP using commercial solvers whenever solvers could find a good solution. To illustrate the performance of the MIP and the heuristic, 11 problems were examined with different numbers of trips which are all based on two real-world problems: a California case study with 54 trips and the Howard County Public School System with 994 trips. Our numerical results indicate the proposed heuristic algorithm can find reasonable solutions in a significantly shorter time. The balanced solutions of our algorithm can save up to 16% of school bus operation costs compared with the best solution found by solvers from optimizing the MIP model after 40 hours. The balancing stage of the heuristic decreases the standard deviation of the tour durations by up to 47%.

The Standing Committee on Transportation Network Modeling (ADB30) peer-reviewed this paper (18-01108). © National Academy of Sciences: Transportation Research Board 2018.

18-01108

English

pp 1-11

2018-12

Transportation Research Record: Journal of the Transportation Research Board

Digital/other

Figures; References (21) ; Tables

Algorithms; Case studies; Heuristic methods; Mixed integer programming; Scheduling; School buses; School trips

Blocking (Schedules); Matching

California; Howard County (Maryland)

Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation

TRIS, TRB, ATRI

Jan 8 2018 10:17AM

• A Generalized Single-Level Formulation for Origin–Destination Estimation under Stochastic User Equilibrium
• A Greedy Path-Based Algorithm for Traffic Assignment
• Algorithm to Compute Urban Road Network Resilience
• Characterization of Taxi Fleet Operational Networks and Vehicle Efficiency: Chicago Case Study
• Impact of Extreme Events on Transportation Infrastructure in Iowa: A Bayesian Network Approach
• Improving Scalability of Generic Online Calibration for Real-Time Dynamic Traffic Assignment Systems
• Level-Change Stackelberg Games Model for the Combined Traffic Assignment–Signal Control Equilibrium on Networks
• Link Transmission Model-Based Linear Programming Formulation for Network Design
• Modeling Day-to-Day Dynamics of Travelers’ Risky Route Choices under the Influence of Predictive Traffic Information
• Multimodal Transportation Network Modeling Based on the Generic Second Order Modeling Approach
• Network Partitioning Algorithms for Solving the Traffic Assignment Problem using a Decomposition Approach
• Optimal Information Provision at Bottleneck Equilibrium with Risk-Averse Travelers