Automatic Generation of School Bus Routes in Los Angeles

Abstract

The goal of our project is to automatically generate school bus routes for the Los Angeles Unified School District (LAUSD). We examined four algorithms, including two from the existing literature and two new ones that we developed. A major focus of our work was the construction of “mixed-load routes,” which transport students from multiple schools. Based on our measurements (whose imperfections we discuss), three of the four algorithms perform at least as well as the existing route plan, and one of those three performs better than the existing route plan. We also delivered a user-friendly routing program to LAUSD that uses one of these algorithms, and we have made our software publicly available. Our insights and results are also applicable to other school districts that permit mixed-load routing.

About the Project

Every regular school day, LAUSD operates over 14,000 hours of service using 1,307 school buses to serve over 38,000 students, who attend more than 300 schools in more than 30 subdistricts, on 1,669 routes over a service area of about 750 square miles. Bus contractors own and operate another 700 school buses to provide service for LAUSD. LAUSD also provides service for midday, athletic events, after-school programs, and on weekends. The buses are subject to traffic conditions — operating both during peak traffic times and during non-peak traffic times — and to changing enrollment patterns. LA’s very large geographic area, as compared to other US cities, makes the problem particularly acute (and also scientifically interesting).The project team seeks to help the Student Transportation Operation of the LAUSD better match its capacity with demand. Specifically, UCLA seeks to answer the following stakeholder question: What is the best way to operate their bus service within regulatory and policy guidelines?