The Walking School Bus Routing Problem

  • Negin Bolkhanian
  • Matthew Reyers


This paper proposes four heuristic methods for the Walking School Bus Routing
Problem (WSBRP). Our work first develops a simulation model based on school
catchment regions and census data, creating a proportionally representative sample
of students. Each sample is then clustered by four methods and a routing
problem is solved on each of these clusters. Evaluation of clustering techniques is
done through a scoring function applied to the generated routes and is compared
with a modi1ed version of an open source Vehicle Routing Problem (VRP) solver.
Results indicate that clustering method based heuristics offer comparable and often
improved results in comparison to VRP outputs in a significantly reduced time
frame, ideal for the design of applets and real-time services.