An algorithmic framework for school bus routing with stop selection and on-time reliability

The school bus routing problem (SBRP) is an NP-hard combinatorial optimisation problem with significant practical relevance. This research is driven by persistent operational challenges reported by guardians and school transport operators, including excessively early pick-up times, long and inconsistent travel durations, and occasional vehicle capacity shortages. These inefficiencies impact student well-being and service equity, revealing limitations in current planning methods. There is a pressing need for routing solutions that are not only cost-efficient but also scalable and reliable under daily operational uncertainty. This dissertation addresses the SBRP in a realistic context, involving problem instances with sizes upwards of 1800 potential bus stops and 750 students. A mixed integer programming model is first developed to solve small-scale instances optimally and establish performance benchmarks. To handle the computational challenges of larger instances, a heuristic algorithmic framework is proposed, incorporating a bus stop selection component, multiple constructive and improvement heuristics, and a destroy-and-repair mechanism for effective solution space exploration. The most advanced version of the framework extends to stochastic settings by modelling arc travel time uncertainty using shifted lognormal distributions, which reflect the skewed nature of real-world travel times. A correlation structure, based on a classification of arc pairs, is also introduced to capture spatial dependencies. Additionally, a percentile-based reliability metric is employed to account for the goal of on-time student arrival. Computational experiments using real-world data, supported by Monte Carlo simulations, demonstrate that accounting for both travel time variability and spatial correlation is critical for generating reliable solutions that better meet service expectations. In contrast, approaches assuming deterministic or independent travel times may underestimate delays or even be practically unimplementable. By aligning algorithmic development with operational realities, this research contributes decision-support tools for enhancing reliability in school bus routing as well as in broader vehicle routing settings.