A Metaheuristic Algorithm for Routing School Buses With Mixed Load
Yane Hou, Lanxue Dang, Weichuan Dong, Yunfeng Kong
Abstract
Designing a system to solve school bus routing problems (SBRP), especially in a large school district, is very complex and expensive. One of the challenges resides in designing routes for the school buses when they have mixed loads, where each bus transports students for one or more schools at the same time to save the total number of buses required. This article aims to explore whether the algorithm originally developed for pickup and delivery problem with time windows (PDPTW) can be employed for solving mixed load SBRP. We present a PDPTW-based algorithm to address the mixed load SBRP focusing on minimizing the number of buses required. Our algorithm combines a record-to-record travel framework with three neighborhood operators, single paired insertion, swapping pairs between routes, and within route insertion, to improve solution iteratively. Results from implementing this algorithm show that our PDPTW-based algorithm is feasible for mixed load SBRP. Moreover, we found that guided strategy is better than random for permuting nodes that would be selected to relocate positions in a route or among routes. In addition, the results also show that the spatiotemporal connectivity index used in our algorithm can reduce the computation time needed for searching for solutions without affecting the quality of the solutions.