School Bus Routing Problem in Large-Scale Networks: 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; the school bus routing problem (SBRP) is an important and practical branch of this problem. Because the number of variables and equations is vast, finding the exact solution for this problem under real conditions is difficult; only heuristic and meta-heuristic algorithms can be used to solve it. Recently, the ejection chain method (ECM) has been introduced as a heuristic algorithm that efficiently finds a new neighbor solution. In a case study in developing countries, efficiency of several heuristic algorithms including ECM along with one metaheuristic algorithm–-tabu search algorithm (TSA)–-is verified for solving large-scale problems. Additionally, capacity limitation, which is usually ignored in VRP and SBRP algorithms such as 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 of feasible solutions (solutions satisfying capacity limitations as well) from the infeasible 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 middle school were used to show the effectiveness of the MA.