A Metaheuristic Solution for the School Bus Routing Problem with Homogeneous Fleet and Bus Stop Selection

Context: Optimization problems allow representing real-life situations, and, with the right method, a good solution to a problem can be reached. Conceptually, the problem under study is known as the School Bus Routing Problem. This work can be taken as a starting point for the creation of tools for this problem. Method: In this work, a mathematical model based on the literature was designed and implemented, and it was adapted to be solved using metaheuristics. Three mutation operators and a selection mechanism based on weights were implemented according to the improvements that each of them offered to the solution. To evaluate the results, a statistical comparison was made with another solution in the literature based on the evaluation of 112 instances of the problem. Results: In the solution of the 112 instances of the problem, the following algorithms were used: the Tabu Search, Hill Climbing variants, Simulated Annealing, and an algorithm portfolio that includes the previous ones. The results showed that the best behavior was obtained by the portfolio, with results comparable to those in the literature. However, as the number of instances grows, the results tend to get worse. Conclusions: With this research, it was possible to obtain a model that represents the initial problem, as well as two algorithms for finding solutions by means of metaheuristics. According to the results obtained, future work should be directed towards new ways of building the initial solution and the implementation of new assignment operators.