从数学建模到工程实践：动态车辆路径问题在医疗转运调度中的应用

1. 项目概述：从一道赛题看医疗流程优化的现实挑战

最近在准备数学建模竞赛的指导材料，正好看到“2025华中杯数学建模竞赛D题：患者院内转运”这个题目，觉得特别有意思，也很有现实意义。这道题把目光聚焦在了医院内部一个看似平常、实则充满复杂性的环节——患者转运。对于非医疗行业的朋友来说，可能觉得“不就是把病人从一个地方推到另一个地方吗？”，但真正深入进去，你会发现这里面交织着资源调度、路径规划、风险控制和效率提升等多个维度的难题，完全是一个经典的运筹学与系统优化问题在真实医疗场景下的绝佳映射。

这道题的核心，就是要求我们建立一个数学模型，来优化医院内患者的转运流程。想象一下，一家大型综合医院，每天有数百名患者需要在门诊、急诊、病房、手术室、影像科（如CT、MRI）、检验科等不同功能单元之间移动。这些转运请求是随机、动态到达的，而执行转运任务的资源（如转运床、平车、专业的转运人员）是有限的。我们的目标，就是在满足患者安全、医疗优先级等硬性约束的前提下，科学地调度这些转运任务和资源，使得整体效率最高——可能是平均等待时间最短，也可能是所有任务完成的总时间最少，或者是资源利用率最均衡。

这绝不是一个纸上谈兵的数学游戏。在实际医院管理中，低效的转运系统会导致一系列连锁反应：手术室因为病人迟迟未到而空置，造成昂贵的医疗资源浪费；急诊患者因为等待检查而延误了黄金救治时间；住院患者因不必要的等待而延长了住院周期，增加了医疗成本和感染风险。因此，优化转运流程，本质上是在优化医疗资源的配置效率，提升医院的整体运营水平和服务质量，最终惠及每一位患者。接下来，我就结合自己多年在优化算法和数据分析方面的经验，为大家拆解这道题的解题思路、核心模型构建以及一些实操中容易踩的坑。

2. 问题拆解与核心需求解析

面对这样一个开放性的建模问题，第一步也是最关键的一步，就是把模糊的现实问题转化为清晰的数学问题。我们不能一上来就想着套用某个现成的算法，而是要先理解“院内转运”这个系统到底在发生什么。

2.1 系统要素识别：谁在动？用什么动？去哪动？

首先，我们需要抽象出系统中的几个核心实体：

1. 转运任务（Jobs）：每一个需要转运的患者请求就是一个任务。每个任务i至少包含以下属性：

   • 出发地（O_i）：如3楼内科病房302床。
   • 目的地（D_i）：如1楼放射科CT室2号机房。
   • 就绪时间（r_i）：医嘱下达、转运申请提交的时间。任务在此时间之后才能被处理。
   • 处理时间（p_i）：即转运任务的实际执行时间。这通常不是简单的两点间直线距离除以速度，而是路径时间。它取决于出发地与目的地之间的实际走廊、电梯路径长度，以及电梯等待时间、走廊拥堵情况等。p_i可以进一步拆分为：从资源当前位置到任务出发地的“空驶接驳时间”、从出发地到目的地的“负载行驶时间”、以及在两端的“上下患者操作时间”。
   • 优先级（w_i）：并非所有患者都一样。急诊、危重、手术患者的转运通常具有更高优先级。在模型中，这可以体现为在目标函数中赋予更高的权重，或者在约束中设置最晚开始时间。

2. 转运资源（Resources/Agents）：执行转运任务的主体，通常是转运床/平车及其配备的一名或多名转运员。资源k的属性包括：

   • 初始位置：在调度开始时，每辆转运车所在的位置。
   • 状态：空闲、正在执行任务（并附带其当前任务进度和位置）、交接中。
   • 能力：是否适用于特殊患者（如带呼吸机的重症患者需要特定转运设备）。

