Reliability-oriented unmanned aerial vehicle nest location optimization method for smart city management inspection
Article Text (Baidu Translation)
-
摘要: 为实现基于固定机巢的城管事件无人机自动巡查，降低机巢和无人机失效对效率与稳定性的影响，研究了基于多层级备援机制的固定机巢可靠性选址-分配问题；考虑任务点差异化巡查频率和固定机巢服务半径约束，构建了以机巢建设与运行总成本最小为目标的混合整数规划模型；提出基于拉格朗日松弛的混合算法，通过松弛选址-分配耦合约束，将原问题分解为机巢选址与多层级任务分配2个子问题精确求解以获得紧下界，设计覆盖增益驱动的选址修复算法生成可行上界，提出了基于邻域搜索的上界改进算法以加速收敛。研究结果表明：在小、中规模算例上，所提算法相较Gurobi求解器计算时间缩短57.56%~88.86%，大规模问题亦可在较短时间内给出高质量解；多层级冗余显著降低系统成本，以大连市中山区为例，3层冗余配置将总成本从72.36万元降至43.72万元，降幅约为39.59%，配置3层以上冗余机巢的边际收益显著减弱；随着机巢服务半径增大，总成本与建设成本先下降后趋于稳定，巡查成本基本不变；机巢采购单价与总成本、建设成本、巡检成本及人工巡检成本呈正相关，与机巢数量呈负相关；无人机单位飞行价格与总成本、建设成本和巡检成本近线性正相关，对人工巡检成本影响不显著。Abstract: To enable automatic inspection by unmanned aerial vehicles for urban management events based on fixed nests and to mitigate the impact of nest and unmanned aerial vehicle failures on efficiency and stability, the reliability-oriented fixed nest location-allocation problem with multi-level backup mechanisms was investigated. The differentiated inspection frequencies of task points and service radius constraints of fixed nests were considered, and a mixed integer programming model was formulated with the objective of minimizing the total cost of nest construction and operation. A hybrid algorithm based on Lagrangian relaxation was proposed. The original problem was decomposed into two subproblems, i.e., nest location and multi-level task allocation, by relaxing the location-allocation coupling constraints, and they were solved exactly to obtain a tight lower bound. A coverage gain-driven location repair algorithm was designed to generate feasible upper bounds. An upper bound improvement algorithm based on neighborhood search was proposed to accelerate convergence. Research results show that, for small-scale and medium-scale instances, the proposed algorithm reduces computation time by 57.56%–88.86% compared with Gurobi, while producing high-quality solutions for large-scale cases within short runtimes. Multi-level redundancy significantly reduces system costs. In the case of Zhongshan District of Dalian, the three-level redundancy configuration reduces the total cost from 723 600 CNY to 437 200 CNY, a reduction of approximately 39.59%. The marginal benefits of configuring nests with more than three levels of redundancy diminish significantly. As the nest service radius increases, total and construction costs decline and then stabilize, with inspection costs remaining nearly unchanged. Unit cost of nest procurement is positively correlated with total, construction, inspection, and manual inspection costs and negatively correlated with the number of nests. Unmanned aerial vehicle unit flight cost shows a near-linear positive correlation with total, construction, and inspection costs but has no significant impact on manual inspection cost.
-
图 1 考虑机巢失效的选址分配网络
Figure 1. Location-allocation network model considering UAV nest failures
表 1 城管巡查重点区域示例
Table 1. Example of key areas for urban management patrol
属性 信息 编号 2 中心位置 经纬度（121.614 6° E，38.914 3° N） 土地类型 商业密集区 土地面积 长度为800 m、宽度为600 m 巡查目标 占道经营、垃圾堆放、高楼消防、道路缺陷、违规搭建等 巡查建议 周期巡查 巡查频率 每日2次 预计时间 30 min 
下载: 导出CSV
表 2 算例计算结果
Table 2. Results of the case study
|L| p=0.2 p=0.4 建设成本/元 巡检成本/元 总成本/元 减小比例/% 建设成本/元 巡检成本/元 总成本/元 减小比例/% 1 140 000 583 589.69 723 589.69 120 000 1 045 150.68 1 165 150.68 2 220 000 244 856.50 464 856.50 35.76 220 000 522 238.55 742 238.55 36.30 3 240 000 197 152.96 437 152.96 39.59 300 000 318 732.27 618 732.27 46.90 4 240 000 196 557.38 436 557.38 39.67 340 000 252 554.99 592 554.99 49.14 5 240 000 196 557.38 436 557.38 39.67 340 000 259 423.45 589 423.45 49.41 6 240 000 196 557.38 436 557.38 39.67 340 000 248 918.71 588 918.71 49.46
下载: 导出CSV
表 3 算法对比结果
Table 3. Comparison of algorithms
算例
规模p 本文算法 Gurobi 邻域搜索算法 上界/元 下界/元 间隙1/% 间隙2/% 计算
时间/s最优值/元 计算
时间/s最优值/元 计算
时间/s43 0.05 105 184.15 104 318.98 0.82 0.00 15.40 105 184.15 45.36 109 337.47 14.37 0.10 114 958.47 114 393.89 0.49 0.00 23.89 114 958.47 47.68 115 282.68 15.35 0.20 131 409.26 130 264.34 0.87 0.00 24.22 131 409.26 52.19 131 409.26 15.87 0.40 199 953.00 199 016.53 0.46 0.00 16.84 199 953.00 48.87 201 353.17 12.77 117 0.05 341 427.73 339 216.62 0.65 0.12 140.04 341 019.17 874.98 346 427.35 89.30 0.10 374 218.52 372 235.16 0.53 0.00 157.28 374 218.52 1 149.77 377 794.63 72.04 0.20 437 152.96 434 805.52 0.54 0.00 112.66 437 140.04 1 284.42 442 392.88 65.54 0.40 618 732.27 615 276.77 0.58 0.00 114.97 618 732.27 1 422.75 623 721.91 66.88 285 0.05 802 045.38 778 385.04 2.95 521.33 3 600.00 818 810.07 430.02 0.10 879 347.98 861 936.89 1.98 487.25 3 600.00 887 876.48 433.98 0.20 1 021 561.95 1 003 963.52 1.72 267.25 3 600.00 1 031 273.42 411.06 0.40 1 466 341.79 1 444 221.75 1.51 444.06 3 600.00 1 483 952.38 402.59 注：“间隙1”表示所提算法计算得到的上下界之间的相对误差，“间隙2”表示所提算法获得的上界与Gurobi求解器获得的最优解之间的相对误差，加粗的结果表示算法横向对比中的最优表现。
下载: 导出CSV
-
[1] 刘磊. 街头政治的形成: 城管执法困境之分析[J]. 法学家, 2015(4): 31-47, 177.LIU Lei. The formation of the street politics: An analysis of the predicament of Chengguan's law enforcement[J]. The Jurist, 2015(4): 31-47, 177. [2] 彭仲仁, 刘晓锋, 张立业, 等. 无人飞机在交通信息采集中的研究进展和展望[J]. 交通运输工程学报, 2012, 12(6): 119-126. doi: 10.19818/j.cnki.1671-1637.2012.06.018PENG Zhong-ren, LIU Xiao-feng, ZHANG Li-ye, et al. Research progress and prospect of UAV applications in transportation information collection[J]. Journal of Traffic and Transportation Engineering, 2012, 12(6): 119-126. doi: 10.19818/j.cnki.1671-1637.2012.06.018 [3] 赵兴科, 李明磊, 张弓, 等. 基于显著图融合的无人机载热红外图像目标检测方法[J]. 自动化学报, 2021, 47(9): 2120-2131.ZHAO Xing-ke, LI Ming-lei, ZHANG Gong, et al. Object detection method based on saliency map fusion for UAV-borne thermal images[J]. Acta Automatica Sinica, 2021, 47(9): 2120-2131. [4] 冯棣坤, 张洪海, 华明壮, 等. 面向城市低空物流的多层异质起降场点网络协同规划[J]. 交通运输工程学报, 2026, 26(2): 110-124. doi: 10.19818/j.cnki.1671-1637.2026.086FENG Di-kun, ZHANG Hong-hai, HUA Ming-zhuang, et al. Multi-layer heterogeneous take-off and landing site network collaborative planning for urban low-altitude logistics[J]. Journal of Traffic and Transportation Engineering, 2026, 26(2): 110-124. doi: 10.19818/j.cnki.1671-1637.2026.086 [5] 马涛, 吴俊, 唐樊龙, 等. 基于多源数据与大模型的无人机巡航风险识别技术[J]. 交通运输工程学报, 2026, 26(3): 75-88.MA Tao, WU Jun, TANG Fan-long, et al. Unmanned aerial vehicle cruise risk identification technology based on multi-source data and large models[J]. Journal of Traffic and Transportation Engineering, 2026, 26(3): 75-88. [6] HONG I, KUBY M, MURRAY A T. A range-restricted recharging station coverage model for drone delivery service planning[J]. Transportation Research Part C: Emerging Technologies, 2018, 90: 198-212. doi: 10.1016/j.trc.2018.02.017 [7] GENTILI M, MIRCHANDANI P B, AGNETIS A, et al. Locating platforms and scheduling a fleet of drones for emergency delivery of perishable items[J]. Computers & Industrial Engineering, 2022, 168: 108057. [8] GHELICHI Z, GENTILI M, MIRCHANDANI P B. Logistics for a fleet of drones for medical item delivery: A case study for Louisville, KY[J]. Computers & Operations Research, 2021, 135: 105443. [9] 叶深文, 张钢, 罗志勇. 无人机集群巡检道路的航线规划与分布式机场选址方法[J]. 广东工业大学学报, 2023, 40(5): 64-72.YE Shen-wen, ZHANG Gang, LUO Zhi-yong. Route planning and distributed airport site selection method for UAV swarm road inspection[J]. Journal of Guangdong University of Technology, 2023, 40(5): 64-72. [10] KABASHKIN I, KULMURZINA A, NADIMOV B, et al. Synchronized multi-point UAV-based traffic monitoring for urban infrastructure decision support [J]. Drones, 2025, 9(5): 370. doi: 10.3390/drones9050370 [11] 戴永东, 黄政, 高超, 等. 多目标优化最低代价无人机机巢选址方法研究[J]. 重庆大学学报, 2023, 46(6): 136-144.DAI Yong-dong, HUANG Zheng, GAO Chao, et al. A UAV nest deployment method with multi-target optimization and minimum cost[J]. Journal of Chongqing University, 2023, 46(6): 136-144. [12] 高云飞, 胡钰林, 刘鸣柳, 等. 多无人机输电线路巡检联合轨迹设计方法[J]. 电子与信息学报, 2024, 46(5): 1958-1967.GAO Yun-fei, HU Yu-lin, LIU Ming-liu, et al. Joint multi-UAV trajectory design for power line inspection[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1958-1967. [13] ZHAO F, MO W H, HU Y, et al. Efficiently optimizing drone nest deployment for transmission line inspection based on heuristic algorithm[C]//IEEE. 2023 China Automation Congress (CAC). New York: IEEE, 2023: 9326-9331. [14] CAI L, LI J L, WANG K, et al. Optimal allocation and route design for station-based drone inspection of large-scale facilities[J]. Omega, 2025, 130: 103172. doi: 10.1016/j.omega.2024.103172 [15] HUANG Z, WANG H X, TANG Y M, et al. A two-stage location-allocation optimization method for fixed UAV nests in power inspection considering node failure scenarios[J]. Sensors, 2025, 25(4): 1089. doi: 10.3390/s25041089 [16] DASKIN M S. A maximum expected covering location model: Formulation, properties and heuristic solution[J]. Transportation Science, 1983, 17(1): 48-70. doi: 10.1287/trsc.17.1.48 [17] SNYDER L V, DASKIN M S. Reliability models for facility location: The expected failure cost case[J]. Transportation Science, 2005, 39(3): 400-416. doi: 10.1287/trsc.1040.0107 [18] CUI T T, OUYANG Y F, SHEN Z M. Reliable facility location design under the risk of disruptions[J]. Operations Research, 2010, 58: 998-1011. doi: 10.1287/opre.1090.0801 [19] SHEN Z J M, ZHAN R L, ZHANG J W. The reliable facility location problem: Formulations, heuristics, and approximation algorithms[J]. INFORMS Journal on Computing, 2010, 23(3): 470-482. [20] YUN L F, FAN H Q, LI X P. Reliable facility location design with round-trip transportation under imperfect information part Ⅱ: A continuous model[J]. Transportation Research Part B: Methodological, 2019, 124: 44-59. doi: 10.1016/j.trb.2019.04.002 [21] YUN L F, WANG X F, FAN H Q, et al. Reliable facility location design with round-trip transportation under imperfect information Part Ⅰ: A discrete model[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 133: 101825. doi: 10.1016/j.tre.2019.101825 [22] 黄志文, 李鸿旭, 钟元芾, 等. 不确定条件下战时应急物资配送中心选址研究[J]. 计算机工程与应用, 2023, 59(4): 269-279.HUANG Zhi-wen, LI Hong-xu, ZHONG Yuan-Fu, et al. Study on emergency distribution center location in wartime under uncertainty[J]. Computer Engineering and Applications, 2023, 59(4): 269-279. [23] 孙华丽, 项美康. 设施失灵风险下不确定需求应急定位-路径鲁棒优化研究[J]. 中国管理科学, 2020, 28(2): 199-207.SUN Hua-li, XIANG Mei-kang. Robust optimization for emergency location-routing problem with uncertain demand under facility failure risk[J]. Chinese Journal of Management Science, 2020, 28(2): 199-207. [24] 李卓伦, 陆建, 王学瑞, 等. 城市物流无人机起降点与卡车停靠点协同选址方法[J]. 交通运输工程学报, 2026, 26(3): 89-105.LI Zhuo-lun, LU Jian, WANG Xue-rui, et al. Collaborative location method for drone vertiport and truck parking point in urban logistics[J]. Journal of Traffic and Transportation Engineering, 2026, 26(3): 89-105. [25] 李姗, 张洪海, 李卓伦. 城市低空物流无人机立体航路网络规划方法[J/OL]. 交通运输工程学报, 2026, https://doi.org/10.19818/j.cnki.1671-1637.2026.163 .LI Shan, ZHANG Hong-hai, LI Zhuo-lun. Planning method for three-dimensional air route network of urban low-altitude logistics drones[J/OL]. Journal of Traffic and Transportation Engineering, 2026,https://doi.org/10.19818/j.cnki.1671-1637.2026.163 .[26] SHERALI H D, ALAMEDDINE A. A new reformulation-linearization technique for bilinear programming problems[J]. Journal of Global Optimization, 1992, 2(4): 379-410. doi: 10.1007/BF00122429 [27] MLADENOVIC N, BRIMBERG J, HANSEN P, et al. The P-median problem: A survey of metaheuristic approaches[J]. European Journal of Operational Research, 2007, 179(3): 927-939. doi: 10.1016/j.ejor.2005.05.034 [28] LIM M, DASKIN M S, BASSAMBOO A, et al. A facility reliability problem: Formulation, properties, and algorithm[J]. Naval Research Logistics (NRL), 2010, 57(1): 58-70. doi: 10.1002/nav.20385 [29] FISHER M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management Science, 1981, 27(1): 1-18. doi: 10.1287/mnsc.27.1.1 [30] YUN L F, QIN Y, FAN H Q, et al. A reliability model for facility location design under imperfect information[J]. Transportation Research Part B: Methodological, 2015, 81: 596-615. doi: 10.1016/j.trb.2014.10.010 -
图(7) / 表(3)
计量
- 文章访问数: 19
- HTML全文浏览量: 7
- PDF下载量: 2
- 被引次数: 0
