The increasing demand on school bus service has enabled more and more primary or secondary schools to provide student transportation using their private buses.Providing school bus service, especially in large scale, is a very complex and expensive system. One of the challenges resides in designing routs for the school buses, well known as school bus routing problem (SBRP).
SBRP aims to plan an efficient route schedule for a fleet of school buses that transport students to or from their schools while satisfying various constraints. There are many variants of SBRP that concern different objectives and constraints. Existing studies have demonstrated the benefits that mixed load SBRP, where each bus transport students for one or more schools at the same time, can save the number of buses required. This paper explores whether the successful algorithm developed for pickup and delivery problem with time windows (PDPTW) can be employed for solving mixed load SBRP. We present a PDPTW-based metaheuristic algorithm to address the mixed load SBRP focusing on minimizing the number of buses. Our algorithm combines record-to-record travel framework with three neighbourhood operators, single paired insertion, swapping pairs between routes, and within route insertion, to improve solution iteratively. Results for benchmark data sets 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 cpu time spent on neighbourhood search without affecting the quality of solutions apparently.