Leveraging Structure in Public School Transportation Problems

Zeng, Liwei

doi:https://doi.org/10.21985/n2-gfyg-2q49

Work

Leveraging Structure in Public School Transportation Problems

Public

Download PDF

Download All Files (.zip)

Across the United States, public school districts are facing critical budget crises. To keep cuts away from the classroom, bus transportation is a common area to look for cost reductions. This thesis studies two fundamental problems that arise in public school transportation: the bus route design problem and the school bus scheduling problem. The goal of this thesis is to develop new models and algorithms that provide fast, robust solutions with provable performance guarantee to both problems. In the bus route design problem, the goal is to find bus routes by selecting bus stops and generating bus routes simultaneously. Optimizing these decisions are NP-hard on a general road network and existing solution approaches based on integer linear program (ILP) can be challenging for implementation due to problem scale. Motivated by the grid-like road network structure of a local school district, we introduce the covering path problem on a grid (CPPG) to model the joint problem of bus stop selection and bus route generation. CPPG finds the cost-minimizing path connecting a subset of potential stops in a coverage region on a grid, such that each point in the region is within a predetermined distance from a stop. We provide algorithms that find routes for the CPPG following a simple up-and-down pattern. The pattern is shown to be near-optimal and robust to students location changes. We also generalize the results to broader settings to incorporate more realistic considerations. In the school bus scheduling problem (SBSP), we optimize school start times and school bus operation times jointly. The problem aims to assign different start times to schools and school buses so that buses can be reused more efficiently. As observed in [25], given a set of bus routes with fixed operation times, the minimum number of buses to complete all the routes is equal to the maximum number of routes in operation in the same time period. Motivated by this observation, we develop a novel time-indexed ILP formulation for the SBSP. Although the ILP is hard to solve to optimality, we show that the optimal solution to the linear relaxation of the ILP is close to that of the ILP. We then introduce a randomized rounding algorithm which finds near-optimal solutions for large-scale problem instances. The randomized nature of the algorithms provides multiple solution options and more flexibility for the school district in policy making. This work provides solution approaches to public school districts searching for new solutions to budget challenges, introducing various approaches to lower transportation costs. Our work takes a first step towards leveraging structural information in bus transportation problems and leads to advances in both bus route design and bus scheduling problems. This thesis is supported by National Science Foundation (CMMI-1727744).

Creator