目录
- 1.摘要
- 2.问题描述与数学建模
- 3.QLNS算法
- 4.结果展示
- 5.参考文献
- 6.算法辅导·应用定制·读者交流
1.摘要
针对异构无人机机队在应急医疗服务中的任务分配与取送货路径规划问题，考虑供应短缺、时间窗及地理限制等挑战，本文构建了以最大化总利润为目标的混合整数线性规划模型。针对大规模问题提出一种增强Q学习自适应大邻域搜索算法（QALNS）。
2.问题描述与数学建模
面向应急医疗的异构无人机任务分配与取送货路径规划（HUTA-PDP）构建最大化总利润MILP模型，在三阶段（前置运营、任务分配、航路规划）框架下，考虑了资源短缺、时间窗、无人机载重、航程及高度等多重约束，并允许部分次要需求不被服务。
max ∑ k ∈ K ∑ ∑ r ∈ R p j r d j r y j r k \max\sum_{k\in K}\sum\sum_{r\in R}p_{jr}d_{jr}y_{jr}^kmaxk∈K∑∑r∈R∑pjrdjryjrk
3.QLNS算法
初始化
通过四个步骤生成初始可行解：1.基于组合与容量约束随机生成任务序列；2.生成顶点序列并合并同顶点任务以消除子回路；3.更新库存与可用任务集；4.结合地理和飞行参数计算到达时间。
破坏-修复算子
针对HUTA-PDP设计了三对基于任务序列的破坏与修复算子，通过更新任务链并同步重构顶点和时间序列来迭代优化解。
破坏算子：随机破坏(RD)随机移除多个任务并回补库存I n v r e m a i n I_{nvremain}Invremain与剩余任务集T a s k r e m a i n T_{askremain}Taskremain；基于群组破坏(GD)以客户点为单位，直接清空无人机k kk访问的某群组下的所有任务；最差利润破坏(WPD)则按利润由低到高依次剔除低效益任务。
修复算子：随机修复(RR)在满足载荷与库存I n v r e m a i n I_{nvremain}Invremain约束下，随机从T a s k r e m a i n T_{askremain}Taskremain抽取任务插入；基于群组修复(GR)优先向无人机k kk已有的访问群组中追加该群组的其他未完成任务；最佳利润修复(BPR)将T a s k r e m a i n T_{askremain}Taskremain按利润降序排列，优先插入高利润任务，并通过重排使同群组任务相邻以防止重复访问。
Q-learning机制
双重Q-learning机制动态调整算子选择和操作率，**算子选择（QL1）**状态（State）由改进、多样性和差值三类指标组合离散化为30个状态；动作（Action）为3对破坏与修复算子交叉组合的9种操作。奖励函数根据新解质量调整：
R Q L 1 = { 8 if O b j ( ς ′ ) > O b j ( ς ∗ ) 5 if O b j ( ς ′ ) = O b j ( ς ∗ ) 3 if O b j ( ς ) < O b j ( ς ′ ) < O b j ( ς ∗ ) 1 if ς ′ is accepted 0 if ς ′ is not accepted R_{QL1} = \begin{cases} 8 & \text{if } Obj(\varsigma') > Obj(\varsigma^*) \\ 5 & \text{if } Obj(\varsigma') = Obj(\varsigma^*) \\ 3 & \text{if } Obj(\varsigma) < Obj(\varsigma') < Obj(\varsigma^*) \\ 1 & \text{if } \varsigma' \text{ is accepted} \\ 0 & \text{if } \varsigma' \text{ is not accepted} \end{cases}RQL1=⎩⎨⎧85310ifObj(ς′)>Obj(ς∗)ifObj(ς′)=Obj(ς∗)ifObj(ς)<Obj(ς′)<Obj(ς∗)ifς′is acceptedifς′is not accepted
**操作率确定（QL2）**状态由目标值改进与计算速度共同定义；动作为6个操作率区间；奖励函数考量质量提升与耗时缩短：
R Q L 2 = { 8 if O b j ( ς ′ ) > O b j ( ς ∗ ) and P ( I t e r ′ ) < P ( I t e r ) 5 if O b j ( ς ′ ) > O b j ( ς ∗ ) and P ( I t e r ′ ) ≥ P ( I t e r ) 3 if O b j ( s ) < O b j ( ς ′ ) ≤ O b j ( ς ∗ ) and P ( I t e r ′ ) < P ( I t e r ) 1 if O b j ( s ) < O b j ( ς ′ ) ≤ O b j ( ς ∗ ) and P ( I t e r ′ ) ≥ P ( I t e r ) 0 otherwise R_{QL2} = \begin{cases} 8 & \text{if } Obj(\varsigma') > Obj(\varsigma^*) \text{ and } P(Iter') < P(Iter) \\ 5 & \text{if } Obj(\varsigma') > Obj(\varsigma^*) \text{ and } P(Iter') \geq P(Iter) \\ 3 & \text{if } Obj(s) < Obj(\varsigma') \leq Obj(\varsigma^*) \text{ and } P(Iter') < P(Iter) \\ 1 & \text{if } Obj(s) < Obj(\varsigma') \leq Obj(\varsigma^*) \text{ and } P(Iter') \geq P(Iter) \\ 0 & \text{otherwise} \end{cases}RQL2=⎩⎨⎧85310ifObj(ς′)>Obj(ς∗)andP(Iter′)<P(Iter)ifObj(ς′)>Obj(ς∗)andP(Iter′)≥P(Iter)ifObj(s)<Obj(ς′)≤Obj(ς∗)andP(Iter′)<P(Iter)ifObj(s)<Obj(ς′)≤Obj(ς∗)andP(Iter′)≥P(Iter)otherwise
4.结果展示
PDPTW基准测试：QALNS在多数算例中达到已知最佳解，并在200-800任务的大规模算例中刷新记录，400任务算例平均提升6.50%，双重Q学习机制未削弱计算时效。
敏感性分析，学习率α = 0.3 \alpha=0.3α=0.3时算法最稳定，目标值平均提升1.75%；折扣因子γ = 0.9 \gamma=0.9γ=0.9时全局寻优与时效最佳，目标值提升1.37%，CPU时间对两参数更敏感。
5.参考文献
Lin Z, Xu X, Demir E, et al. Optimizing task assignment and routing operations with a heterogeneous fleet of unmanned aerial vehicles for emergency healthcare services[J]. Computers & operations research, 2025, 174: 106890.
6.算法辅导·应用定制·读者交流
xx
)
