Which Graph Theory Algorithm is More Effective in Optimizing a School-Bus Route in Terms of Computational Complexity and Efficiency?

This paper delves into the optimization of school-bus routes, a critical challenge with implications for student schedules, fuel consumption, environmental sustainability, and transportation costs. Four graph theory algorithms—Genetic Algorithm, Simulated Annealing, Clarke-Wright Savings Algorithm, and Nearest Neighbor—are examined for their effectiveness in tackling the School-Bus Routing Problem with a Single Load Plan (SBRP-SLP), a variant of the Vehicle Routing Problem. Through rigorous experimentation, the algorithms’ computational efficiency and solution quality are assessed. A specialized ‘School’ class generates and manages bus stops, while each algorithm follows a unique approach to route optimization. By systematically altering the number of bus stops and exploring various bus capacities, the study uncovers how the algorithms perform and their behavior patterns. The findings indicate that the Genetic Algorithm and Simulated Annealing strike a balance between solution quality and computational time. Nearest Neighbor offers simplicity and moderate efficiency, and the Clarke-Wright Savings Algorithm excels in computational efficiency. Considering the trade-off between solution quality and computational time, Simulated Annealing emerges as a recommended choice for school-bus route planning under capacity constraints. This paper provides insights into diverse strategies for addressing the SBRP-SLP, offering practical guidance for efficient school-bus route optimization.