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

Across the United States, public school districts are facing critical budget crises [5, 24]. Aiming to keep cuts “away from the classroom”, bus transportation is often a common area to look for cost reductions [33]. This is the case at Evanston/Skokie District 65 (D65), a pre-K - 8 public school district north of Chicago with approximately 8,000 students at 18 schools (attendance area elementary schools, middle schools, magnet schools, an early childhood center, and a school for students with special needs). The school district has projected deficit of over $100 million over the next ten years [14]. In 2015, D65 and Northwestern University began a partnership to improve transportation operations, looking for opportunities to save costs while maintaining service. This partnership identified a number of challenges and opportunities in bus transportation which motivates the work described in this proposal. School bus routing has been studied by the operations research community for fifty years, identifying creative routing and scheduling approaches for school districts. In recent years, school districts have adopted routing and scheduling software to assist in bus transportation planning. However, such software can be limited in application. In this work, we take a different approach. We exploit the grid-like network structure common in many urban and suburban school districts to obtain simple solution approaches that can provide robust options to budget-challenged school districts. As such, this work contributes to a growing literature on routing problems with special network structure, while, at the same time, addressing a critical problem faced by many public school districts.