Solving the integrated school bell time, and bus routing and scheduling optimization problem under the deterministic and stochastic conditions

Abstract

The school bus planning problem (SBPP) has drawn significant attention in research and practice because of its importance in pupil transportation. The major task of the SBPP is to simultaneously optimize the school bell times, the routing plan (a set of trips) and the scheduling plan (the assignment of buses to serve these trips) while maintaining the minimum level-of-service requirements with the objective that the total number of buses and the total vehicle time are both minimized. Many subproblems of the SBPP have been well studied, but the integrated problem lacks much research due to its complexity.

A Mixed Integer Programming (MIP) model is proposed for the integrated SBPP. A novel decomposition method is developed to solve the model. It distinguishes itself from the literature with the consideration of trip compatibility in the routing stage, which is a piece of essential information in the following scheduling stage. This ‘look ahead’ strategy finds a new balance between the model integration and decomposition, which solves the problem efficiently as a decomposed problem but with the high solution quality as the integrated model. Three heuristic algorithms are proposed to solve the deterministic SBPP with the trip compatibility. Then, two mathematical programming models and a Column Generation-based algorithm are proposed for the SBPP under traffic congestion and stochastic travel time in a real uncertain world. These innovative algorithms incorporate the merits of the Simulated Annealing, Tabu Search, Insertion Algorithm, and Greedy Randomized Adaptive Search Procedure and gain the computational power that the existing methods do not have.

The experiments are conducted on randomly generated datasets, benchmark problems, and real-world cases. The results show that the proposed models and algorithms outperform the state-of-the-art method in all test problems by up to 25%. In a real-world case study, after the bell time adjustment, up to 41% of current buses can be saved with even better service with respect to the higher punctuality and shorter student ride time.