MULTI-DEPOT AND MULTI-SCHOOL BUS SCHEDULING PROBLEM WITH SCHOOL BELL TIME OPTIMIZATION
Publication or External Link
The school bus transportation system is responsible for transporting students to and from schools safely and promptly. This research aims to optimize the school bus schedules and the school bell times simultaneously for improving the efficiency of the school bus system operation. We consider the school bus scheduling problem in a multi-depot multi-school bus system and incorporate the bell time optimization to make bus operations more efficient. We propose four different methods, including one exact method and three heuristic methods, to solve the Multi-depot and Multi-school Bus Scheduling Problem with School Bell Time Optimization (MDSBSPTW). Besides, they can also solve the Single-depot Multi-school Bus Scheduling Problem with School Bell Time Optimization problems (SDSBSPTW) or problems without bell time optimization regardless of the number of depots (i.e., MDSBSP or SDSBSP).
First, the MDSBSPTW is formulated as a mixed-integer programming model. Second, a two-phase heuristic method is proposed, namely the first-route second-assignment method. Then, we improve the first-route phase of the two-phase heuristic method with a Simulated Annealing-based Greedy Algorithm (SA-GDA) method. Combined with the same second-assignment phase, we have the improved two-phase heuristic method. Finally, we propose a Tabu Search-Based Ant Colony Optimization (TS-ACO) for solving the MDSBSPTW without dividing it into different phases.
Fourteen test problems with different characteristics derived from the real-world collected data are used to examine the performance of the proposed four methods. The results are compared and explained. The improved two-phase heuristic method and the TS-ACO method perform better than the other two methods when the problems are more complicated (e.g., more trips, depots, schools, or larger bell time window). Overall, the improved two-phase heuristic method is the best as it can achieve better solutions (i.e., fewer buses) much quicker, especially for large-size complicated problems. Generally, incorporating the school bell time optimization into the school bus scheduling problem can significantly reduce the total number of buses since it makes more trips compatible and thus link more trips together on a single bus route. Besides, the larger the school bell time window, the fewer buses are needed overall, but more computational resources and longer model running time are required.