Exploiting Network Structure in Routing Problems: Applications to School Bus Routing

Northwestern University, Evanston IL

Investigators

Abstract

Public school districts in the United States are under great pressure to improve operations and reduce costs of support services in order to better support classroom education. Expanding on a partnership with a densely populated suburban school district, this project provides a comprehensive approach to improving student transportation needs. The project will support optimization-based approaches to district-wide school bus routing that address staggered bell schedules, mixed fleet capacity, community bus stops, and after school transportation needs. More broadly, this research project will support better planning and decision-making for urban public transit in locations with grid-like road networks. The educational component includes the involvement of K-12 teachers in developing modules to help students understand the value of operational methods to provide decision-making support for complex, practical problems, such as transportation planning. This work introduces an innovative approach to the joint problem of vehicle stop selection and vehicle route generation, leveraging the underlying grid-like structure of the road network to obtain robust, implementable solutions. Methodological advances revolve around analyzing the Covering Path Problem with non-uniform distances between stops. While the Covering Path and Hamiltonian Path Problems are in general NP-hard, even on general grid graphs, this project will investigate trade-offs between stop-minimizing designs and length-minimizing designs. Starting with analysis of the single vehicle, single destination covering path problem on a complete grid, the problem setting is generalized to consider the multiple vehicle, multiple destination problem. Complexities in the school bus routing context, including robustness to demand, staggered school starting schedules, and mixed capacity fleet availability are also addressed. This research will lead to advances in route optimization modeling and solution approaches and contribute to a growing literature on routing problems with special network structure.