Analyzing the performance of a two-stage framework for the school bus routing and scheduling problem

The problem of routing and scheduling school buses is of great importance due to its monetary and social impact on many communities. Its solution is usually tailored to specific solution strategies or instances, but will be avoided in this work to achieve broader benefit and extensibility. A detailed description of the problem and constraints is provided, in addition to illustrating the linkage between school bus routing and other classes of routing problems. The current literature is briefly reviewed. Moreover, six solution strategies were selected to serve as a standard set for solving common cases of the problem. Those strategies can be classified into two types. The first type solved the problem over two stages by minimizing travel distances in a routing stage followed by a scheduling stage in which the cost of buses and fuel were minimized. On the other hand, the second type of strategies combined the routing and scheduling stages and optimized the total cost in one stage. The mathematical formulations of all strategies were derived from an existing pickup and delivery formulation, and the performance of those strategies with respect to solution quality and speed was examined by solving many randomly generated instances from local school board data. Each generated instance was solved twice based on two scenarios: first with short delivery periods prior to schools' bell times and a large assignment of students to stops, resulting in high bus demands; the other assumed wide delivery periods with fewer students assigned to stops, resulting in low bus demands. Due to the increased concern about fuel cost and the adverse influence of exhaust gases on the environment, the significance of optimizing the effect of students' weight on fuel consumption was investigated. The poor quality of the continuous relaxation lower bounds on the required number of buses and travel distances from the optimization solver, led to the development of the first known formulation-independent lower bounds for single-school problems and they were extended to accommodate multi-school problems. Finally, many conclusions were drawn suggesting proper practices for selecting suitable solution strategies based on the data of the real-life instance being solved.