3. 医院环境地图（Map/Graph）：这是连接所有任务和资源的物理基础。我们需要将医院楼层平面图抽象为一个加权图G=(V, E)。

   • 节点（V）：代表关键位置点，如每个病房的门口、每个检查室门口、电梯口、楼梯口、护士站等。
   • 边（E）：连接两个节点的路径，如走廊。每条边有一个权重d(e)，代表通过该路径所需的时间（或距离）。
   • 特殊边：电梯或楼梯连接的楼层间路径，其权重（等待+运行时间）通常远大于同层走廊移动。

2.2 核心优化目标与约束分析

在明确了系统要素后，我们需要定义“好”的标准是什么，以及必须遵守的规则。

优化目标（Objective Function）：题目通常会要求最小化一个或多个指标。常见的有：

• 最小化总完成时间（Makespan）：所有转运任务完成时刻的最大值。这侧重于整体流程的吞吐速度。
• 最小化总流程时间（Total Flow Time）：所有任务的“完成时间 - 就绪时间”之和。这更关注平均等待时间，提升患者体验。
• 最小化总加权延迟（Total Weighted Tardiness）：每个任务都有一个期望完成时间（Due Date），最小化超出这个时间的加权和。这能更好地处理优先级。
• 最大化资源利用率：让转运资源尽可能少地空闲。 在实际建模中，我们可能需要结合多个目标，例如“在保证高优先级任务及时完成的前提下，最小化平均等待时间”。

硬性约束（Hard Constraints）：这些是模型必须满足的条件，否则方案不可行。

1. 资源能力约束：一个资源在同一时间只能执行一个任务。
2. 任务不可分割约束：一个任务必须由一个资源一次性完成，不能中途换车（除非模拟特殊情况）。
3. 路径时间约束：任务执行时间必须包含真实的路径行驶时间。
4. 就绪时间约束：任务不能在就绪时间之前开始。
5. 医疗安全与优先级约束：可以体现为“某类任务必须在其就绪后X分钟内开始”。

柔性约束与惩罚（Soft Constraints）：我们希望尽可能满足，但如果不满足可以接受一定惩罚的规则。例如，我们希望资源在完成一个任务后，不要空驶太远去接下一个任务，这可以通过在目标函数中增加空驶成本来实现。

注意：很多新手团队容易犯的错误是，一上来就试图建立一个包含所有细节的“完美”模型，结果模型过于复杂无法求解。正确的思路是先建立核心模型，再逐步增加细节。例如，第一版模型可以假设路径时间是固定的、已知的，忽略电梯拥堵；第二版再引入基于图的动态路径时间。

3. 模型构建：从动态车辆路径问题到优化算法选择

将上述要素和约束整合起来，我们发现“患者院内转运调度”问题本质上是一个“带时间窗、多出发地、动态到达的车辆路径问题（Dynamic Vehicle Routing Problem with Time Windows, DVRPTW）”的变体。这里的“车辆”是转运资源，“客户点”是转运任务（任务有接患者和送患者两个节点，可视为一个“请求”），“时间窗”由医疗优先级和就绪时间隐含定义。

3.1 数学模型框架（以整数规划为例）

我们可以尝试建立一个混合整数线性规划（MILP）模型。定义决策变量：

• x_{ijk}：二进制变量，若资源k从位置i（可能是任务结束点或资源初始位）前往任务j的出发地并执行该任务，则为1。
• s_i：任务i的开始时间。
• c_i：任务i的完成时间。

目标函数：例如，最小化总加权完成时间Min Σ w_i * c_i。

约束条件包括：

1. 每个任务必须被恰好一个资源执行一次：Σ_k Σ_i x_{ijk} = 1(对于所有任务j)。
2. 资源流平衡：资源k在执行一个任务后，必须去执行另一个任务或回到“车库”（虚拟终点）。
3. 时间连续性约束：如果资源k在执行任务i后执行任务j，那么任务j的开始时间必须晚于任务i的完成时间加上资源从i的目的地移动到j的出发地的时间。即s_j >= c_i + travel_time(D_i, O_j) - M*(1 - x_{ijk})，其中M是一个很大的数。
4. 就绪时间约束：s_i >= r_i。

