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.