基于排队优化的无人机响应网络设计：应急救援药物配送场景

论文题目：Drone-Delivery Network for Opioid Overdose - Nonlinear Integer Queueing-Optimization Models and Methods

大牛作者：Miguel A. Lejeune 乔治华盛顿大学商学院决策科学终身教授，方法论重点包括随机规划、分布鲁棒优化、决策依赖不确定性下的优化、排队和混合整数非线性规划；应用涵盖医疗、供应链与灾害管理、安全和军事行动、能源与电力系统、野火管理和金融等。担任《Operations Research》、《INFORMS Journal on Computing》、《Mathematical Programming》、《Computational Optimization and Applications》以及《Open Journal on Mathematical Optimization》的副主编。

E-mail：mlejeune@gwu.edu ‎

基于排队优化的无人机响应网络设计：应急救援药物配送场景

论文摘要

本文针对阿片类药物过量急救场景，研究如何通过无人机网络缩短响应时间。传统救护车响应常需 7–8 分钟，而无人机可显著缩短首剂纳洛酮到达时间。论文提出无人机网络设计问题（DNDP），将系统建模为一组 M/G/K 排队系统，并构建最小化平均响应时间的非线性分式整数模型。

为解决模型中的非线性与整数耦合难题，作者提出两步式 MILP 重构方法，将原模型等价转化为混合整数线性规划，并结合外近似分支定界算法实现高效求解。基于弗吉尼亚海滩真实数据的实验表明，无人机网络可将平均响应时间缩短 82%，生存概率提升 2.73–4.00 倍，每年额外挽救 17–33 条生命。

一、研究背景与问题定义

1.1 阿片危机与响应时间矛盾

• 阿片过量死亡激增：1999–2019 年美国过量死亡近 50 万人 ，每日约 130 人因阿片过量死亡 。
• 响应时间关键性：患者每过一分钟生存率降低 10% ，而救护车平均到达时间 7–8 分钟，高峰或偏远地区更慢 。
• 无人机优势突出：无人机成本远低于救护车且能够快速飞行，初步测试表明无人机递送纳洛酮明显快于救护车 。

1.2 问题描述

为解决“如何配置与调度无人机以最小化阿片过量救援响应时间”的问题，论文提出 无人机急救网络设计问题。其核心任务包括：

• 在候选站点中选择若干 无人机基站(DB)，并决定每个基站的 无人机数量；
• 将随机到来的 过量触发请求(OTR) 分配给合适的基站；
• 最小化平均响应时间 ，以最大化患者生存率。

该问题涉及地点选择、资源配置与排队调度三类决策，是具有显著拥堵效应的服务系统设计问题。

二、模型构建与关键公式

2.1 排队模型假设与变量

论文将无人机网络视为多个 M/G/ 排队系统 ：

• 到达过程：每个需求点  的过量事件到达服从泊松分布，速率为 。通过决策变量  表示地点  是否由基站  服务，则基站  的总到达率为

  其中  是位于基站  覆盖半径内的需求点集合。

• 服务时间模型：服务时间包括飞行时间、现场处置时间与返航准备时间。若  表示基站  与需求点  的欧氏距离，飞行速度为 ，则单次服务的期望时间为

  其中  为现场操作时间， 为重置时间。

• 响应时间：考虑排队等待时间  和飞行时间，需求点  的期望响应时间为

• 决策变量：

• ：基站  是否开放；
• ：需求点  是否由基站  服务；
• ：基站  部署的无人机数量。

• 约束：每个需求点必须被分配且只能分配给一个覆盖范围内的基站；总基站数和无人机数受限；排队系统稳定性要求到达率小于服务率 。

2.2 基本模型与难点

综合上述变量，作者给出了平均响应时间  的分式表达式：

并建立了 基础模型 B-IFP。该模型既有 非线性分式目标函数，又涉及整数变量，难以直接求解。难点包括：

• 非凸性：目标函数包含非线性分子与分母，既不凸也不凹 。
• 高阶多项式与阶乘项：包含指数、阶乘和高次多项式，使连续放松问题极难处理 。
• 决策依赖的不确定性：服务时间的均值和到达率由决策变量决定，导致传统排队模型方法难以应用。
• 混合整数：既有二进制决策也有可变整数 ，增加了组合复杂度。

三、模型重构与算法创新

3.1 MILP 重构框架

为攻克求解难度，作者提出两步式 MILP 重构方法：

1. 辅助二进制变量与分式转移：将容量  用一组二进制变量  表示，转化为与无人机数量有关的组合选择问题。这一步将原问题重写为新的分式问题 R-BFP，使分母中不再出现决策变量的阶乘和指数项 。
2. 线性化与变量提升：通过经典线性化技巧，如二进制变量乘积线性化 ，以及二进制与有界连续变量乘积线性化 ，对残留的多项式项进行转化，引入辅助变量  等，最终得到等价的 MILP 模型 R-MILP 。作者证明该线性化不仅对  有效，还可推广到任意排队容量 。