这个MILP模型概念清晰，但对于大规模、动态的现实问题（任务数上百），直接求解会非常慢，甚至无法在竞赛时间内得到可行解。因此，它更适合作为问题形式化的描述和求解小规模实例的基准。

3.2 核心挑战与算法策略选择

竞赛中更实用的方法是设计启发式或元启发式算法。我们需要根据问题的动态性、实时性要求来选择策略。

• 静态调度 vs. 动态调度：

  • 静态：假设所有任务信息（r_i, O_i, D_i）在调度开始时全部已知。这适用于做全天计划或离线分析。我们可以使用遗传算法（GA）、模拟退火（SA）、禁忌搜索（TS）等元启发式算法来求解一个较优的全局方案。
  • 动态：任务随时间陆续到达，调度系统需要实时做出决策。这是更贴近现实的场景。常用滚动时域优化（Rolling Horizon）或事件驱动调度。

• 滚动时域优化框架：这是处理动态VRP非常有效的范式。

  1. 时域划分：将整个运营时间（如8:00-18:00）划分为多个时间窗口（如每15分钟一个窗口）。
  2. 信息更新：在每个窗口开始时，收集所有“已到达但未开始”以及“预计在本窗口内到达”的任务信息。
  3. 静态子问题求解：将当前已知的任务集合，结合资源当前位置和状态，形成一个静态的VRPTW子问题。
  4. 执行与滚动：求解这个子问题，得到资源在当前窗口内的行动指令（例如：资源1去接任务A，然后送其去CT室）。只执行该窗口时间内的指令（或执行到下一个决策点）。时间推进到下一个窗口，重复步骤2-4。

• 调度规则（Dispatching Rules）：在动态环境下，当需要快速做出“下一个任务派给谁”的决策时，简单的启发式规则往往非常有效，可以作为复杂算法的补充或基准。

  • 最短处理时间优先（SPT）：选择预计转运时间最短的任务。能快速消化小任务，提高吞吐量，但可能让大任务饿死。
  • 最早截止时间优先（EDD）：选择医疗要求最紧急（时间窗最紧）的任务。保障高危患者。
  • 最短旅行时间优先：选择距离空闲资源最近（空驶时间最短）的任务。提高资源利用率。
  • 复合规则：例如，定义一个综合评分Score = α * (优先级权重) - β * (空驶时间) + γ * (等待时间)，每次选择分数最高的任务。α, β, γ 是需要调参的权重。

实操心得：在竞赛中，我推荐采用“滚动时域优化 + 元启发式求解静态子问题 + 紧急任务优先规则”的混合策略。即，在每个决策点，用遗传算法等求解一个当前最优的静态计划，但在算法运行间隙，如果有新的极高优先级任务突然到达，则用一个简单的优先规则立即指派给最近资源，打断原有计划，再重新规划。这样兼顾了全局优化和实时响应。

4. 关键环节实现：路径规划与仿真评估

模型和算法给出了调度指令“派资源A去接任务B”，但“怎么去”和“去了之后效果如何”还需要两个关键模块支撑：路径规划模块和离散事件仿真模块。

4.1 精细化路径时间估算

“转运时间p_i”是模型的核心输入，其准确性直接决定调度方案的真实有效性。不能简单用直线距离估算。

1. 构建医院路径图：

   • 根据医院平面图，将走廊交叉口、房间门口、电梯厅等设为节点。
   • 连接相邻节点形成边，并为每条边赋予一个基础通行时间（长度/步行速度，通常步行速度按60-80米/分钟估算）。
   • 重点建模电梯：将每个楼层的电梯口设为节点，电梯本身视为一种特殊的“边”或“资源”。电梯的运行时间包括：呼叫等待时间、运行时间（与跨越楼层数相关）、开关门及人员进出时间。可以简化为一个固定周期（如平均90秒）加上每层额外的运行时间（如10秒/层）。

