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

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

• 批准号: 2032458
• 负责人: Hadi Gard
• 金额: $ 20万
• 依托单位: University of South Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2032458&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的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。