Collaborative Research: Arc Routing Problems in Combined Drone/Truck Fleets

合作研究：无人机/卡车联合车队中的弧线路由问题

• 批准号: 2032460
• 负责人: Sung Hoon Chung
• 金额: $ 23.77万
• 依托单位: SUNY at Binghamton
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2032460&HistoricalAwards=false
• 关键词: Collaborative; Research; Arc; Routing; Problems

This award contributes to national prosperity by advancing planning methods for combined drone/truck fleets to serve critical societal needs, such as energy transmission infrastructure monitoring, urban police patrolling, rural and suburban mail delivery, roadway pavement inspection, and traffic monitoring. Despite the significant opportunities offered by drones for remote operations, their limited flying time and small battery capacity hamper large-scale operations. Coordination between drones and roadway-dependent motor vehicles, such as trucks, can help resolve these issues by providing batteries and payload required for continued drone services. This project will provide a novel approach to cover large service areas using combined drone/truck fleets. This award highlights the societal applications characterized by combined ‘arc’ routing, for which existing routing methods cannot provide adequate decision-making tools. In particular, this project will validate the methods developed through a case study involving surveillance of electric power transmission lines, the backbone of the nation’s energy infrastructure. This project will train the future workforce in computational operations research and develop open-source software packages to support the further use of unmanned vehicles. The project will advance our understanding of arc routing problems in combined drone/truck fleets by developing computational optimization models and algorithms. The combined drone/truck arc routing problem is fundamentally different and significantly more challenging than traditional arc routing problems because drones can fly directly from one point to another point in the network without following ground arcs. In addition, a drone may serve only part of an arc due to its limited capacity and footprint, or potentially multiple distinct routes covering the entire arc. The optimal routing of mobile hubs served by trucks must also be incorporated into this already challenging problem. Furthermore, a drone may launch from one truck and return to another truck if beneficial; therefore, synchronization between drones and trucks plays a significant role. This project will provide a novel mixed-integer linear programming formulation and adaptive heuristics based on decomposition, dynamic programming, partitioning, large neighborhood search, and machine learning for efficient operations of the combined fleets. The models and algorithms will be validated with actual data from power transmission line monitoring.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

该奖项通过推进无人机/卡车联合车队的规划方法来满足关键的社会需求，如能源传输基础设施监测，城市警察巡逻，农村和郊区邮件递送，道路路面检查和交通监控，从而为国家繁荣做出贡献。尽管无人机为远程操作提供了重大机会，但其有限的飞行时间和小电池容量阻碍了大规模操作。无人机和依赖道路的机动车辆（如卡车）之间的协调可以通过提供持续无人机服务所需的电池和有效载荷来帮助解决这些问题。该项目将提供一种新的方法，使用无人机/卡车车队覆盖大型服务区域。该奖项突出了以组合“弧”路由为特征的社会应用，现有的路由方法无法提供足够的决策工具。特别是，该项目将通过一个案例研究验证开发的方法，该案例研究涉及对国家能源基础设施的骨干电力传输线的监控。该项目将培训未来的计算操作研究工作人员，并开发开源软件包，以支持无人驾驶车辆的进一步使用。该项目将通过开发计算优化模型和算法来促进我们对无人机/卡车联合车队中的弧形路由问题的理解。无人机/卡车组合弧路由问题与传统的弧路由问题有着根本的不同，并且更具挑战性，因为无人机可以直接从网络中的一个点飞到另一个点，而无需遵循地面弧。此外，无人机可能由于其有限的容量和占地面积而仅服务于弧的一部分，或者可能覆盖整个弧的多个不同路线。由卡车服务的移动的枢纽的最佳路线也必须纳入这个已经具有挑战性的问题。此外，无人机可以从一辆卡车发射并返回到另一辆卡车（如果有益的话）;因此，无人机和卡车之间的同步起着重要作用。该项目将提供一种新的混合整数线性规划公式和自适应算法，基于分解，动态规划，分区，大邻域搜索和机器学习，以实现联合舰队的有效运营。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。