School transportation systems play an important role in ensuring equal access to education. They ensure that students can attend school regularly, regardless of their family’s financial situation or access to transportation. They also help to ensure safety, reduce traffic congestion, and save time for working parents.
In many countries, local governments are legally responsible for arranging school transport for eligible students. In England, for example, free school transport must be provided to children aged 5 to 16 who attend their nearest suitable school but live beyond a certain distance. Arrangements must also be made for students with special educational needs, disabilities, and, in some cases, those from low-income families.
In 2023, English local authorities collectively spent over £1 billion on home-to-school transport [1]. Sparsely populated areas often need to spend more per student on school transport; in contrast, urban areas see different logistical challenges, such as traffic congestion and the identification of safe walking routes between homes and pick-up points.
An Optimisation Problem
School transportation systems are usually designed by local government for each individual school. The process involves identifying a suitable set of pick-up points (such as bus stops), assigning qualifying students to these pick-up points, and then creating efficient bus routes that visit these stops. Several factors should be considered while doing this.
- Economic costs should be minimised by limiting the number of vehicles and drivers used
- Journeys should not be too long and boarding times should be considered
- Pick-up points should be close to people’s houses
- Buses have limited seating capacities.
These factors make this problem an interesting mix of vehicle routing, set covering, and bin packing, all of which are known to be NP-hard optimisation problems.
Industry Focussed Algorithm Design
Since 2018, researchers at the Cardiff School of Mathematics, led by Professor Rhyd Lewis, have been developing new heuristic-based algorithms for designing school transportation systems. In this work, collaboration with industrial stakeholders has been crucial, as has the integration of state-of-the-art mapping technologies, which have allowed tests to be conducted on real-world scenarios. Figure 1 shows an example solution produced by our methods.
Current Work
On the 24th of April 2024, the issue of school transport was debated at a plenary session of the Welsh Parliament. During this, Sarah Murphy MS said to the Minister of Transport:
“Dr Rhydian Lewis, who is at Cardiff University School of Mathematics, has designed an algorithm that can be used to minimise bus use, student walking distance, and journey time. I think that this would be an excellent way of using new technology—our own Cardiff University academics bringing something in that could actually resolve an awful lot of this. Is this something that you would meet with me to discuss further? Diolch.” [2]
Preliminary results from data supplied by Welsh schools have indicated that our methods have real potential for maintaining or improving school transport systems, while not increasing financial costs to the taxpayer. This is achieved through the identification of more efficient routes, allowing a reduction in vehicles, shorter journey times, and shorter walking distances.
Conclusions
The use of our bespoke algorithms in this area brings two main advantages. First, the automated processes bring a reduction in administrative overheads while ensuring solutions are efficient and give value for money. Second, they allow stakeholders to explore various “what-if” scenarios when contemplating policy changes. For example, what are the consequences of altering eligibility criteria, limits to walking distances, and maximum journey times? More broadly, can services be improved through the efficiencies gained by these tools? In Wales, answering these questions in an analytical manner is an important step in meeting the requirements of the Well-being of Future Generations Act (2015), which “requires public bodies in Wales to think about the long-term impact of their decisions, to work better with people, communities and each other, and to prevent persistent problems such as poverty, health inequalities and climate change” [3]. For further details, see www.rhydlewis.eu/bus/ or [4].
References
[1] https://www.isospartnership.com/blog/hometoschooltransport
[2] https://record.assembly.wales/Plenary/13875#C583761
[3] https://www.futuregenerations.wales/about-us/future-generations-act/
[4] Lewis, R. and K. Smith-Miles (2018) A Heuristic Algorithm for Finding Cost-Effective Solutions to Real-World School Bus Routing Problems, Journal of Discrete Algorithms, vol. 52-53, pp. 2-17.