Search

Maintaining a fleet of buses to transport students to school is a major expense for school districts. An efficient bus routing system can greatly reduce the time and cost associated with transportation, while also ensuring the safety and comfort of students. Optimizing large-scale school bus routing problems (SBRP) is challenging due to the huge number of variables and constraints involved. It is thus treated by decomposing into several subproblems, involving bus stop selection, bus route generation, school bell time adjustment, and bus scheduling. All subproblems of the SBRP are known to be NP-hard. Among all the sub-problems of SBRP, the school bell time adjustment sub-problem has drawn little research attention. Nonetheless, change in the school bell time (start and end time) can be a cost-efficient and practical approach to improve the school bus transportation system. Given a set of bus routes assigned to schools, in this dissertation we develop a multicriteria optimization model that determines the bell times in each school, the assignment of routes to buses, and the schedule of the buses under a single load assumption for both heterogeneous and homogeneous fleet scenarios. The three criteria we consider are (1) minimizing the number of buses, (2) minimizing the total miles of travel distances, and (3) maximizing the preference of all constituents for schools' bell times. We first introduce an end-to-end neural combinatorial method to efficiently deal with the school bus scheduling problem. Borrowing the idea from the Transformer architecture, an attention model trained using reinforcement learning is applied to the bus scheduling problem by taking the embedded graph information as input, to predict the optimal routing permutation. As a result, a pre-trained model would be available for solving multiple instances simultaneously in parallel. In addition, we design the scheme for generating benchmark datasets for the bus scheduling problem. Then, a 2-stage Tabu Search framework is designed to solve the original large-scale mixed integer linear programming model by integrating the neural combinatorial model in the evaluation stage, making it practicable to provide near-optimal solutions by exploring different combinations of bell time assignments within the search space. Numerical experiments show that our solution approach outperformed existing heuristics and a state-of-the-art commercial solver with respect to solution quality for a given execution time. The tests on the Boston Public Schools transportation system, that serves 133 schools and 22,420 students, demonstrate that adjusting the school bell time in school districts can result in the reduction of total travel distances from 15% to 55% (average 20% - 30%), depending on the original bell time allocation, and the proposed bell time policy. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]