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

在路由问题中利用网络结构：在校车路由中的应用

• 批准号: 1727744
• 负责人: Karen Smilowitz
• 金额: $ 55.08万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1727744&HistoricalAwards=false
• 关键词: Exploiting; Network; Structure; Routing; Problems

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.

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

项目成果

Incorporating equity into the school bus scheduling problem

• DOI: 10.1016/j.tre.2019.08.006
• 发表时间: 2019-11-01
• 期刊: TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW
• 影响因子: 10.6
• 作者: Banerjee, Dipayan;Smilowitz, Karen
• 通讯作者: Smilowitz, Karen

The Covering Path Problem on a Grid

网格上的覆盖路径问题

• DOI: 10.1287/trsc.2019.0901
• 发表时间: 2019
• 期刊: Transportation Science
• 影响因子: 4.6
• 作者: Zeng, Liwei;Chopra, Sunil;Smilowitz, Karen
• 通讯作者: Smilowitz, Karen

A Bounded Formulation for The School Bus Scheduling Problem

校车调度问题的有界公式

• DOI: 10.1287/trsc.2022.1130
• 发表时间: 2022
• 期刊: Transportation Science
• 影响因子: 4.6
• 作者: Zeng, Liwei;Chopra, Sunil;Smilowitz, Karen
• 通讯作者: Smilowitz, Karen

On the use of operations research and management in public education systems

论运筹学和管理在公共教育系统中的运用

• 发表时间: 2020
• 期刊: Operations researchmanagement science
• 作者: Smilowitz, K;Keppler, S
• 通讯作者: Keppler, S