School Bus Routing Problem in Large-Scale Networks: A New Approach Utilizing Tabu Search on a Case Study in Developing Countries.

The Vehicle Routing Problem (VRP) is one of the most complicated optimization mathematical models and in particular the School Bus Routing Problem (SBRP) is an important and practical branch of this problem. Since the number of variables and equations are vast, finding the exact solution for this problem under real conditions is difficult and only heuristic and meta-heuristic algorithms can be used to solve it. In previous studies, many heuristic and meta-heuristic algorithms were tested in order to solve VRP. However, many of them are capable of solving the problem under specific assumptions. In other words, one might find few algorithms which are capable of solving real world cases in which large-scale networks are used and limitation of bus capacity is considered. Recently, “Ejection Chain Method” (ECM) has been introduced as a heuristic algorithm which efficiently finds a new neighbor solution. In a case study in developing countries, efficiency of several heuristic algorithms including ECM along with one Meta-heuristic algorithm, Tabu Search Algorithm (TSA), is verified for solving large-scale problems. Additionally, capacity limitation, which is usually ignored in VRP and SPRP algorithms like ECM, is considered as a restricting condition in this study’s models. This study will show that neither the ECM used individually nor its combination with TSA produces feasible solutions for real-life scenarios. The authors have developed two innovative heuristic algorithms, the Construction Feasible Solutions and the Changing Algorithm that when used in combination with TSA and ECM generate a practical and efficient procedure called, the Mixed Algorithm (MA). Addressing vehicles’ capacity is mainly performed by the Construction Feasible Solutions, which works to generate feasible solutions (solutions satisfying capacity limitations as well) from the unfeasible solutions that might result from the TSA and ECM. The Changing Algorithm is responsible for generating a local optimum for every resulting feasible solution. Data from bus routing of a girls' middle school was used to show the effectiveness of the Mixed Algorithm.