OPTIMIZATION OF SCHOOL BUS AND STAFF TRANSPORTATION ROUTING USING GRAPH THEORY
Notice: This is a sample project for study and reference. Submitting it as your own work violates most universities' academic integrity policies.
Abstract
About This Research Topic
Daily pupil and staff transportation is a major cost and safety challenge for Nigerian schools. Determining which bus picks which pupils, in what order, to minimize distance while respecting seating capacity is a classic combinatorial optimization problem. With rising fuel costs, efficient routing directly impacts budgets, punctuality, and safety. Explore mathematics project topics on optimization This article rewrites the original undergraduate project on school bus routing, preserving its exact Held-Karp benchmark and 16-stop Nigerian case study while adding explanatory depth for Scholarnesthub readers.
Main Abstract
Efficient school bus and staff transport routing to collect all pupils at minimum travel distance under vehicle capacity is a daily operational problem for Nigerian schools. This study develops a graph-theoretic treatment grounded in shortest-path theory, the travelling salesman problem (TSP), and the capacitated vehicle routing problem (CVRP), applied to an original Nigerian school district case study. Dijkstra shortest-path and Kruskal minimum-spanning-tree algorithms were implemented on a seven-node illustrative network to establish foundations. A nine-node (one depot, eight stops) single-vehicle problem was solved exactly via Held-Karp dynamic programming and compared to Nearest-Neighbor heuristic and 2-opt local search; Nearest-Neighbor alone was 8.2% above optimum, while 2-opt refinement reached the exact optimum, visually confirmed by elimination of crossing edge. The framework was extended to CVRP and applied to a 16-stop district with heterogeneous pupil counts and 45-seat capacity, solved via Clarke-Wright Savings algorithm followed by 2-opt refinement, yielding four-bus solution covering 128.4 km total daily distance. This achieved 56.4% reduction versus naive one-bus-per-stop baseline and 11.4% reduction versus Nearest-Neighbor capacity-splitting baseline. Capacity sensitivity analysis showed monotonically diminishing returns between seating capacity and both total distance and buses required, with marginal benefit declining sharply beyond ~50 seats for this demand pattern. The study concludes graph-theoretic optimization combining exact verification for small instances with efficient heuristics for realistic scale provides Nigerian administrators a rigorous actionable tool, recommending Clarke-Wright with 2-opt as practical standard.
Chapter One Preview
Background to the Study
Graph theory models schools and stops as vertices, roads as weighted edges. The TSP, studied by Menger (1932) and Flood (1956), seeks minimum closed walk visiting all vertices once. The VRP, introduced by Dantzig and Ramser (1959) for petrol delivery, generalizes to multiple capacity-constrained vehicles. Both are NP-hard: no polynomial-time exact algorithm is known; Held-Karp DP requires exponential time, impractical beyond ~25 stops. This motivates heuristics: Nearest-Neighbor builds route by repeatedly going to closest unvisited point; Clarke-Wright Savings merges routes offering greatest distance saving subject to capacity; 2-opt iteratively removes two edges and reconnects to eliminate crossings.
In Nigerian context, school transport often uses intuitive routing leading to overlaps and underutilized capacity. Systematic optimization can cut distance and fleet needs while maintaining coverage. National Academies research on school transportation routing and US Department of Transportation school bus routing guidelines show similar benefits globally. See our operations research project materials
Statement of the Problem
Many Nigerian undergraduate treatments present only Nearest-Neighbor without benchmarking against exact optimum, without 2-opt improvement, and without extension to capacity-constrained multi-vehicle case that reflects real bus operations. Quantitative case studies with representative Nigerian stop locations, heterogeneous pupil counts, bus capacity, naive baseline comparison, and sensitivity analysis are less common, often omitting capacity or remaining abstract. This study addresses both by establishing Held-Karp benchmark, rigorously comparing heuristics against it, extending to CVRP, and applying to realistic 16-stop Nigerian district with full baseline comparison and capacity sensitivity analysis.
Aim and Objectives
Aim: Develop, implement, benchmark graph-theoretic routing methods and apply validated methods to Nigerian school district case study.
Objectives:
1. Implement Dijkstra shortest-path and Kruskal MST on 7-node illustrative network.
2. Solve 9-node single-vehicle TSP exactly via Held-Karp DP for optimality benchmark.
3. Implement Nearest-Neighbor and 2-opt and compare against exact benchmark.
4. Extend to CVRP via Clarke-Wright Savings with 2-opt refinement.
5. Apply to 16-stop Nigerian district with heterogeneous counts and 45-seat capacity.
6. Compare against naive baselines (one-bus-per-stop, Nearest-Neighbor capacity-splitting).
7. Conduct sensitivity analysis of total distance and buses required versus seating capacity.
Research Questions
1. What are shortest distances and minimum spanning tree for illustrative network?
2. How does Nearest-Neighbor with/without 2-opt compare to exact Held-Karp optimum on small TSP?
3. What is minimum-fleet minimum-distance plan for 16-stop case study under 45-seat capacity?
4. How much distance/fleet does optimized plan save vs naive baselines?
5. How sensitive are distance and fleet size to bus capacity variation?
Significance of the Study
For graph theory students, provides rigorously benchmarked treatment including exact optimum verification. For Nigerian school administrators, demonstrates directly implementable method to minimize fuel, wear, fleet size while maintaining full coverage, relevant amid rising fuel costs. For education boards, sensitivity analysis illustrates trade-off between fewer larger buses vs more smaller buses for procurement planning. Related logistics and transportation project topics
Scope of the Study
Restricted to static, single-depot, single-commodity (pupil count) routing where locations, counts, distances fixed at planning time. Time-window constraints, multiple depots, heterogeneous fleet, dynamic/stochastic routing outside scope. Applied case study uses representative illustrative stop locations and counts for stylized Nigerian district, not primary data from named school.
Limitations
Illustrative random coordinates not surveyed data. Edge weights approximated as Euclidean distances scaled by detour factor, not true road-network distances with traffic/quality. No time-window constraints. Homogeneous fleet assumption. Clarke-Wright + 2-opt heuristic for CVRP, not exact; global optimality not claimed for 16-stop solution, though internally consistent and benchmarked on small instance.
Operational Definition of Terms
Graph: Structure of vertices (locations) and edges (roads) representing network.
Shortest path: Minimum-weight edge sequence connecting two vertices.
Minimum spanning tree: Cycle-free edge subset connecting all vertices at minimum total weight.
Travelling salesman problem (TSP): Minimum-length closed route visiting each vertex exactly once and returning to start.
Vehicle routing problem (VRP): Generalization of TSP to multiple vehicles serving all demand points.
Capacitated VRP (CVRP): VRP where each vehicle has max demand (pupil count) per route.
Nearest-Neighbor heuristic: Construction method repeatedly traveling to closest unvisited point.
Clarke-Wright Savings: CVRP construction merging routes offering greatest saving subject to capacity.
2-opt: Local search removing two edges and reconnecting to reduce length, eliminating crossings.
NP-hard: Complexity class indicating no known polynomial-time exact algorithm for all instances.
Dijkstra shortest path algorithm explanation | Vehicle Routing Problem survey - Transportation Research Board | Clarke-Wright Savings algorithm original paper
Conclusion
Seven-node Dijkstra and Kruskal foundations led to nine-node exact TSP via Held-Karp. Nearest-Neighbor alone was 8.2% above optimum; 2-opt refinement achieved exact optimum, removing crossing edge. Extended to 16-stop 45-seat Nigerian district, Clarke-Wright + 2-opt yielded 4-bus solution covering 128.4 km, achieving 56.4% saving vs one-bus-per-stop baseline and 11.4% vs Nearest-Neighbor capacity-splitting. Sensitivity showed diminishing returns beyond ~50 seats. The study recommends Clarke-Wright Savings with 2-opt refinement as practical efficient standard for school routing, combining exact verification on small instances with scalable heuristics for realistic problems. For implementation code templates, see our graph theory project collection
FAQs
1. What is the difference between TSP and CVRP?
TSP finds single shortest tour visiting all stops once. CVRP extends to multiple vehicles each with capacity limit, splitting stops across routes—essential for school buses.
2. What was the exact benchmark result?
On 9-node problem, Held-Karp DP gave true optimum. Nearest-Neighbor alone was 8.2% longer; after 2-opt it reached optimum exactly.
3. How was the 16-stop Nigerian case study solved?
Using Clarke-Wright Savings algorithm to construct routes based on distance savings, then 2-opt to refine each route, with 45-seat capacity constraint.
4. How much distance did optimization save?
128.4 km total for 4 buses, saving 56.4% vs one-bus-per-stop baseline and 11.4% vs Nearest-Neighbor capacity-splitting baseline.
5. What is 2-opt and why does it matter?
Local search that removes two edges and reconnects opposite way if shorter, eliminating crossings common in Nearest-Neighbor tours, improving distance and safety.
6. What did capacity sensitivity show?
Increasing seats reduces total distance and buses needed, but marginal benefit declines sharply beyond ~50 seats for this demand pattern—important for procurement.
7. Why are school bus problems NP-hard?
Exact solution time grows exponentially with stops. No polynomial-time exact algorithm known, so heuristics like Clarke-Wright + 2-opt are used for realistic sizes.
8. Can this be applied to staff transportation?
Yes. Same model applies—replace pupil counts with staff counts per stop, same depot, capacity, and distance minimization objective.
9. What are limitations of Euclidean distance approximation?
It ignores road detours, traffic, road quality. Real deployment should use OpenStreetMap road-network distances or travel times.
10. What tools were used for implementation?
Dijkstra, Kruskal, Held-Karp DP for exact TSP, Nearest-Neighbor, Clarke-Wright Savings, and 2-opt—all implementable in Python with full reproducibility.
Purchase to unlock the full material.