School Transportation Budgets

A guest article written by students Matthew Anderson and Franco Gomez, edited by Tyler Perini.

It’s no secret that public schools over America can and have faced issues with their budget. In lieu of the ongoing pandemic, it has become even more apparent that job security is not a guarantee, and unforeseen circumstances can cause schools to scramble to find ways to allocate their budget effectively. The research paper by Zeng, Chopra, and Smilowitz focuses on how to help public schools have more control over their budget by reducing their transportation costs. To state the obvious, fewer school buses are cheaper than more. The purpose of the article is to create an integer linear program (ILP) formulation by which public schools can reduce costs by minimizing the number of required school buses by staggering start times and utilizing multiple routes. The savings from effective optimization algorithms can be profound; by implementing the biobjective algorithm, the Boston Public Schools reduced public school transportation costs by $5 million (Bertsimas 2019).

There are two related problems of interest to study. The school bus scheduling problem (SBSP) is a subproblem of the school bus routing problem (SPRP), and SBSP aims to “optimize school start time and bus operation times to minimize transportation cost.” In this research paper, Zeng, Chopra, and Smilowitz present a time-indexed ILP with the aim of “minimizing the number of buses to serve all bus routes such that each route arrives in a time window before school starts.” The hope of this study is to start with a set of routes and buses to generate an ILP meant for a small set of public schools and then implement a randomized rounding algorithm in order to apply the findings to a larger scale scale to larger problems.

Shifting our focus to the model for the SBSP , there are two binary decision variables included. The first is x(i,t), which is equal to 1 if route i arrives at time t, and 0 otherwise. A set of routes and a school start times are given. These times are not continuous and are contained as intervals. (For instance, a time of 7:12:43 AM is unreasonable, but 7:15 AM is.) Say a school bus takes a particular route; then the binary decision variable is “on” (equal to 1) if that school bus will arrive at its school destination at a specific time given a particular route. Otherwise, we say that variable is “off” (equal to 0).

Another binary decision variable in this study is the binary variable y(s,t), which is on if school s starts at time t, and off otherwise. These variables are indexed by the same set of time intervals but also an additional set of public schools.

Binary decision variables are like a light switch! The lightbulb is turned on when the value equals 1. Conversely, when the value equals 0, the lightbulb is turned off. When their conditions are met, binary decision variables turn “on,” and they can not only control lights but also other mechanisms in the model. However, when their conditions are not met, they are turned off, and they don’t directly impact the model — there’s only darkness.

One final decision variable z represents the maximum number of school buses needed. This is more representative of the objective for this model, but since it’s linked with a constraint we will discuss, it’s worth a brief mention. The objective of the model is to minimize the maximum number of school buses needed, i.e., to minimize z.

Now, to get into the ILP model:

• The first two constraints are assignment constraints. (1a) makes sure that each route is assigned to a start time, and (1b) makes sure that each school is assigned to a start time. Intuitively, this makes sense because both x and y are binary variables, and the constraints make sure that that exactly one of each variable is turned on for all routes and all schools in the program. It does this by setting the sum of the binary variables across all the times equal to one for each route and for each school. Notice that the binary decision variable cannot be on for multiple times, so each unique route and school have unique start times.
• (1c) is a time constraint that guarantees each bus route will reach the school at a time before school starts. In the summation indices of (1c), t’≥t presents an arbitrary time and l(s) is the length of the time window it takes for a route to arrive at school. For example, it is good if a school starts at a time t’ when x(i,t) is turned on because it ensures that the bus will reach the school before school starts. If that school doesn’t start at t, then the school should start at t+1, or t+2, etc. up until t+l(s). On the flipside, if x equals one but an appropriate y is never turned on because the school doesn’t start at any of the particular times, then the constraint will not be satisfied, which will be helpful in determining whether the school needs to shift its start time or add more buses.
• The fourth constraint (1d) links the decision variables to the objective z. This constraint introduced the variable r(i), which denotes the length of route i. With this in mind, we can see that the left side of (1d) sums the total number of routes in operation within the feasible time interval. This constraint is what enables the model to minimize the maximum number of busses required.

Essentially, constraint (1d) sets the maximum number of buses required equal to the maximum number of routes in operation during the same time interval. In this example, three buses are assigned to three routes. Each bus can only travel that specific route. In other words, we want at least one bus to be assigned to one route.

This ILP was the first one presented in the article and thus is the simplest version of the model. It incorporates restrictions on school start times and route operation times by fixing part of the decision variables, sets appropriate bounds, and accounts for school start times. However, the complexity of the model makes it difficult to solve. To account for this, the authors present two more complex ILP models. The second version of the ILP makes the model easier to solve and the third ILP uses a randomized rounding algorithm that generalizes the model and implements it at a larger scale.

Although this paper focuses on minimizing the maximum number of school buses needed, there are certainly other objectives that can help reduce costs, such as optimizing routes and bus stop locations. Nevertheless, the authors provide an in-depth look at multiple possible models to reduce costs by optimizing the number of buses needed. School districts that are struggling with their budget, especially in light of the ongoing pandemic, should consider the methodology discussed in this research paper.