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

Sciortino, Monique 2026. An algorithmic framework for school bus routing with stop selection and on-time reliability. PhD Thesis, Cardiff University. Item availability restricted.

Preview	PDF - Accepted Post-Print Version Download (224MB) | Preview
	PDF (Cardiff University Electronic Publication Form) - Supplemental Material Restricted to Repository staff only Download (485kB)

Abstract

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.

Item Type:	Thesis (PhD)
Date Type:	Completion
Status:	Unpublished
Schools:	Schools > Mathematics
Uncontrolled Keywords:	1. School bus routing 2. Vehicle routing 3. Bus stop selection 4. Stochastic travel times 5. Travel time reliability 6. Correlated travel times
Date of First Compliant Deposit:	27 February 2026
Last Modified:	27 Feb 2026 11:17
URI:	https://orca.cardiff.ac.uk/id/eprint/185333

Actions (repository staff only)

Edit Item