New Heuristics for the Operation of an Ambulance Fleet under Uncertainty

该论文针对救护车车队在不确定性下的调度问题，提出了包括最佳短视、非短视及多种贪婪启发式算法在内的新策略，并结合两阶段随机规划构建的滚动时域方法，在真实城市急救数据上实现了优于现有方法的响应时间并满足实时决策需求。

要点

这篇论文讲的是如何更聪明地管理救护车车队，特别是在面对突发状况和不确定性时。

想象一下，你是一家大型城市的“急救指挥中心”的总调度员。你的手里有一支由不同型号救护车组成的车队，而城市里随时可能有人拨打急救电话。你的任务非常艰巨：既要决定派哪辆车去救谁，又要决定救完人后这辆车该去哪。

这篇论文就是为了解决这个难题，提出了一套新的“聪明调度法”。

1. 核心难题：两个关键决定

救护车的工作就像一场永不停歇的接力赛，调度员主要面临两个决定：

• 决定一：派谁去？（救护车选择）
  当急救电话响起，是派离得最近的车，还是派能力最强的车？
  • 比喻： 就像你在玩《王者荣耀》或《英雄联盟》，队友召唤你支援。你是派一个离得近但装备一般的“新手”去，还是派一个离得远但装备神装的“大神”去？如果派了大神去救一个小火苗，万一后面来了个大火灾，大神就被困住了，这就亏大了。
• 决定二：救完去哪？（救护车重分配）
  救护车把病人送到医院后，是原地待命、回“老家”（固定站点），还是去别的地方待命？
  • 比喻： 就像外卖骑手送完一单，是回原来的站点休息，还是直接去下一个可能出单的商圈附近等着？如果回站点，可能离下一个订单很远；如果乱跑，可能又没单子。

2. 以前的做法 vs. 现在的创新

以前的做法（旧地图）：
很多旧方法比较“短视”或“死板”。

• 短视： 看到谁离得近就派谁，不管后面会不会有大麻烦。
• 死板： 规定救护车救完人必须回“老家”（固定站点）。但这就像让外卖员送完单必须回公司，哪怕下一个订单在隔壁街，他也得绕一大圈回去，效率太低。
• 忽略差异： 以前往往只把急救电话分个“紧急”和“不紧急”，忽略了救护车也有“普通版”和“高级版”（比如有的能除颤，有的只能做基础护理），也没考虑不同病人需要不同的技能。

这篇论文的新方法（新导航）：
作者提出了四种新的“调度算法”（也就是给电脑写的聪明指令），并配合一种叫**“滚动规划”（Rollout）**的高级策略。

• 四种新算法：

  1. 最佳短视法 (BM)： 虽然叫“短视”，但它比以前的短视更聪明。它不仅仅看距离，还看“性价比”。比如，如果有个高级救护车离得远但能救急，而普通救护车离得近但救不了，它会权衡一下，尽量不浪费高级救护车的“大招”。
  2. 非短视法 (NM)： 这个更厉害，它会“预判”。虽然它不能看到未来，但它会想：“如果我现在派这辆车去救 A，那 B 和 C 两个稍后可能发生的急救，会不会因为没车而延误？”它会为了未来的大局，牺牲一点眼前的利益。
  3. 贪婪法 (GHP1 & GHP2)： 这两种方法专门处理“排队”的情况。如果救护车都在忙，新来的电话就得排队。这两种算法会聪明地排序：是优先救那个等了很久的？还是优先救那个虽然刚来但病情最重的？它们会像排队买奶茶一样，动态调整顺序，让整体等待时间最短。

• 滚动规划（Rollout）：这是核心黑科技
  想象你在下围棋。如果你只看下一步，很容易输。如果你能看未来几步，就能赢。
  这篇论文的方法就是：每次做决定时，电脑会在脑海里模拟未来 100 种可能发生的情况（比如：如果 5 分钟后这里又有人叫车怎么办？如果那辆车路上堵车怎么办？）。
  它通过快速模拟这些“平行宇宙”，计算出哪种决定在未来最划算，然后做出选择。

  • 比喻： 就像开车导航，它不是只看眼前红绿灯，而是模拟了“如果走这条路，5 分钟后会不会堵车”，然后告诉你走哪条路最快。

3. 为什么这套方法很牛？

1. 考虑了“人”和“车”的差异：
   它知道有些病（比如心脏骤停）需要“高级救护车 + 高级医生”，有些病（比如擦伤）“普通车”就行。它不会让“法拉利”去拉砖，也不会让“拖拉机”去救心脏病人。
2. 考虑了“排队”和“未来”：
   它允许电话排队，并且会根据排队的时间长短和病情轻重，动态调整派车顺序。
