D-STOP Software Improves Bus Routes for Charter School
D-STOP has built connections with the education community by solving the bus routing problem for KIPP, the second largest charter school in the Austin area. At KIPP, 86% of students are low-income, and 90% are minorities. KIPP provides bus services for students located throughout Austin to their two campuses. The school had 40 to 50 bus stops to include in their routes, which were being designed by hand. These routes were not performing well in terms of cost or efficiency; the previous year’s bus routes often had varying levels of bus capacity usage and travel times. Designing a bus route that optimizes both student travel time and bus capacity is a difficult task, particularly when there are many feasible routes that could include 40–50 bus stops. D-STOP took on the task of helping optimize KIPP’s bus routes and transportation planning.
To improve the routing, Dr. Stephen Boyles and his graduate student, Michael Levin, employed vehicle routing problem techniques. Using traffic network topology and travel times from a dynamic traffic assignment (DTA) model, they implemented the Clarke-Wright heuristic, which merges stops into routes in order of greatest savings. Bus stop demand was estimated geographically based on student addresses. The new routes were predicted to significantly reduce operating time while guaranteeing adherence to all constraints—and the routes lived up to this prediction.
The D-STOP-developed routing software was used for the first time during the fall 2014 semester. KIPP reported that both reductions in total operating time and significant increases in reliability.
- First, in previous years, some bus routes would often have demand that exceeded the capacity of a single bus, necessitating having a second bus on the same route to carry the excess demand. This was rather costly as the second bus was mostly empty. After using the developed routing software, demand predictions were more accurate and a second bus was not necessary.
- Second, under the old system, travel time predictions were often inaccurate, and buses would frequently arrive late at the bus stop relative to the published schedule. This led to a number of complaints from students and parents—particularly those parent dropping off young students at bus stops. The use of a calibrated DTA model improved the accuracy of travel time predictions, resulting in a significant decrease in the number of complaints despite greater bus ridership.
D-STOP is excited to have created such a significant improvement so quickly for the KIPP students, parents, and administrators. The center is optimistic that the models developed under D-STOP-supported research can lead to more efficient use of transportation infrastructure, decreasing congestion and supporting the economic competitiveness of not only the Austin area, but the rest of the nation as well.