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

为了更好地支持课堂教育，美国的公立学区面临着改善运营和降低支持服务成本的巨大压力。在与人口密集的郊区学区合作的基础上，该项目提供了改善学生交通需求的综合方法。该项目将支持基于优化方法的全区校车路线，以解决错开的上课时间、混合车队容量、社区巴士站和放学后的交通需求。更广泛地说，这个研究项目将支持在网格状道路网络地区更好地规划和决策城市公共交通。教育部分包括K-12教师参与开发模块，帮助学生理解操作方法的价值，为复杂的实际问题（如交通规划）提供决策支持。这项工作引入了一种创新的方法来解决车辆停车选择和车辆路线生成的联合问题，利用路网的底层网格状结构来获得鲁棒的、可实施的解决方案。方法上的进步围绕着分析站点间距离不均匀的覆盖路径问题。虽然覆盖路径和哈密顿路径问题通常是np困难的，即使在一般的网格图上，这个项目将研究停止最小化设计和长度最小化设计之间的权衡。从分析完整网格上的单车、单目的地覆盖路径问题入手，将问题设置推广到考虑多车、多目的地问题。还解决了校车路线环境中的复杂性，包括对需求的鲁棒性、错开的学校开学时间表和混合容量车队的可用性。这一研究将推动路径优化建模和求解方法的进步，并有助于增加具有特殊网络结构的路由问题的文献。

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.