论文信息：Lei Cai, Jiliu Li, Kai Wang*, Zhixing Luo and Hu Qin. Optimal Allocation and Route Design for Station-Based Drone Inspection of Large-Scale Facilities. Omega, August 2024, accepted.
1. 前言
随着工业电力设施的规模日益扩大，无人机逐渐成为巡检这些大型设施的重要工具，尤其在风力涡轮机和电力传输塔等领域中备受关注。这不仅因为无人机能显著提升巡检效率，还能大幅降低维护成本。在这一背景下，我们探讨一种新型的基于站点的无人机巡检问题（SDIP），专注于如何最优分配与设计巡检任务，以最大限度地降低固定站点和无人机的运行成本。
SDIP可以被看作是location-routing problem的变体，是一个NP-hard问题。为了得到最优解，论文采用了logic-based Benders decomposition (LBBD)算法进行精确求解。LBBD算法是对经典Benders decomposition的扩展，适用于任意形式的子问题，在往期推文中我们有过详细介绍，不明白的朋友们可以事先学习一下~
运筹学教学|Benders decomposition（一）技术介绍篇
运筹学教学|Logic-based Benders Decomposition技术介绍(一)
2. 问题描述
对于大型电力设施，传统的人工检查一般通过多种方式进行，包括地面巡逻、登塔、使用吊臂车和直升机等，不仅昂贵还效率低下。越来越多的公司开始使用高效灵活的无人机进行巡检工作，但受限于电池容量，部分偏远地区很难完成无人机的电池更换。针对这一问题，论文提出了基于站点的无人机巡检模式，每一个站点（Automatic Battery Swap Station, ABSS）都配备有一辆无人机。无人机从ABSS出发前往各个大型设施检查（每个设施只需被检查一次），并通过信号传输将结果立即反馈回ABSS，当电量不足时无人机需要返回ABSS更换电池。为了确保信号传输的稳定性，每一个ABSS都有其特定的服务半径和运行时间限制。
图2通过示例详细描述了这种巡检模式。考虑3个ABSSs侯选位置，11个待检设施。图中展示了两辆无人机分别部署在和位置的ABSS内，并有四条可行的飞行路径，该飞行路径均保持在ABSS的服务半径内。
定义无向图，其中为点集，包括设施集合、ABSSs出发和终点集合，为弧集。定义每个ABSS的服务半径为、运行时间为、固定成本为，每辆无人机的飞行时间为、电池容量为。对于点，定义服务时间为，当时，则表示无人机的换电时间。此外，无人机经过边的飞行时间为，相应的电量消耗为，当无人机悬停在点进行检查时对应的电量消耗则为。
SDIP的问题决策主要是确定每个ABSS的位置，为ABSS分配需要检查的设施，为无人机设计巡检路线。目标是将总检查成本（即飞行时间和服务时间）和ABSS固定成本降至最低。论文中建立的MILP模型在这里就不做具体展示了，主要包括无人机的路径结构约束、设施到ABSS的分配约束、设施访问约束、ABSS的服务半径和运行时间约束、无人机的电量约束等。
3. LBBD算法
显然，SDIP的决策可以被系统地分为一个两阶段过程，第一阶段决策ABSS的选址并分配待检设施，第二阶段为每一个ABSS生成无人机的飞行路径。因此，可以使用LBBD算法对该问题进行精确求解。
该算法主要是在一个branch-and-check框架中实现。首先求解一次主问题（MP）并获得可行的整数解，然后通过相应的子问题生成Benders cuts，不断迭代直到optimality gap收敛为0。在每次迭代中，算法在分支树中搜索MP的可行整数解来作为SDIP的下界（lower bound, lb），同时通过列生成求解子问题的线性规划松弛问题（RSP）；如果所有RSP最优解的成本加上MP解的成本足够大，则添加Benders cuts以加强主问题，否则采用分支定价算法精确求解子问题，获得最优整数解并更新上界（upper bound, ub），同时基于该解生成的logic Bender cuts将被加到主问题中。
3.1.Logic-based Benders decomposition
optimality Benders cuts和feasibility Benders cuts，分别如下所示：然而当主问题MF1生成了不可行的分配解时，子问题RF1-i对应生成的对偶解具有不稳定性，这导致feasibility cuts只能消除变量的部分不可行组合。论文采取了两种措施来提高feasibility cuts的有效性，一是采用列生成算法求解松弛子问题RF1-i；二是添加一条strengthened inequality到主问题MF1中，该不等式用于提供ABSS总运行时间的下界，避免主问题产生极值解。
3.2. Logic cuts
论文还基于SF1-i的最优解提出了三条logic cuts，以删除主问题的一些不可行或非最优解。一条有效的logic cut需要满足下述两个性质：
每次迭代产生的cuts能排除当前产生的全局不可行解 cuts不能排除任意全局可行解
性质1保证在主问题的解数量有限时的收敛性，性质2保证最终的最优性。在论文的LBBD算法中，可将这些cuts分为logic feasibility cut和logic optimality cut。
(1) Logic feasibility cuts
(2) Logic optimality cuts
no-good cut）如下所示：上述cuts只有当后续迭代再次出现解时有效，即提供了一个比optimality Benders cut更紧的下界。
analytical cut，以确保后续迭代时从中移除或插入一些设施的有效性：3.3. Column generation and BP
论文采用列生成算法求解RF1-i以应对变量指数级增长的问题，其对应的定价问题可以被写成：
该定价子问题属于传统的ESPPRCs。论文采用了分支定价算法求解SF1-i，BP算法属于非常经典的精确算法，具体的求解过程这里就不再赘述啦。
此外，文章还考虑了ABSS内的无人机电池数量有限的情况。对于该种情况，只需对LBBD进行轻微的修改，即在前面提到的模型F1中添加一条电池数量约束：
其中表示ABSS 内的无人机电池数量。相应的，后续的cuts和检验数都做对应调整即可。
结束语
指导老师：秦虎教授（华中科技大学管理学院，tigerqin1980@qq.com）
文案&排版：李璠（华中科技大学管理学院，fiona@hust.edu.cn）
