第二十三届华为杯研究生数学建模竞赛D题范文 山区洪涝无人机应急运输与通信中继优化

2中国研究生创新实践系列大赛“华为杯”第二十三届中国研究生数学建模竞赛D题范文空中投送。本文以广西横州市镇龙乡的灾后场景计算口径，再依次研究单点往返组批、多点多架次调度、通信约格单调后用二分法求得最大安全载荷：A型对15个服务区均可满载25kg,B型仅对S008降为28.8kg,C型在5个远端服务区降至58.9～68.9kg。随后枚举满足载质量、体积和返航余量的732个装载模式，建立装载模式整数规划，依次以架次数、累计作业时间和总能耗为目标做字典序求解，得到18个架次(C、B型各9架次)的组批方案，累计作业9.10h、能耗59.13kWh,比FFD启发式节能21.3%。由ε约束分析可知，三项指标在最少架次处基本一致；返航余量超过23%后架次数阶梯上升，达到36%时S008已无法服务。机与电池互斥及充电周转约束的多行程异构车辆路径与调度模型，间、能耗和架次数为目标。以列表调度为解码器，采用自适应大邻域搜索求解，6组权重并行得到11个帕累托近似解，经熵权TOPSIS选出折中方案：22个架次(其中9个多点架次)在106.2min内送完全部物资，80箱全部按期送达，能耗67.20kWh;与问题一方案直接排程相比，完成时间缩短36.9%,并消除了1881.8s的硬时限违约。针对问题三，对5040个轨迹采样点做链路预算与视线遮挡判定，发现仅S001、S006、S011在交接高度可直连网关，其余服务区往返轨迹有35%～53%的时间直连中断。在1725个回传可用的候选悬停点中求最小集合覆盖得到3个必需悬停点，并按两点最大覆盖补充2个备选点；再把问题二的解码器改为通信感知列表调度，中继按需派出、续航不足时轮换。折中方案由21个运输架次和3个中继架次组成，联合完成时间125.0min,221个通信时段无中断且全部按期送达，总能耗67.48kWh,比在问题二方案上直接补排中继缩短针对问题四，用并查集把同一架次涉及的服务区合并为8个不可拆分的块，以区间图着色求各组资源的精确最小值，并计入中继架次跨组服务时的重低于平均值一半的均衡约束下穷举127种二分区和966种三分区，依次按总缺口、资源总数和作业量变异系数择优：整体执行需27台(组)资源，未超库存；分为2组需35台(组),缺口5;分为3组需41台(组),缺口11,其中中继无人机缺4。缺口主要来自覆盖区相比资源分别减少4和2。可行性检验。从计算结果看，本场景下通信中继是制约投送效率和分区执行的关键资源，31问题背景与重述 61.1问题背景 61.2问题重述 61.3总体解题思路 72模型假设与符号说明 72.1模型假设 72.2符号说明 93数据预处理与统一计算口径 93.1数据说明与质量检查 93.2航段地形剖面 3.3统一计算口径 3.3.1航段几何与飞行时间 3.3.2等效航程与能耗 3.3.3充电周转 3.3.4通信链路判定 4问题一的建模与求解 4.1问题一的分析 4.2问题一的模型建立 4.2.1最大安全载荷模型 134.2.2组批的装载模式整数规划 4.2.3多目标处理与组批模型 4.3问题一的求解与分析 4.3.1求解算法 4.3.2最大安全载荷 4.3.3组批方案 4.3.4与其他方案的比较 4.3.5指标之间的权衡关系 4.3.6返航安全余量的灵敏度分析 5问题二的建模与求解 5.1问题二的分析 5.2问题二的模型建立 45.2.1决策变量 5.2.2调度模型 5.2.3目标函数与递推关系 5.3问题二的求解与分析 5.3.1求解算法 5.3.2收敛情况与帕累托解集 5.3.3调度方案与送达情况 5.3.4方案对比与可行性检验 6问题三的建模与求解 6.1问题三的分析 6.2问题三的模型建立 256.2.1轨迹离散与通信状态 6.2.2中继选址模型 6.2.3中继架次的时间与能耗 6.2.4联合调度模型 6.3问题三的求解与分析 6.3.1求解算法 6.3.2通信可达性与悬停点 6.3.3联合调度方案 6.3.4与问题二的比较及可行性检验 6.3.5指标之间的权衡关系 7问题四的建模与求解 7.1问题四的分析 7.2问题四的模型建立 7.2.1不可拆分块 7.2.2各组资源需求 7.2.3评价指标与分区优化模型 7.3问题四的求解与分析 7.3.1求解方法 7.3.2不可拆分块与整体需求 7.3.3分区与资源配置方案 7.3.4两种分区方式的比较 7.3.5资源缺口的原因 58模型的优缺点与展望 8.1模型的优点 8.2模型的不足 8.3模型的改进与推广 参考文献 附录A支撑材料文件列表 附录B人工智能工具使用说明 38附录C求解算法伪代码 附录D补充图表 附录E结果明细与可行性检验 47附录F主要程序代码 6些村落在几个小时内同时失去道路、电力和通信。2026年7月，台风“美莎克”带来的持续降雨使广西横州市镇龙乡遭受严重洪涝，洪水、落石和道路塌方从多个方向阻断交通，全乡一度断路、断电、断网，约8000人受困，食品、饮用水和药来越突出[4]。不过，无人机能否完成一次投送，不只取决于能不能飞到目标点，还受载重、航程、爬升高度、沿线地形净空和电池余量的共同约束，空中投送要把运输组织、通信保障和有限装备的存在缺口。题目以镇龙乡及周边山区为背景设置标准测试场景：凤丹村设1个临时调度中心001,周边有15个服务区和80个不可拆分的货箱，物资分为医疗物资、饮用水、应急食品和生运输装备为A、B、C三种机型共8架无人机和同机型共享的电池组，另有2架中继无人机和6组能源组件。附件还给出30m数字高程模型(DEM)、无线链路参数，以及飞行时问题一：不考虑实体无人机和共享电池的调度，每个架次只从001往返一个服务区。要求计算三种机型对各服务区的最大安全载荷；在货箱不可拆航安全余量约束下确定各服务区的货箱组批方案，并综合架次数问题二：不考虑通信保障，每个架次可以依次访问多个服务区后返回001。要求在无人机与电池数量、充电周转以及医疗物资、首批保障货箱的时限约束下，联合确定组批、访问顺序、机型、具体无人机、共享电池和各架次开始时刻，综合配7经一架中继无人机的中继通信。要求联合确定运输方案与中拔、服务时段和能源组件分配，综合及时性、联合任务完成时间问题四：在问题三方案不变的前提下，把15个服务区分别划分为2个和3个任务组，各组独立执行、资源不得跨组调配。要求给出分区方案和池、中继无人机和能源组件数量，从资源规模、冗余、组间工作本文的总体思路如图1.1所示。四个问题共用一套计算口径，因此先对附件数据和DEM做预处理，生成240条有向航段的地形剖面，并把航段、时间、能耗、充电和通信链问题一的决策结构最简单，但其中的能耗计算会被后续各问反并用ε约束法和参数扫描分析指标权衡与返航余量本文先建立混合整数规划模型，再以列表调度为解码器、用自一的组批结果作为对照基准。问题三叠加连续通信约束，先对的通信可达性预计算，再用最小集合覆盖和两点最大覆盖选出中继悬停(1)附件给出的节点海拔视为地面海拔，用于确定作业高度；巡航高度与视线遮挡统一由30mDEM判定，因为题目规定需求与装备参数以附件为准，而DEM更适合(2)水平巡航能耗按单组电池可用能量对应等效航程线性折算，爬升附加能耗按重力势能除以爬升能耗效率计算，下降段不回收能量(3)交接悬停期间的能耗不单独计列，与题目给出的架次能耗式一致；不考虑风和(4)电池更换在工位固定准备时间内完成，换下的电池立即开始充电，充满后方可航段表与能耗函数_e约束权衡与余量灵敏度ALNS改进与TOP区间图着色核算资源分区穷举字典序择优节点高程核对航段地形剖面附件数据(5)同一服务区内同类物资的货箱除首批标记外没有差别，货箱送达时刻取该站交(6)一架中继无人机可同时为多架运输无人机提供中继，中继往返悬停点途中不要(7)视线遮挡判定不计地球曲率和大气折射，8km距离上曲率带来的高度差约5m,与DEM高程误差同一量级。92.2符号说明本文使用的主要符号见表2.1,其余符号在正文首次出现处说明。符号航段i→j的水平巡航距离航段i→j的计划巡航海拔航段i→j的爬升高度、下降高度机型g的最大载货质量、可用装载体积m机型g的返航安全余量比例架次p的总运输能耗机型g对服务区i单点往返的最大安全载荷装载模式p的物资箱数向量及其使用次数箱，次架次p的作业时长、开始时刻S货箱c的期望送达时间、首批截止时间S悬停点h对直连中断点k的覆盖系数一架或组题目附件包括五个基础参数表和一套地理空间数据(表D.1)。五个参数表字段完整，没有缺失值和明显的异常值，逐箱清单中非首批货箱的而非缺失。DEM来自CopernicusGLO-30[8],坐标系为WGS84,像元大小1/3600°,共1309行、1486列，高程41.7～1132.9m,无空值。该数据实为数字表面模型(DSM),含表格给出的节点海拔与DEM像元高程并不完全一致，16个节点中有9个差值超过3m,最大为S009的-10.6m,主要源于DSM含地表覆盖物以及节点不在像元中心。题目明确“需求、时限、装备和资源参数以附件给定值为准”,因此作业高度用表格海拔确定(O01取地面海拔、服务区取地面海拔以上30m),沿线净空和视线遮挡统一用DEM判断。3.2航段地形剖面像元的最高高程加50m。为了不漏掉被航线斜切的像元，本文沿航线以1/8像元为步长加密采样，取各采样点所在像元的高程最大值。16个节点之间共有240条有向航段。任务区的地形与节点分布如图3.1所示。调度中心001位于东南部的河谷中，海拔只有127.7m,而西北部和东南部各有一片海拔500～1000m的山地，服务区大多散布在两片山地之间的丘陵地带。各服务区到001的水平距离在2.81km(S011)到8.08km(S008)服务区(面积示意保障人口)调度中心001/网关G01图3.1任务区地形与调度节点分布从001出发的15条航段中，巡航海拔最低的是S001(273.1m),最高的是S014(591.9m)。去往S014和S003的航线分别要翻越约540m和510m的山脊，巡航海拔比出发点高出464m和434m,而去往S001的航线巡航海拔只比001高145m(典型剖面见图D.1)。爬升高度的差异直接体现在爬升时间和爬升附加能耗上，这是同等距离下各服务区能耗差别很大的原因。3.3统一计算口径记航段i→j的水平投影所经DEM像元集合为Ωij,像元k的高程为zk,则计划巡航记节点i的作业高度为HP,则爬升高度h去=H{;-H?P,下降高度h;j=H-H⁹。连续访问多个服务区时，每次投送后都从30m作业高度重新爬升。机型g在航段i→j上的飞行时间为接时间，本文把一个架次从开始准备到返回001的作业时长统一定义为式中，rp为架次p的路线，0表示001;np为架次装载的总箱数，npi为在服务区i交付的箱数；,tload=30s;对A、B型取150s和30s,对C型取180s和36机型g携带载荷q时的等效航程由题目给出：两部分组成。本文把标准航程理解为一组电池的可用能量所能距离能耗为,水平巡航能耗为为0,即下降段既不回收能量也不另计附加能耗。巡航能耗按航程折算、爬升能耗按势能折算，这一处理与配送无人机能耗模型比较研究中的常用做法一致[6]。航段能耗Egi;(q)为两者之和，架次p的总能耗必须满足返航安全余量约束：式中，qpij为架次在航段i→j上的剩余载荷，Pg取附件中的返航电量下限20%。架次结束时的荷电状态为,约束(3.7)等价于sp≥Pg。共享电池和中继能源组件都按两阶段等效模型充电。由结束荷电状态s充至满电所需组件为1800s。该函数在s=0.90处连续。同一资源的使用时段与充电时段不得重叠，不接收端b的有效接收门限为P₆h=Psens+Mb=-98+8=-90dBm。通信方向a→b端点i、j之间的总传播损耗为自由空间损耗与遮挡附加损耗之和[9]:元为步长采样。当时链路可用，记Aij=1。代入附件参数，直连、接入和回传三类链路的双向门限分别为122、116和126dB,无遮挡时可达12.51、6.27和19问题一可以拆成四个小问：求三种机型对15个服务区单点往返的最大安全载荷；在不可拆分、载质量、装载体积和返航余量约束下确定各服务区的组批方案；综合架次数、总能耗和累计作业时间优化组批并说明三者的关系单点往返时去程带载、回程空载，只要证明架次能耗关是一个区间，最大安全载荷可以用二分法直接求出。组的装箱问题，一般是NP难的，常用首次适应降序(FFD)之类的启发式近似求解[10];但本题每个服务区最多15箱、只有4种物资，可行装载模式的数量很少，完全可以枚举后建立整数规划求精确最优解。三个指标的重要性在应急场景下有明确先后，本文序优化，并用ε约束法[11]描绘权衡曲线来说明排序的合理性；返航余量在10%～40%范围内扫描。问题一的求解流程如图4.1所示。附件数据：节点坐标、30附件数据：节点坐标、30mDEM、机型参数、货箱清单航段地形剖面巡航海拔、爬升与下降高度按服务区枚举可行装载模式(质量、体积、能量)装载模式整数规划架次数→累计作业时间→总能耗字典序求解架次一能耗一时间权衡回填货箱编号，输出组批方案并检验能耗关于载荷单调二分法求最大安全载荷等效航程与能耗函数返航安全余量约束返航安全余量10%-40%灵敏度图4.1问题一的求解流程以0表示001,机型g对服务区i单点往返的最大安全载荷定义为9g;×=max{q∈[0,Qg]:Egoui(q)+Egio(0)≤(1-pg)Eg}若满载仍满足约束，则qg9×=Q₉。对服务区i和机型g,一个装载模式用计数向量a=(a1,a₂,a₃,a4)表示，分量依次为医疗物资、饮用水、应急食品、生活卫生用品的箱数。模式可行当且仅当式中，mk、vk为第k类物资的单箱质量和体积，nik为服务区i对第k类物资的需求箱数。确定的架次能耗Ep和作业时长Tp,分别由式(3.7)和式(3.3)算出。记Pi为服务区i在三种机型下的全部可行模式，整数变量xp为模式p被使用的次数，则架次数fi=peP:Tp,累计作业时间。问题一中各服务区之间没有资源耦合，15个服务区的组批可以分别求解。累计作业时间关系到整体保障速度；能耗在调度中心可以补充，优流研究也主张把物资短缺造成的损失放在运营成本之前考虑[12业时间、能耗的顺序做字典序优化，服务区i的组批模型为lexmin(fi,装载体积和返航余量的要求。求解时先求最小架次数f,在f₁=f的条件下求最短作业时间f3,再在前两者均取最优的条件下求最小能耗。为检验这一排序是否合理，另用ε约束法把全部服务区的架次总数固定为ε,分别求最小能耗与最短作业时间(此时f₂、f₃取15个服务区之和):令ε从f*逐步增大，即可看出多用一个架次能换来多少能耗或时间上的变化。求解步骤见附录中的算法C.1。最大安全载荷的二分精度取10⁻⁴kg;装载模式整数规划用PuLP调用CBC求解器，按式(4.4)的目标顺序依次求解三次，每次把前一指标固定在最优值。为了校核整数规划的结果，本文另写了一个动态规划：4.3.2最大安全载荷三种机型对各服务区的最大安全载荷及纯飞行往返时间见表4.1。A型C型A型B型C型从表中可以看出，A型对全部服务区都能满载25kg往返，限制它的是0.06体积而不是续航；B型只有去往最远的S008(8.08km)时载荷降到28.8kg;C型在S002、S003、S004、S008、S012这五个距离超过7km的服务区受能量约束，最大安全载荷只有58.9～68.9kg,比额定载重少14%～26%。C型满载时的等效航程只有12km,不到空载时往返要多用5min。用一架次C型；S001需求154kg,用两架次C型，分别装76kg和78kg;S002和S003各81kg,超过了C型在这两个远端服务区约68kg的安全载荷，于是拆成一架次C型(56kg)加一架次B型(25kg)。S009～S015每区3箱正好25kg,但体积0.067m³超过了AA型在这一方案中没有被使用：小批量任务上B型的体积够用且单位质量能耗更低，质量能耗分别约为0.066、0.073和0.090kWh/kg。问题一不限制各机型架次数，而实体机队中B、C型各只有2架，这种搭配在问题二中必然要作出让步。将本文方案与另一种排序、FFD启发式以及只用单一机型的方案比较(表D.3),其中机型架次。两种字典序排序得到同一个方案，说明在最少架次的前耗最低并不冲突。FFD同样用18个架次，但它优先开C型架次，许多架次处于轻载状态，能耗达到75.11kWh,本文方案比它节能21.3%。只用C型时能耗高出25.0%,只用B型需要35个架次，只用A型则需要52个架次。可见按任务规模匹配机型是降低能耗的关键。用式(4.5)把架次总数强制设定为18～32,分别求最小能耗与最短作业时间(图D.2)。的工位准备时间和150～180s的基础交接时间。能耗曲线先平后升：架次数由18增至19时，最小能耗只降低0.10kWh(0.16%),此后反而上升，32个架次时为65.37kWh。用0.46h的额外作业时间换0.10kWh的节能得不偿失，因此三项指标在最少架次处基本一致，先架次、再作业时间、最后能耗的优先顺序是合理的。指标之间4.3.6返航安全余量的灵敏度分析让返航安全余量在10%～40%之间以1%为步长变化，其余参数不变，重新计算最大最大安全载荷对返航余量的响应明显非线性。A型在余量不超过24%时对所有服务区都能满载，此后远端服务区的载荷迅速下降，对S008在余量为34%时降为0;B型和C型下降开始得更早，但更平缓。原因在于回程空载荷的能量迅速减少，而等效航程随载荷的3/2次方下降，越接近上限越敏感。组批结果呈阶梯状变化。余量在10%～23%之间时方案与基准完全相同；24%时C型对S004的安全载荷降到57.5kg,装不下该区59kg的需求，架次数增至19;28%、34%和35%时分别跳升到20、22和25个架次，总能耗增至75.64kWh。余量达到36%时，任何机型都无法向S008运送14kg的饮用水箱，组批问题变为不可行，38%时S004也出现同样情况。可见附件给出的20%余量距离方案发生变化的临界点还有3个百分点以上的裕度，把余量提高到25%左右只需多安排1个架次。问题一得到的最大安全载荷、装载模式的能耗与时间以及18个架次的组批方案，将5.1问题二的分析问题二要求在不考虑通信保障的前提下，为8架实体运输无人机安排多点多架次的投送任务，包含三个小问：一是综合配送及时性、全部任务完成时间、行优化，并说明各指标之间的权衡关系；二是给出运输与问题一相比，问题二有三处本质变化：一个架每次投送后递减，各航段能耗要按剩余载荷分别计算；决策对象31个货箱，其余货箱的期望送达时间只用来衡量及时性。问题二把带时间窗的车辆路径问题作为特例包含在内，后者是NP难问题[13,14],再叠加多行程、非线性能耗[15]和电池周转，直接用通本文先写出混合整数规划模型以明确决策与约束，再以列表调调整选用概率，在带时间窗的路径问题上表现稳定[16]。四到帕累托近似解集，再用熵权TOPSIS[17]选出折中方案，求解流程如图5.1所示。列表调度解码：按最早截止时刻排序后悔值插入模拟退火准则接受新解，按得分更新算子权重多组权重并行求解→帕累托近似解集→熵权TOPSIS输出路线、架次、逐箱送达时刻，独立检验资源可行性破坏：随机/最差/整架次整服务区/相关/最低装载率架次评价：枚举访问顺序5.2问题二的模型建立把同一服务区、同类物资且首批标记相同的货箱视为一个货箱组，组内货箱可以互换，80个货箱共分为62个组。记货箱集合为C,架次集合为P,无人机集合为U,电池集合为B。决策变量包括：Tcp∈{0,1}表示货箱c是否由架次p运送；zpu∈{0,1}表示架次p是否由无人机u执行；Wpb∈{0,1}表示架次p是否使用电池b;Sp≥0为架次p的开始时刻；Opy∈{0,1}表示在同一资源上架次p是否先于p′。架次p的访问顺序记为综合载荷、能量、时限和资源各方面的要求，问题二的多行程异构调度模型为积；第四组为逐段按剩余载荷计算的返航安全余量约束；第五、六组为医疗物资期望送达在共用资源上的先后次序；最后两组保证每个架次恰好分配一架同型电池，Ug、B₉为机型g的无人机与电池集合。目标F、剩余载荷qp,k和送达时刻te的后的剩余载荷为式中，Cp为架次p装载的货箱集合，Cp(ii)为其中在第l站交付的货箱。各航段能耗按该(1)解的表示与架次评价。一个解由若干架次组成，每个架次给定机型以及各货箱组的装载箱数。访问顺序不作为独立的决策变量：评价架次时枚举全部访问顺序(每个架次最多访问4个服务区，至多24种),在满足式(5.1)中载质量、体积和返航余量约束的顺序(2)列表调度解码。各架次按所含货箱的最早硬时限、最早期望时间和作业时长依次排序，逐个分配给最早可用的同型无人机和最早充满的同型电池刻的较大值，由此得到每个架次的开始时刻、每个货箱的送达式中，Chard为带硬时限的货箱集合，Hc为货箱c的硬时限，μ为罚系数(每迟到1min计100),保证搜索优先满足硬约束；输出的方案均为罚项为零的可行解。(3)初始解与算子。初始解把全部货箱按硬时限、期望时间和优先系数排序，依次贪区移除、相关移除(同一服务区及最近两个服务区)和最低装载率架次移除，每次移除3~10箱；修复算子3个：贪心插入、带10%随机扰动的贪心插入和后悔值插入，插入位置(4)接受准则与权重更新。新解优于当前解时接受，否则按模拟退火准则[18]以概率接受，温度Tk由0.03按几何方式降至0.0005。每100次迭代按更新算子权重，式中，ψ。为算子o在该阶段的累计得分(刷新全局最优得33分、优于当前解得9分、被接受得13分),θ。为使用次数。(5)多目标处理。权重入取6组，分别对应四项指标均衡、侧重及时性、侧重完成时间、侧重能耗、侧重架次数以及同时侧重及时性与完成时间，每组2个随机种子，共12个ALNS并行运行，每个迭代6000次。被接受且无硬约束违约的解存入外部档案并做非支配筛选，得到帕累托近似解集；再用熵权法对四个目标定权，按TOPSIS贴近度Cs=D₅/(D+D)选出折中方案，D、D为方案s到正、负理想解的加权欧氏距离。以均衡权重的一次运行为例(收敛曲线见图D.4),加权目标值在前1000次迭代由1.16降到0.81左右，此后几次跳出局部最优并继续下降，最终收敛到0.75。12次运行合并后得到11个非支配方案(图D.5),完成时间在102.0～131.8min之间，能耗在66.44～69.58kWh之间，架次数在20～23之间。完成时间最短的方案用了23个架次、能耗68.14kWh;架次最少的方案(20个)能耗降到66.5kWh左右，完成时间却拉长到131.5min。实体机队只有8架，要缩短完成时间就得把大批次拆给更多架次并行执行，而小批次的单位质量能耗更高，这是完成时间与能耗、架次数之间权衡关系的来源。熵权法给出的权重为迟到量0.185、完成时间0.320、能耗0.216、架次数0.279,TOPSIS选出的折中方案完成时间106.2min、能耗67.20kWh、22个架次，比完成时间最短的方案只慢4.2min,却少用1个5.3.3调度方案与送达情况折中方案的运输路线与资源时间线分别如图5.2和图5.3所示，22个架次的完整安排、逐箱送达时刻和资源使用明细分别见表E.3、表E.4和表E.5。开局8架无人机同时出动，A型的P2-01串联S013、SO10、S001,P2-02串联SO011、S007,B型的P2-06串联S001、S005,把首批医疗物资和饮用水尽快分散送到8个时限为3600s的服务区，17个一小时是70kg的两点架次，结束荷电状态在20.1%～20.6%之间，能量约束在这些架次上是紧约束。A型共执行10个架次，主要承担20～22kg的补送任务，问题一中没有用到的A型在这里成了主力之一，这是B、C型数量不足的直接结果。22个架次中有9个多点架次，其中1个访问三个服务区。A型架次往返001的首末航段图5.2问题二的运输路线(实线为服务区之间的航段)从图5.3可以看出，C型的U08从开局一直忙到最后，利用率100%,是整个方案的关键路径；U07的利用率为92.3%,两架B型约89%,A型在70.6%～87.1%之间，而每种机型都有2组电池只用了1次。可见限制完成时间的是C型和B型无人机的数量，而不是电池。全部80个货箱都在期望时间之前送达(图D.6),平均送达时刻51.3min,最后一箱在94.3min送达；时限为7200s和10800s的硬时限货箱余量都在36min以上。5.3.4方案对比与可行性检验表5.1比较了三种方案。把问题一的18个单点架次(机型不变)直接交给实体机队排程时，由于B、C型各只有2架，这些架次只能排队执行，完成时间长达168.4min,按期率只有82.5%,且硬时限累计违约1881.8s。贪心构造的初始解满足了硬时限，但用了31个架次，能耗高达100.51AA型架次B型架次C型架次BA1图5.3问题二的无人机与电池使用时间线(数字为架次编号)表5.1问题二不同方案的指标对比架次(A/B/C)问题一组批直接排程贪心构造初始解本文折中方案kWh。经ALNS改进后，架次数降到22,能耗比初始解降低33.1%,完成时间比问题一方案直接排程缩短36.9%,全部货箱按期送达。与问题一不考虑机队数量时的能耗59.13kWh相比，问题二的能耗高出13.6%,这是满足时限要求和机队数量约束的代价。新计算每个架次的载重、体积、能耗与时间，再逐项检查无人和硬时限。6项检验全部通过(表E.6),最紧的架次能耗占电池可用能量的79.9%,结束荷电状态仍高于20%的返航下限。问题二的运输方案将作为问题三的初始解，在其上叠加持通信：与固定网关G01直连不可用时，必须经一架中继无人机转接，否则方案不可行。它包含两个小问：一是综合配送及时性、联合任务完无人机的架次数进行优化，并说明权衡关系；二是给出运输点须位于DEM范围内、离地不超过300m,中继完成30s建链后才能服务，续航受3.2kWh能源组件和20%返航下限限制，返回后需要300s周转；三是耦合关系，中继只有2因此本问分三步求解。第一步做通信可达性预计算：运输机的轨迹完全由航段决定，点对中断点的覆盖关系，后续调度只查表。第二步做中继选址：以覆盖001与各服务区之间往返轨迹上的全部中断点为约束求最小集合覆盖[19],并考虑同一时刻最多两架中继在把解码器改为考虑通信约束的列表调度(下称通信感知解码),中继架次在解码中按需派出、续航不足时轮换，中断时段无法覆盖时推迟运输架次。求解流程如图6.1所示。接入链路判定最小集合覆盖+两点最大覆盖，确定悬停点集合按需派出、续航不足时轮换，否则推迟架次ALNS上层优化运输方案(以问题二方案为初始解)候选悬停点：网格×离地三层筛选回传链路可用者判定直连可用性6.2问题三的模型建立按3.4节的规则，运输机在航段起点垂直爬升、以巡航海拔水平飞行、在终点垂直下降，交接时悬停在服务区上方30m。本文在16个节点的升降柱上每20m、在120条节点连线的巡航段上每150m取一个采样点，交接悬停点取升降柱底端，共5040个采样点。采样点k(三维位置ζk)与G01的直连可用性AkG由式(3.10)的总损耗与运输机和G01之间的双向门限122dB比较得到。候选悬停点h(位置ηh)只保留回传链路可用(门限126dB)的点，它对中断点k的覆盖系数为式中，LFSPL为式(3.10)中的自由空间损耗部分，b(·)为式(3.11遮挡时1.98km,计算中据此先按距离记K。为001与各服务区之间往返轨迹上的全部直连中断点，H为候选悬停点集合，yh∈{0,1}表示是否选用候选悬停点h。为保证每个服务区都至少能用单点架次服务，悬停点集合必须覆盖K₀,最小集合覆盖模型为式中，E为中继往返悬停点的飞行能耗，∈=10-³,用于在点数相同时优先选择近处、低式中，uk表示中断点k是否被覆盖。两个模型选出的悬停点合并为调度可用的悬停则到达悬停点的时刻t=Pk+tRre+toh,建链完成时刻t长=teT+tlink,返回001的时刻ηR=0.72。中继的返航电量要求为ER≤(1-pR)ER,use,其中ER,use=3.2kWh,p=20%,设运输架次p在开始时刻Sp下的直连中断时刻集合为Tut,时刻t所在位置能被悬停点h覆盖时记ap,n(t)=1。K为中继架次集合，选用中继架次k记yk=1,h(r点；B(t)表示t是否落在服务时段[t,t]内，ocC(t)表示k在t时刻是否占用一架中继机(从准备开始到周转结束)。问题三的运输与式中，加权迟到量F₁仍按式(5.2)计算；与问题二相比，完成时间取运输与中继架次返回001的最晚时刻，能耗与架次数计入中继，即约束中第二组要求每个直连中断时刻都有一架在岗s)和能源组件充电约束，k<k′表示k′紧接在k之后；H*中的悬停点均位于DEM范围内且离地不超过300m。同一时刻每架运输机只由G01或一架中继保障，这一点在解码时上层沿用问题二的ALNS,以问题二的折中方案为初始解；下层把列表调度解码器改为通信感知版本，步骤见附录中的算法C.3。架次评价时，对每种访问顺序先查预计算结果，把相邻且可覆盖悬停点集合有交集的中断采样合并为若干通信时段；若某个中断采样不能被H*中任何悬停点覆盖，则换一种访问顺序，全部顺序都不行则该装载不可行。解码时，每个通信时段[A,B]优先由已在岗的中继架次延长服务来覆盖；不行则为某架空闲中继插入一个新架次，其准备开始时刻取A-tlink-ton-tprD,同时检查中继的返航电量和前后架次的周转间隔；仍不行则把运输架次推迟60s再试。能源组件在解码结束后按时间顺序分配。上层ALNS的权重设置与问题二相同，12个并行搜索各迭代2500次。5040个采样点中有2328个(46.2%)无法与G01直连。只有S001、S006、S011三个服务区在交接高度能与G01直连，它们离001都在3.2km以内，即使被遮挡链路损耗也在门限之内；其余12个服务区的往返轨迹有35.2%～53.0%的时间直连中断，中断主要发生在靠近服务区的巡航段、下降段和交接悬停段，各服务区的统计见表D.4。在任务区外扩约2km的范围内以0.004°(约400m)为间距、离地100/200/300m三层生成3393个候选悬停点，其中1725个回传链路可用。Ko共含253个中断采样点，全部可被覆盖。最小集合覆盖需要3个悬停点H1、H2、H3;两点最大覆盖的最优组合H4、H5能覆盖233个中断点(92.1%),仍有20个覆盖不到，说明两架中继同时在岗无法一次性覆盖全部服务区，中继必须在不同悬停点之间轮换。5个悬停点的参数见表6.1,位置与直连区域如图6.2所示。离地30m时能与G01直连的区域集中在001周围3～4km的河谷内，与有遮挡时H5(离地300m)H5(离地300m)H4(H4(离地300m)H1(H1(离地200m)经度(E)离地30m可与G01直连区域图6.2中继悬停点与离地30m处的直连可用区域陵上，是S003、S007唯一可用的悬停点；H2位于北部、距001约6.4km,是S004、S008唯一可用的悬停点；H3位于东侧山脊、距001约3.9km,是S010、S012、S014唯一可用联合优化的12次运行合并后得到12个非支配方案，完成时间在111.7～130.8min之中方案由21个运输架次和3个中继架次组成，联合任务完成时间125.0min,总能耗67.48kWh(其中中继3.43kWh),全部货箱按期送达。中继架次安排见表6.2,运输架次与资源时间线分别见表E.7和图D.7。从时间上看，三个中继架次先保障东侧、再转向西侧，北部则全程有中继在岗。R02表6.2中继架次安排(悬停位置见表6.1)悬停点2先在东侧H3为东南方向的首批投送服务(816.6～1800.2s),周转并更换能源组件后前往西北的H1,为S003、S007方向服务到5391.5s;R01在北部H2从1206.4s一直服务到6747.2s,悬停约93min,结束荷电状态仍有37.2%。运输架次的时序明显迁就了中继：东南方向的5个架次都在前40min内完成，西部方向的4个架次集中在第36～91min。与问题二相比，开局只有5架同时出发，另有2架推迟1～2min以配合中继建链；6组能源组件只用了3组，不是瓶颈。细见表D.5),去程和S001交接全程直连，飞往S00与G01直连经R3-02中继经R3-03中继P3-08(C)P3-11(A)0表6.3通信约束对调度方案的影响问题二方案(不考虑通信)0问题二方案+通信感6联合优化折中方案(本文)36.3.4与问题二的比较及可行性检验表6.3给出了通信约束的影响。如果把问题二的方案原封不动，只在其上用通信感知4499.7s,还需要6个中继架次。联合优化后，运输方案主动按中继覆盖区重新组织：完成时间为125.0min,比补排方案缩短26.3min,硬时限全部满足，中继架次减少到3个；运输能耗反而比问题二低3.15kWh,因为运输架次更集中、装载率更高。与不考虑通信的问题二相比，完成时间增加18.8min(17.7%),这是通信约束的代价。独立检验覆盖货箱交付、载荷与能量、资源占用、硬时限、通信连续、中继周转与电量部通过(表E.8)。6.3.5指标之间的权衡关系与问题二相比，问题三的权衡多了一层中继的影响kWh,因为缩短完成时间需要让更多运输架次在中继在岗的时段并行，拆出的小批次单位能耗更高。在运输与中继之间，运输架次按间，但会让部分服务区等待。中继能耗只占总能耗的5%左右，但中继的数量和轮换决定源配置的影响。它包含三个小问：一是分别给出划分为2个和3个任务组时的分区与资源配置方案；二是从资源配置规模、资源冗余、组间工作量均衡和拆分的块，分区在块上进行。第二，各组独立执行、资源不得跨行本组既定任务所需的最少资源数。时刻固定后区间，最少资源数就是这些区间的最大重叠数模[21],可以精确求出。第三，一个中继架次若同时为两个组提供保障，分区后两个组都源总数反映配置规模；作业量变异系数反映组间均衡。为避免某组按资源最少以及按地理位置聚类的分区对比。求解流程如图7.1所示。中继机(含周转)、能源组件7.2问题四的模型建立把15个服务区合并为若干块B={β1,..,βn}。一个K分区就是把块划分为K个非空的组G₁,...,GK,第k组承担的运输架次集合记为Pk。组件共8类。任务p对资源γ的占用区间(a3,e?)定义为：运输无人机为(Sp,Sp+Tp);电第k组对资源γ的最少需求量为式中，Ⅱ为第k组中占用资源γ的任务集合。对运输资源，它由P.中对应机型的架次组成；对中继资源，记P(k)为中继架次k保障的运输架次集合，只要P(k)∩Pk≠ø,k就计入第k组。实际计算时以全部区间端点把时间轴划分为若干基本时段，式(7.1)中的最资源缺口、资源池化损失和组间作业量变异系数分别为W、σ(W)为其均值与标准差。资源的平均利用率定义为总占用时长与资源数、时间跨度式中，前三组约束保证每个块必须且只能属于一个任块数为n时，二分区有2n-1-1种，三分区有第二类斯特林数S(n,3)种。本文先对全部2”个块的子集递推计算资源占用曲线和需求量：去掉子集中编号最小的块即得到已算过的子集，两者的占用曲线相加即可；中继部分按子集所涉及问题三方案中有7个多点架次，合并后得到8个块，见表D.6。块B1由7个服务区组成，承担了49.7%的作业量，这是因为问题三为节省中继轮换，把东部和北部多个服务区串联在同一架次中。中继架次与块的关系为：R3-01服务B1、B7;B4、B5、B8;R3-03服务B2、B8。其中R3-02同时服务5个块，任何把这5个块拆开的分2架，A、B、C型电池6、4、4组，中继机2架，能源组件3组，共27台(组),除能源组件有3组富余外，其余资源都恰好用满库存，这也从侧面验证了问二分区共127种，其中64种满足均衡约束；三分区共966种，其中121种满足均衡约束。按式(7.3)选出的分区及各组资源配置见表7.1(服务区以编号后两位表示),分区示意如图7.2所示，各组任务量见表D.7。表7.1任务分区与各组资源配置服务区CABC4124230200233123223022020023个服务区)个服务区)经度(E)/009经度(E)图7.22个与3个任务组的分区示意(虚线连接同一块内的服务区)划分为2组时，G2-1包含B1、B2和S006,共10个服务区，承担74.4%的作业量；时，G3-1以B1为主(9个服务区，57.5%),G3-2为西部的SO03、S007(20.8%),G3-3表7.2不同分区方式的资源需求对比总数缺口不分区(问题三整体执行)2个任务组(本文分区)2个任务组(仅按资源最少)2个任务组(地理聚类对照)443个任务组(本文分区)3个任务组(仅按资源最少)3363个任务组(地理聚类对照)5一各方案的资源需求对比见表7.2和图D.8,下面从四个方面比较。(1)资源配置规模。不分区需要27台(组),分为2组、3组分别增至35台(组)和41台(组),增加29.6%和51.9%,组数越多，各组的资源峰值越难错开。(2)资源冗余。二分区的池化损失为8台(组),其中能源组件多3组、B型电池多2组、中继机多2架、B型无人机多1架；三分区的池化损失为14台(组),中继机一项就多出4架。中继机平均利用率从65.2%降到三分区时的55.5%。(3)组间工作量均衡。二分区、三分区选定方案的作业量变异系数分别为0.488和0.512。若不加均衡约束、只追求资源最少，二分区只需29台(组),但变异系数高达0.923(三分区为1.270)。由图D.9可见，资源最少的方(4)与库存的缺口。二分区缺口5:B型无人机缺1架、B型电池缺2组、中继机缺2架；三分区缺口11:A型无人机缺2架，B、C型各缺1架，A、B机缺4架，能源组件缺1组。与按块质心做K均值聚类的地理分区相比，本文分区在二分区、三分区时分别少用4台(组)和2台(组)资源。地理聚类的组间作业量更均衡，但它把共用同一中继架次的S015。二分区时两组都用到了全部3个中继架次，各需2架中继机，合计4架；三分区时共需6架，而库存只有2架。第二，B型装备的需求峰值在各组叠加。二分区时G2-2的五个小需求服务区都由B型服务，在第59min前后需要2架B型同时出动，而G2-1开局也需要1架，合计超出库存1架；B型电池在第91～96min出现4组的峰值，与G2-1的2组叠加后缺2组。第三，三分区时A型需求被拆散。G3-1开局需要3架A型，G3-2在第53min前后也需要3架，两组峰值时刻不同但不能互借，合计超出库存2架，A型电池也相应缺1组。(1)先建立统一的航段、能耗、充电和通信计算口径，补全了题目未给出的能耗分项表达式，四个问题共用同一套公式和数据，模型(2)组批、选址和资源核算都给出了精确解，NP难的调度问题用ALNS求解，并由(3)通信感知解码把中继选址、轮换和运输时序放在同一过程中处理，比先排运输(4)所有方案都经过独立的可行性检验，并对返航余量、指标排序和分区均衡约束8.2模型的不足(2)通信判定采用离散采样和400m间距的候选悬停点网格，可能漏掉更优的悬停求解上可以把中继选址与时段分配写成时间离散的整数案的最优性差距；建模上可以引入风场、需求动态更新和无附录A支撑材料文件列表支撑材料包含全部求解程序、输入数据与结果文件，清单见表A.1。表A.1支撑材料文件列表文件名文件说明1公共计算模块：数据读取、DEM查询、航段式23累托解集与熵权TOPSIS、可行性检验45穷举与对比分析6按顺序运行全部程序7附件数据(5个参数表、30mDEM、结果提交模板)8结果提交.xlsx(Q1～Q4全部sheet)、各问题结果与中间结果csv/json9结果文件与各问题的对应关系、公共计算口径、各问题可行性检验项及结果正文图片(PDF矢量图)附录B人工智能工具使用说明本文使用的人工智能工具及用途见表B.1。按规定第5条，辅助编写的每个程序文件开头【填写说明】本附录须由参赛队按实际使用情况如实填写和修改：写明工具名称、版表B.1人工智能工具使用情况选题评估与数据探查，建模思路与算法设计，求解程序编写与运行，结果图表绘制，论文初稿撰写与排版修改(填写)附录C求解算法伪代码正文第4～6章所用三个核心算法的步骤如下。输出：最大安全载荷,组批方案{zp}1:for每个服务区i和机型gdo3:否则在[0,Q₉]上二分，直到区间长度小于10-4,取可行端点为9:按所含医疗物资箱数从多到少排列各架次，首批保障箱优先放入第一个架次，回填货10:算法C.2问题二的自适应大邻域搜索输出：最优解x*与非支配解档案A1:贪心插入构造初始解x,令x*←x,各算子权重置为13:按权重轮盘赌选取破坏算子d与修复算子r,随机取移除箱数q∈[3,10]6:x*←x',x←x′,算子得33分8:x←x′,算子得9分10:x←x,算子得13分12:每100次迭代按式(5.6)更新算子权重；按几何方式降温算法C.3通信感知的列表调度解码输入：架次集合及其通信时段，悬停点集合H*,中继机日历(初始为空)1:按最早硬时限、最早期望时间对运输架次排序5:复制中继日历；对p的每个通信时段[S+a,S+b]与可覆盖悬停点集合M:6:若有在岗于M中悬停点的中继架次且延长至S+b不违反续航与周转，则延长7:否则为某架中继插入新架次，恰好在S+a前完成建链表D.1附件数据及其用途调度中心与服务区1个调度中心、15个服务区的坐标、海拔与保障人口节点位置、作业高度物资需求与配送时限组批与时限约束运输无人机数据享电池库存能耗、时间与资源约束中继无人机数据中继机型参数、2架中继无人机、6组能源组件中继能耗与周转收发参数巡航海拔、视线遮挡表D.2三类通信链路的双向门限与可达距离直连：运输无人机与G01回传：中继与G01虚线为各航段计划巡航海拔距001的水平距离(km)图D.1典型航段的地形剖面与计划巡航海拔表D.3问题一不同组批方案的指标对比整数规划：架次→时间→能耗(本文)整数规划：架次→能耗→时间FFD启发式(最大机型优先)仅用A型(字典序最优)仅用B型(字典序最优)仅用C型(字典序最优)图D.2问题一强制架次数下的最小总能耗与最短累计存在服务区无法服务返航安全余量(%)加权目标值加权目标值图D.4问题二ALNS的收敛过程(均衡权重)图D.6问题二逐箱送达时刻与期望送达时间的对比表D.4各服务区单点往返轨迹的通信情况服务区否否表D.5运输架次P3-04的通信保障明细开始/s结束/s001→S001爬升、巡航、下降直连一直