Date on Master's Thesis/Doctoral Dissertation
8-2018
Document Type
Doctoral Dissertation
Degree Name
Ph. D.
Department
Industrial Engineering
Degree Program
Industrial Engineering, PhD
Committee Chair
Bae, Ki-Hwan
Committee Co-Chair (if applicable)
Alexander, Suraj
Committee Member
Alexander, Suraj
Committee Member
Biles, William
Committee Member
Riedel, Thomas
Author's Keywords
school bus routing; student assignment; genetic algorithm; column generation; special-education student
Abstract
In this dissertation, we solve a school bus routing problem of transporting students including special education (handicapped) students and assigning them in Oldham county education district. The main contribution of this research is that we consider special education students (Type-2) along with other students (Type-1) and design a comprehensive school bus schedule to transport both kinds of students at the same time. Also, a student assignment mathematical model is presented to optimize the number of bus stops in use as well as one important measure of service quality, the total student walking distance. Comparing to the classic clustering methods, heuristic methods, or other methods from previous literatures, a mathematical optimization model is developed to solve a student assignment problem and to obtain the global optimal solution. The modeling constraints include budget limit, travel time limit, equity, school time window, and etc. Especially, the main difference between our model and other models is that it takes Type-2 students into consideration along with critical constraints accordingly, and solves the resulting more complex problem. Moreover, the school bus routing model in this work is one of the most general optimization models representing the school bus routing problem. On the other hand, similar to all existing models, the developed model considers the total system cost as the objective function value to minimize, different bus capacities, and common vehicle routing constraints such as flow conservation on routes and subtour elimination. Furthermore, another main difference is that the bus scheduling and school time window is also considered and solved in the model. With two different types of students, both Type-1 and Type-2, the time restrictions are varying, resulting in more complexity and additional constraints. The results in this work present the difficulties of meeting the requirement of Type-2 student riding time limit and school time window simultaneously. Also, the constraints regarding service equity and quality are provided and they can be used by decision makers if necessary. Either densely populated urban areas or sparsely populated rural areas, the school bus routing problem is difficult to solve due to a large number of students or long travel distance. The school bus routing problem falls under vehicle routing problem (VRP) with additional requirements because each student represents one unit of capacity. In this dissertation, we present a modeling framework that solves a student assignment problem with bus stop selection, and subsequently a school bus routing problem with school time window constraints. We demonstrate the efficacy of heuristic methods as well as a column generation technique implemented to solve the problems using real data.
Recommended Citation
Zhang, Di, "Solving school bus routing and student assignment problems with heuristic and column generation approach." (2018). Electronic Theses and Dissertations. Paper 3051.
https://doi.org/10.18297/etd/3051