3. 速度极快：
   虽然电脑要模拟 100 种未来，但它算得飞快（几秒钟）。这意味着在真实的急救现场，医生打电话进来，系统能立刻给出最佳方案，不会让病人等太久。
4. 实战效果好：
   作者用巴西里约热内卢的真实数据（几百万人口的城市）做了测试。结果发现，这套新方法比过去文献里提出的 8 种其他方法都要好，响应时间更短，资源利用更合理。

4. 总结：一个生动的比喻

如果把急救系统比作**“城市里的超级英雄战队”**：

• 旧方法像是：只要有人喊救命，就派离得最近的超级英雄去，不管他是“大力士”还是“隐身侠”，也不管他刚打完怪累不累，打完怪必须回基地睡觉。
• 新方法像是：有一个超级 AI 指挥官。
  • 当有人喊救命，AI 会想：“大力士离得远，但隐身侠离得近。虽然隐身侠离得近，但那个病人需要大力士的力量。而且，如果我把大力士派过去，5 分钟后东边可能会发生大火灾，需要大力士。所以我决定，派隐身侠去处理眼前的小麻烦，让大力士在附近待命，随时准备救火。”
  • 当超人救完人，AI 不会让他回基地，而是会看地图：“东边刚才火警多，西边现在很安静。你刚救完人，去东边待命吧，那里马上又要有麻烦了。”

一句话总结：
这篇论文发明了一套**“会思考、会预判、懂搭配”**的救护车调度系统。它不再只是机械地派车，而是像一位经验丰富的老将军，在混乱的战场上，根据敌情（病情）、兵种（救护车类型）和地形（交通状况），实时计算出最优的排兵布阵，从而挽救更多的生命。

技术摘要

这是一篇关于在不确定性条件下优化救护车车队调度的学术论文的详细技术总结。

1. 问题背景与定义 (Problem Definition)

核心问题：
急诊医疗服务（EMS）的救护车车队运营涉及两类关键决策，且必须在高度不确定的环境下实时做出：

1. 救护车选择决策 (Ambulance Selection)：当新的急救呼叫到达时，决定派遣哪辆救护车前往，或者是否将呼叫放入队列等待。
2. 救护车重新分配决策 (Ambulance Reassignment)：当救护车完成当前任务（如送医、清洁）并变为空闲时，决定将其派往队列中的下一个急救任务，还是派往某个救护车站点进行待命（Staging）。

挑战与复杂性：

• 不确定性：未来的急救呼叫位置、类型、到达时间以及行驶时间、现场服务时间等均具有随机性。
• 权衡 (Trade-offs)：需要在当前任务的响应时间与未来任务的可用性之间进行权衡。例如，派遣一辆高级救护车处理当前低优先级任务，可能导致未来高优先级任务缺乏合适的资源。
• 多维属性：
  • 急救类型：不仅区分优先级（高/中/低），还区分具体的医疗需求（如心脏骤停、中风等），不同需求对响应时间和救护车/医护人员能力（如基础生命支持 BLS vs 高级生命支持 ALS）的要求不同。
  • 车队能力：救护车和医护人员具备不同的资质和技能。
  • 任务流程：救护车完成任务后可能需要送医、清洁（现场或清洁站）或返回站点，不同流程影响其再次可用时间。
• 队列管理：当没有可用救护车时，急救请求需要排队。决策不仅涉及派车，还涉及决定将空闲车辆派往队列中的哪个任务，或者是否暂时不派车（让车辆去更需要的区域待命）。

2. 方法论 (Methodology)

作者提出了一种基于两阶段随机规划 (Two-Stage Stochastic Programming) 框架的滚动时域 (Rollout) 策略，并结合了四种新的启发式算法。

2.1 滚动时域框架 (Rollout Approach)

• 机制：每当需要做出决策（新呼叫到达或救护车完成任务）时，求解一个简化的两阶段随机规划问题。
• 过程：
  1. 第一阶段：在当前状态下，枚举所有可行的即时决策 $x_0$。
  2. 第二阶段：对于每个决策 $x_0$，利用生成的随机场景（模拟未来的呼叫和行驶时间），使用一个基础策略 (Rollout Policy, $H$) 来估算未来的总成本。
  3. 优化：选择使得“即时成本 + 期望未来成本”最小的决策。
• 优势：相比直接求解大规模多阶段随机规划（计算量过大），滚动时域方法利用启发式算法快速估算未来成本，既考虑了未来影响，又保证了实时性。

2.2 提出的四种新启发式算法 (用于救护车选择)

这些算法作为滚动时域中的基础策略 $H$，或直接用于决策：

1. 最佳短视启发式 (Best Myopic, BM)：
   • 最小化当前分配的即时成本（响应时间惩罚 + 能力匹配成本）。
   • 考虑了救护车当前的状态（在站、在途、服务中）和未来的可用性。
   • 在多个最优解中，优先选择能力“较低”的救护车（如用 BLS 而非 ALS），以保留高级资源给更紧急的任务。
