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.Contexto: Los problemas de optimización permiten representar situaciones de la vida real, y con un método apropiado se puede llegar a una buena solución del problema. Conceptualmente, el problema bajo estudio se conoce como problema de planificación de ruta de autobuses escolares. El presente trabajo puede ser tomado como punto de partida para la creación de herramientas para este problema. Método: En este trabajo se diseñó e implementó un modelo matemático del problema basado en la literatura y se adaptó para su solución usando algoritmos metaheurísticos. Se implementaron tres operadores de mutación y un mecanismo de selección basado en pesos, según las mejoras que brindaba cada uno a la solución. Para evaluar los resultados, se realizó una comparación estadística con otra solución de la literatura a partir de la evaluación de 112 instancias del problema. Resultados: En la solución de las 112 instancias del problema se utilizaron los siguientes algoritmos: búsqueda tabú, variantes del escalador de colinas, recocido simulado y un portafolio de algoritmos que incluye a los anteriores. Los resultados reflejaron que el mejor comportamiento lo obtuvo el portafolio con resultados comparables a los de la literatura. Sin embargo, a medida que crece el número de instancias, los resultados tienden a empeorar. Conclusiones: Con esta investigación se obtuvo un modelo que permite representar el problema inicial, así como dos algoritmos para la búsqueda de soluciones utilizando metaheurísticas. Según los resultados obtenidos, los trabajos futuros deben encaminarse hacia nuevas formas de construcción de la solución inicial y la implementación de nuevos operadores de asignación y mutación