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

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

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.