2. 非短视启发式 (NonMyopic, NM)：
   • 在 BM 的基础上，不仅考虑当前呼叫，还考虑在救护车完成当前任务前可能到达的未来呼叫。
   • 通过评估将救护车分配给未来呼叫的“最小分配成本”，判断是否应该将当前救护车保留给更“昂贵”的未来任务，从而避免短视决策。
3. 贪婪启发式 1 (GHP1)：
   • 引入队列机制。当没有可用救护车时，呼叫进入队列。
   • 按惩罚后的等待时间（基于呼叫类型和等待时长）对队列排序，优先处理等待时间最长或优先级最高的呼叫。
4. 贪婪启发式 2 (GHP2)：
   • 同样引入队列机制。
   • 按最小分配成本（即该呼叫在所有可用救护车中的最佳匹配成本）对队列排序。优先处理那些“如果不立即处理，未来成本会急剧上升”的呼叫。

2.3 救护车重新分配策略 (Ambulance Reassignment)

当救护车空闲且队列为空时，决定其去向：

• 家庭站点规则 (HSR)：返回预设的家庭站点。
• 最近站点规则 (CSR)：前往最近的站点。
• 最佳站点规则 (BSR)（新提出）：基于前瞻性 (Lookahead) 分析。计算未来一段时间内各站点覆盖特定类型急救需求的预期缺口（Deficit），将空闲救护车派往缺口最大的站点。

3. 主要贡献 (Key Contributions)

1. 综合决策框架：不同于以往文献仅关注救护车选择或假设无队列/固定回家站点，本文同时优化了选择和重新分配决策，并显式处理了急救队列。
2. 细粒度的需求与能力建模：
   • 超越了简单的优先级分级，引入了具体的急救类型（如 MPDS 系统分类）。
   • 考虑了救护车类型（BLS/ALS/中风单元等）和医护人员技能的匹配度，而不仅仅是响应时间。
3. 高效的滚动时域策略：提出了一套计算速度极快（秒级）的启发式算法，能够嵌入滚动时域框架中，实现了在实时约束下对未来的有效预测和权衡。
4. 重新分配策略创新：提出了基于需求预测的“最佳站点规则 (BSR)"，优于传统的返回家庭站点或最近站点策略。
5. 开源与可视化：提供了 C++ 和 Matlab 代码，并建立了可视化网站，展示了里约热内卢 EMS 的真实数据模拟。

4. 实验结果 (Numerical Results)

实验基于巴西里约热内卢 EMS 的真实数据（2016-2018 年），并混合了人工数据以测试极端情况。

• 对比基准：与文献中 7 种现有启发式算法（如 Andersson & Värbrand, Lee, Mayorga 等）及“最近可用救护车 (CA)"规则进行了对比。
• 性能指标：分配成本（加权响应时间 + 能力不匹配惩罚）和响应时间。
• 主要发现：
  1. 算法优越性：本文提出的四种启发式算法（BM, NM, GHP1, GHP2）在分配成本和响应时间上均显著优于文献中的其他算法。
  2. 滚动时域的效果：将上述启发式算法作为滚动时域的基础策略（Rollout Policy）使用时，性能进一步提升，优于直接使用启发式算法做决策。
  3. 计算效率：所有决策均在几秒内完成，满足实时管理需求。
  4. 车队规模影响：随着救护车数量增加，所有算法性能提升，但本文算法始终保持领先。
  5. 重新分配策略：在特定场景下（如区域需求波动大时），最佳站点规则 (BSR) 的表现显著优于家庭站点规则 (HSR)，响应时间可降低约 50%。
  6. 随机性影响：在考虑行驶时间随机性（对数正态分布）的情况下，结论依然成立。

5. 意义与结论 (Significance and Conclusion)

• 理论意义：证明了在复杂的随机动态环境中，结合滚动时域框架和精心设计的启发式算法，可以有效解决多阶段随机优化问题，避免了直接求解大规模整数规划的计算不可行性。
• 实践意义：
  • 为 EMS 管理者提供了更科学的调度工具，能够根据实时交通、呼叫类型和车队能力动态调整策略。
  • 通过优化重新分配策略（BSR），提高了救护车在空间上的分布效率，减少了高需求区域的等待时间。
  • 开源工具和可视化平台有助于推广和应用这些方法。
• 未来工作：计划进一步扩展模型以考虑救护车的容量限制（如一次任务可运送的患者数量或设备限制）。

总结：该论文提出了一套完整、高效且实用的救护车车队动态调度解决方案，通过引入对急救类型、车队能力及未来不确定性的精细化建模，显著提升了急救服务的响应速度和资源利用效率。