此重构的主要贡献在于：消除了指数和阶乘项，引入的线性约束数量相对较少，并可保证分式项不出现 0/0 等不确定情况 。

3.2 外近似与分支剪枝算法

尽管 R-MILP 已是线性形式，但其规模巨大。为进一步提升求解效率，文章设计了两种 外近似算法：

• 外近似算法 (OA) ：先忽略部分“延迟约束”，求解一个简化的松弛问题，并在过程中按需加入这些约束。这种方法利用懒惰约束的思想，减少初始问题规模 。
• 外近似分支剪枝算法 (OA-B&C) ：在 OA 的基础上动态添加有效不等式和最优性割，形成分支剪枝框架，以进一步缩减搜索空间。作者还利用重构中较为紧凑的 R-MILP 替代大规模的 L-MILP，形成 R-OA-B&C 方法。

实验结果表明：面对 50 个真实实例，传统非线性求解器 BARON 无法在 1 小时内求解任何实例，而 R-OA-B&C 能在同一时间内求解全部实例且规模可扩展 。

3.3 方法流程图

文章研究的整体方法可概括为以下步骤：

四、案例分析与实验结果

4.1 数据来源与设置

研究团队收集了弗吉尼亚海滩市 2018 年第二季度至 2019 年第二季度的阿片过量事件数据，并将一年分为训练和测试季度。候选基站包括消防站、警察局等公共设施，参数如无人机速度、覆盖半径等通过实地测试确定。

4.2 空间分布与网络配置

下图展示了 2018Q2 与 2018Q3 两个季度的过量事件分布及最优无人机网络配置。每个黑点代表一个无人机基站，阴影圈表示其覆盖范围，基站周围的矩形或圆圈表示开闭变化。可以看到，网络能自适应需求分布变化，例如在 2018Q3 在西南部新增基站以覆盖新增的远程请求 。

4.3 性能评估与比较

1. 响应时间显著降低：经过交叉验证，网络平均响应时间为 1 分 39 秒，而弗吉尼亚海滩救护车系统为 9 分 19 秒，减少近 82% 。
2. 生存概率大幅提升：根据不同心脏骤停生存函数 ，无人机网络的平均生存概率是救护车网络的 2.73–4.00 倍 。
3. 挽救更多生命：一年内估计有 560 起过量事件，其中 84 起伴随心脏骤停。使用无人机后，预计可挽救 17–33 名患者 。
4. 质量调整生命年(QALY)收益：假设幸存者平均余寿 11.4 年，每年生活质量折扣 0.85 且折现率 3%，则每名幸存者可获得约 8.47 个 QALY。无人机网络可产生 143–279 个额外 QALY ，成本每 QALY 约 257–502 美元 。

下图展示了不同生存函数下，使用无人机和救护车网络的平均生存概率比较；无人机显著更高。

4.4 算法效率分析

作者比较了四种求解方法：直接求解非线性模型 (REFO)、外近似 (OA)、外近似分支剪枝 (OA-B&C) 以及利用紧凑重构的 OA-B&C (R-OA-B&C)。如图所示，R-OA-B&C 在任意运行时间下都能解决更多实例，显著优于其他方法 。这表明 MILP 重构与外近似策略的有效性。

五、贡献评价与未来展望

5.1 创新点与学术贡献

• 创新性建模：首次针对阿片过量急救设计了 包含决策依赖服务时间的 M/G/K 排队网络模型，解决了以往研究中服务时间假定固定的问题 。
• 严谨的重构理论：提出通用的 MILP 重构方法，证明了任何最小化平均响应时间的 M/G/K 队列系统均可线性化求解 。
• 高效算法框架：设计了结合懒约束与有效不等式的 外近似分支剪枝算法，使大规模实例在实用时间内可解 。
• 实证价值：使用真实数据展示无人机急救网络在减少响应时间、提高生存概率及成本效益方面的显著优势 。

5.2 局限性与未来方向

• 法规与安全：无人机飞行需遵守航空法规并面对恶劣天气、隐私等挑战 。
• 模型假设：泊松到达、服务时间分布等假设可能与实际存在差异，未来可引入更复杂的随机过程或学习驱动的预测。
• 算法扩展：重构与外近似方法虽高效，但仍依赖求解器。未来可以探索基于强化学习或元启发式的实时调度策略。

六、结语

通过将急救无人机网络视为 M/G/K 排队优化问题，并利用 混合整数线性化与外近似算法，该研究系统地解决了无人机基站选址、资源配置与调度三类关键决策，显著提高了阿片过量患者的救治效率和生存概率。其理论方法具有普适性，可推广至其他紧急医疗配送场景，为智能化医疗救援网络设计提供了重要参考。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。