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

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.

Keywords:  School Bus Routing Problem; Combinatorial Optimization; Meta-heuristic Algorithms