2. 动态路径时间：

   • 基础最短路径：使用Dijkstra或A*算法，计算图中任意两点（O_i, D_i）之间的最短时间路径。
   • 拥堵效应：在高峰期，主要走廊和电梯可能出现拥堵。一个简化的建模方法是，对某些关键边（如通往影像科的主走廊）和电梯，根据当前时间段（如9:00-11:00）设置一个拥堵乘子（如1.5），将基础通行时间乘以该乘子。
   • 更复杂的模拟可以引入基于智能体的仿真，让每个转运资源在图上移动，实时占用和释放路径资源，但这在数模竞赛中计算负担较重。

4.2 基于离散事件仿真的方案评估

我们设计出的调度算法效果如何？不能只靠理论分析，必须通过仿真来验证和比较。离散事件仿真（DES）是模拟此类排队系统的标准工具。

1. 定义事件：整个系统的演进由一系列事件驱动。核心事件包括：

   • TaskArrival：新转运任务到达（服从某种随机分布，如泊松过程）。
   • ResourceBecomesIdle：资源完成当前任务，变为空闲状态。
   • StartTask：调度器指派一个任务给一个空闲资源，任务开始。
   • FinishLeg：资源完成一段移动（如空驶到患者处，或负载行驶到目的地）。

2. 仿真流程：

   • 维护一个未来事件列表（FEL），按事件发生时间排序。
   • 初始化：设置资源初始状态，生成第一批任务到达事件。
   • 主循环：取出FEL中时间最早的事件，处理它，更新系统状态（如资源位置、任务状态），并可能触发新事件加入FEL（如StartTask后会触发一个预计的FinishLeg事件）。
   • 在ResourceBecomesIdle事件中，调用我们的调度算法，决定该资源下一个执行哪个任务（或等待）。
   • 持续运行，直到模拟时间结束或所有任务完成。

3. 输出性能指标：

   • 所有任务的平均等待时间、中位数等待时间。
   • 任务完成时间的分布（特别是高优先级任务）。
   • 资源利用率（忙碌时间/总时间）。
   • 系统吞吐量（单位时间完成的任务数）。
   • 绘制甘特图（Gantt Chart）展示资源和任务的时间线，直观发现瓶颈。

注意事项：仿真必须运行足够多的次数（例如，用不同的随机数种子生成多组任务到达序列），计算性能指标的均值和置信区间，以消除随机性的影响，保证评估结果的统计可靠性。这是评判算法鲁棒性的关键。

5. 模型拓展与深度思考方向

如果只完成基础调度，可能只能拿到及格分。要想在竞赛中脱颖而出，必须体现对问题更深层次的理解和建模能力。以下是一些有价值的拓展方向：

5.1 多目标优化与帕累托前沿

现实中的医院管理者可能面临多个相互冲突的目标：既想减少患者等待时间（提高服务质量），又想降低运营成本（减少转运人员或设备）。这就构成了一个多目标优化问题。

• 目标：最小化平均患者等待时间（F1），最小化使用的转运资源数量（F2）。
• 方法：可以采用NSGA-II（非支配排序遗传算法）这类多目标进化算法。
• 输出：算法会找出一系列帕累托最优解。这些解的特点是：在其中一个目标上无法变得更优，除非让另一个目标变得更差。将这些解绘制在二维图上，就形成了帕累托前沿。
• 决策支持：医院管理者可以根据当前的运营重点（如疫情期间更关注效率，平时更关注成本），从前沿上选择一个合适的折中点。在论文中展示帕累托前沿图，能极大提升模型的实用性和理论深度。

5.2 不确定性建模与鲁棒优化

之前的模型大多假设参数（如转运时间、任务到达时间）是确定的。但现实充满不确定性：某段路临时清洁导致绕行、电梯故障、患者准备未就绪导致交接延迟。

