AnEmpirical Performance Comparison of Meta-heuristic Algorithms for School Bus Routing Problem

Authors

Sherehe Semba, Department of Physics, Mathematics and Informatics, Dar es Salaam University College of EducationFollow
Egbert Mujuni, Department of Mathematics, University of Dar es Salaam, P. O. Box 35062, Dar es Salaam, TanzaniaFollow

Section

Mathematics and Computational Sciences

Abstract

School Bus Routing Problem is an NP-hard Combinatorial Optimization problem. Thus, mega-heuristic algorithms are widely used to solve instances of the School Bus Routing Problem with large data. In this work we present a model of the School Bus Routing Problem and empirical performances comparison between three meta-heuristic algorithms named Simulated Annealing (SA), Tabu Search (TS) and Ant-Colony Optimization (ACO) on the problem. We have analyzed their performances in terms of solution quality. The results show that all three algorithms have the ability to solve the School Bus Routing Problem. In addition, computational results show that TS performed best when execution time is not restricted while ACO had relative good performance when time is restricted but poor when the time is unrestricted.

Recommended Citation

Semba, Sherehe and Mujuni, Egbert (2019) "AnEmpirical Performance Comparison of Meta-heuristic Algorithms for School Bus Routing Problem," Tanzania Journal of Science: Vol. 45: Iss. 1, Article 8.
Available at:https://doi.org/10.65085/2507-7961.1724