optimizing school bus routes

This is my second post on politics this month (this month’s INFORMS blog challenge–my first post is about snow removal).  There are few political topics that invoke an emotional response as strongly as does K12 public education.  My daughter started attending the public school system this year, and I have been surprised at how, well, political school is.  But given the budget cuts over the past few years, some of that is understandable.

I learned the bus route that my daughter would take before the school year began.  My first reaction was to wonder if the bus routes were optimized (what else would my reaction be?).  Designing bus schedules isn’t rocket science, but it can be haphazard, leading to kids spending extra time on the bus, wasted gas, and late bus drivers.

A quick search on the web indicates that bus route scheduling is quite the political issue.

• A multiobjective optimization model that balances efficiency and equity.  The approach first creates routes by grouping students into clusters using a multi-objective districting algorithm, and then optimizes each group of students using set covering and traveling salesman problem algorithms.  The objectives include minimizing the number of buses, minimizing the fleet travel times, balancing the work loads among the buses, and minimizing student walking distance.
• A multiobjective optimization model for creating bus routes for kindergarten in Hong Kong
• An optimization model for generating bus routes for New York City schools with the objective of reducing the number of buses.
• A recent review in EJOR summarizes school bus route selection.  They write that routing school buses can address the following issues in various sub-problems: “data preparation, bus stop selection, bus route generation, school bell time adjustment, and bus scheduling.”

In my neck of the woods, I could probably identify near-optimal solutions without having to build a model (there are a number of small, isolated subdivisions with low road connectivity, which makes routing and bus stop selection a breeze).  But other bus routing scenarios are more complex, either due to the sheer size of the school system, the density and layout of neighborhoods, or not-so-simple school boundaries.

One feature that makes bus routing tough are “fair” policies for allocating students to schools that use lotteries to let parents select their schools: any child could attend any school so buses for every school could pass through a single neighborhood.  Good bus routes become much harder to identify (unless OR is used!), and regardless, students would have to spend more time on the bus as the distance to school increases.

Michael Johnson and and Karen Smilowitz’s excellent TutORial on Community Based Operations Research contains a brief overview about allocating public education resources.  In addition to school bus routing, operations research has been used to

• design recommendations for school closures in a region that reflect socio-economic characteristics of the students in different areas of the region.
• develop forecasting models for school attendance as input to optimization models for locating public-school buildings and setting attendance boundaries.
• use data envelopment analysis (DEA) that uses school performance observations to guide secondary schools for ways to improve their performance.

Have you seen OR used for public education?

Related posts:

• snow removal using a shovel, a plow, and operations research