The School Bus Routing Problem (SBRP) is a complex optimization challenge crucial to efficient and cost-effective transportation of students. This paper aims to improve school transportation efficiency, addressing issues such as under-utilization of buses and driver shortages, exacerbated by the COVID-19 pandemic. We propose a novel approach to identify a subset of students who voluntarily withdraw from bus services in exchange for an incentive, enabling significant fleet size reductions. This study presents a comprehensive mixed-integer linear programming model that integrates principles from the SBRP and capacitated team orienting problems. The model considers critical factors, including bus capacity, maximum walking distance, maximum riding time, and time to pick up students at stops. Additionally, a novel heuristic approach based on a pre-allocation-location-routing-allocation scheme is introduced to generate feasible solutions, further refined through a randomized tabu search process. The proposed algorithm demonstrates favorable results, yielding outcomes within a sub-10% gap from optimal solutions in synthetic instances. Empirical validation is conducted through a case study using data from the Williamsville central school district, corroborating the efficacy of our methods and highlighting the potential for fleet reduction and cost savings.
Caceres et al. (Fri,) studied this question.