• 随机规划：将不确定参数（如任务转运时间p_i）视为随机变量，服从某种概率分布（如正态分布，均值为基础时间，标准差为10%）。目标函数变为最小化期望总完成时间。求解时可能需要用到场景法或样本平均近似。
• 鲁棒优化：假设不确定参数在一个有界集合内变化（如p_i在[p_i_low, p_i_high]之间），目标是找到一个调度方案，使得在最坏情况下的性能最好（最小化最大遗憾）。这种方法更保守，适用于对风险高度敏感的医疗场景。
• 实时重调度：当不确定性事件发生时（如资源故障），触发重调度机制。这要求算法具备快速响应的能力。

5.3 数据驱动的参数校准与预测

一个高级的亮点是引入数据驱动思想。题目可能提供历史转运数据，或者我们可以假设存在这样的数据。

• 预测任务到达：利用历史数据，训练时间序列模型（如ARIMA、LSTM）来预测未来不同时段的任务到达率，从而让滚动时域优化能更好地预知未来负荷。
• 学习路径时间：通过历史GPS或RFID轨迹数据，学习不同时段、不同路径的实际通行时间分布，取代简单的手工估算，使模型更贴近现实。
• 优化算法参数调优：我们算法中的权重参数（如α, β, γ）如何设置最优？可以使用强化学习或贝叶斯优化，以仿真系统的最终性能指标为反馈，自动搜索最佳参数组合。

6. 论文撰写与结果呈现要点

数学建模竞赛最终比拼的是论文。模型再精巧，说不清楚也白搭。

1. 问题重述与分析：不要照抄题目，要用自己的语言提炼核心矛盾、约束和目标，并画出系统示意图（任务流、资源流）。
2. 模型假设：清晰列出所有假设，并说明其合理性。例如：“假设同一楼层的转运速度恒定”、“假设电梯等待时间服从均匀分布U[30s, 150s]”。这是建模工作的起点。
3. 符号说明：在模型建立前，用三线表列出所有使用的主要变量、符号及其含义。
4. 模型建立：分步骤、分层级地阐述。先给出整体框架（如滚动时域），再分别描述路径规划子模型、调度优化子模型、仿真评估子模型。关键公式必须给出，并解释其物理意义。
5. 算法设计：用流程图或伪代码说明算法的步骤。特别是遗传算法，要说明编码方式（如何用一条染色体表示一个调度方案）、交叉变异操作、适应度函数如何定义。
6. 仿真实验与结果分析：这是论文的重头戏。
   • 参数设置：详细说明所有实验参数，如医院规模（节点数）、资源数量、任务生成规则（到达率、时空分布）。
   • 基准对比：将自己的算法与几种经典的调度规则（如FCFS先到先服务、SPT、EDD）进行对比。使用表格和图表展示各项性能指标（平均等待时间、资源利用率等）的对比结果。
   • 敏感性分析：改变关键参数（如资源数量、任务到达强度），观察系统性能的变化趋势，并分析原因。例如，绘制“资源数量 vs. 平均等待时间”的曲线图，找到性能拐点，为医院资源配置提供建议。
   • 可视化：善用图表。除了折线图、柱状图，还可以绘制资源移动的热力图（发现拥堵区域）、甘特图、调度时序图等，让结果一目了然。
7. 模型评价与推广：客观评价自己模型的优点（如综合考虑了动态性和优先级）、缺点（如未考虑电梯容量限制），并提出可能的改进方向。说明模型稍加修改后，也可用于物流仓库的拣货员调度、机场的地勤服务车辆调度等类似场景。

最后想说的是，这道题的魅力在于它扎根于真实世界。解决它，不仅需要数学和编程能力，更需要一种系统思维和将复杂现实抽象化的能力。在构建模型时，要时刻问自己：我这个假设是否合理？这个简化会不会丢失关键信息？我的方案真的能让医院的转运护士用起来吗？多从实际应用的角度去思考，你的模型才会更有生命力，你的论文也才能打动评委。在实际编程实现时，不妨先用小规模数据（比如5个资源，20个任务）跑通整个流程，确保仿真逻辑正确无误，再逐步扩展到竞赛要求的规模，这样可以避免在最后阶段被一些隐蔽的bug搞得焦头烂额。