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

1. 项目概述从一道赛题看医疗流程优化的现实挑战最近在准备数学建模竞赛的指导材料正好看到“2025华中杯数学建模竞赛D题患者院内转运”这个题目觉得特别有意思也很有现实意义。这道题把目光聚焦在了医院内部一个看似平常、实则充满复杂性的环节——患者转运。对于非医疗行业的朋友来说可能觉得“不就是把病人从一个地方推到另一个地方吗”但真正深入进去你会发现这里面交织着资源调度、路径规划、风险控制和效率提升等多个维度的难题完全是一个经典的运筹学与系统优化问题在真实医疗场景下的绝佳映射。这道题的核心就是要求我们建立一个数学模型来优化医院内患者的转运流程。想象一下一家大型综合医院每天有数百名患者需要在门诊、急诊、病房、手术室、影像科如CT、MRI、检验科等不同功能单元之间移动。这些转运请求是随机、动态到达的而执行转运任务的资源如转运床、平车、专业的转运人员是有限的。我们的目标就是在满足患者安全、医疗优先级等硬性约束的前提下科学地调度这些转运任务和资源使得整体效率最高——可能是平均等待时间最短也可能是所有任务完成的总时间最少或者是资源利用率最均衡。这绝不是一个纸上谈兵的数学游戏。在实际医院管理中低效的转运系统会导致一系列连锁反应手术室因为病人迟迟未到而空置造成昂贵的医疗资源浪费急诊患者因为等待检查而延误了黄金救治时间住院患者因不必要的等待而延长了住院周期增加了医疗成本和感染风险。因此优化转运流程本质上是在优化医疗资源的配置效率提升医院的整体运营水平和服务质量最终惠及每一位患者。接下来我就结合自己多年在优化算法和数据分析方面的经验为大家拆解这道题的解题思路、核心模型构建以及一些实操中容易踩的坑。2. 问题拆解与核心需求解析面对这样一个开放性的建模问题第一步也是最关键的一步就是把模糊的现实问题转化为清晰的数学问题。我们不能一上来就想着套用某个现成的算法而是要先理解“院内转运”这个系统到底在发生什么。2.1 系统要素识别谁在动用什么动去哪动首先我们需要抽象出系统中的几个核心实体转运任务Jobs每一个需要转运的患者请求就是一个任务。每个任务i至少包含以下属性出发地O_i如3楼内科病房302床。目的地D_i如1楼放射科CT室2号机房。就绪时间r_i医嘱下达、转运申请提交的时间。任务在此时间之后才能被处理。处理时间p_i即转运任务的实际执行时间。这通常不是简单的两点间直线距离除以速度而是路径时间。它取决于出发地与目的地之间的实际走廊、电梯路径长度以及电梯等待时间、走廊拥堵情况等。p_i可以进一步拆分为从资源当前位置到任务出发地的“空驶接驳时间”、从出发地到目的地的“负载行驶时间”、以及在两端的“上下患者操作时间”。优先级w_i并非所有患者都一样。急诊、危重、手术患者的转运通常具有更高优先级。在模型中这可以体现为在目标函数中赋予更高的权重或者在约束中设置最晚开始时间。转运资源Resources/Agents执行转运任务的主体通常是转运床/平车及其配备的一名或多名转运员。资源k的属性包括初始位置在调度开始时每辆转运车所在的位置。状态空闲、正在执行任务并附带其当前任务进度和位置、交接中。能力是否适用于特殊患者如带呼吸机的重症患者需要特定转运设备。医院环境地图Map/Graph这是连接所有任务和资源的物理基础。我们需要将医院楼层平面图抽象为一个加权图G(V, E)。节点V代表关键位置点如每个病房的门口、每个检查室门口、电梯口、楼梯口、护士站等。边E连接两个节点的路径如走廊。每条边有一个权重d(e)代表通过该路径所需的时间或距离。特殊边电梯或楼梯连接的楼层间路径其权重等待运行时间通常远大于同层走廊移动。2.2 核心优化目标与约束分析在明确了系统要素后我们需要定义“好”的标准是什么以及必须遵守的规则。优化目标Objective Function题目通常会要求最小化一个或多个指标。常见的有最小化总完成时间Makespan所有转运任务完成时刻的最大值。这侧重于整体流程的吞吐速度。最小化总流程时间Total Flow Time所有任务的“完成时间 - 就绪时间”之和。这更关注平均等待时间提升患者体验。最小化总加权延迟Total Weighted Tardiness每个任务都有一个期望完成时间Due Date最小化超出这个时间的加权和。这能更好地处理优先级。最大化资源利用率让转运资源尽可能少地空闲。 在实际建模中我们可能需要结合多个目标例如“在保证高优先级任务及时完成的前提下最小化平均等待时间”。硬性约束Hard Constraints这些是模型必须满足的条件否则方案不可行。资源能力约束一个资源在同一时间只能执行一个任务。任务不可分割约束一个任务必须由一个资源一次性完成不能中途换车除非模拟特殊情况。路径时间约束任务执行时间必须包含真实的路径行驶时间。就绪时间约束任务不能在就绪时间之前开始。医疗安全与优先级约束可以体现为“某类任务必须在其就绪后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。约束条件包括每个任务必须被恰好一个资源执行一次Σ_k Σ_i x_{ijk} 1(对于所有任务j)。资源流平衡资源k在执行一个任务后必须去执行另一个任务或回到“车库”虚拟终点。时间连续性约束如果资源k在执行任务i后执行任务j那么任务j的开始时间必须晚于任务i的完成时间加上资源从i的目的地移动到j的出发地的时间。即s_j c_i travel_time(D_i, O_j) - M*(1 - x_{ijk})其中M是一个很大的数。就绪时间约束s_i r_i。这个MILP模型概念清晰但对于大规模、动态的现实问题任务数上百直接求解会非常慢甚至无法在竞赛时间内得到可行解。因此它更适合作为问题形式化的描述和求解小规模实例的基准。3.2 核心挑战与算法策略选择竞赛中更实用的方法是设计启发式或元启发式算法。我们需要根据问题的动态性、实时性要求来选择策略。静态调度 vs. 动态调度静态假设所有任务信息r_i, O_i, D_i在调度开始时全部已知。这适用于做全天计划或离线分析。我们可以使用遗传算法GA、模拟退火SA、禁忌搜索TS等元启发式算法来求解一个较优的全局方案。动态任务随时间陆续到达调度系统需要实时做出决策。这是更贴近现实的场景。常用滚动时域优化Rolling Horizon或事件驱动调度。滚动时域优化框架这是处理动态VRP非常有效的范式。时域划分将整个运营时间如8:00-18:00划分为多个时间窗口如每15分钟一个窗口。信息更新在每个窗口开始时收集所有“已到达但未开始”以及“预计在本窗口内到达”的任务信息。静态子问题求解将当前已知的任务集合结合资源当前位置和状态形成一个静态的VRPTW子问题。执行与滚动求解这个子问题得到资源在当前窗口内的行动指令例如资源1去接任务A然后送其去CT室。只执行该窗口时间内的指令或执行到下一个决策点。时间推进到下一个窗口重复步骤2-4。调度规则Dispatching Rules在动态环境下当需要快速做出“下一个任务派给谁”的决策时简单的启发式规则往往非常有效可以作为复杂算法的补充或基准。最短处理时间优先SPT选择预计转运时间最短的任务。能快速消化小任务提高吞吐量但可能让大任务饿死。最早截止时间优先EDD选择医疗要求最紧急时间窗最紧的任务。保障高危患者。最短旅行时间优先选择距离空闲资源最近空驶时间最短的任务。提高资源利用率。复合规则例如定义一个综合评分Score α * (优先级权重) - β * (空驶时间) γ * (等待时间)每次选择分数最高的任务。α, β, γ 是需要调参的权重。实操心得在竞赛中我推荐采用“滚动时域优化 元启发式求解静态子问题 紧急任务优先规则”的混合策略。即在每个决策点用遗传算法等求解一个当前最优的静态计划但在算法运行间隙如果有新的极高优先级任务突然到达则用一个简单的优先规则立即指派给最近资源打断原有计划再重新规划。这样兼顾了全局优化和实时响应。4. 关键环节实现路径规划与仿真评估模型和算法给出了调度指令“派资源A去接任务B”但“怎么去”和“去了之后效果如何”还需要两个关键模块支撑路径规划模块和离散事件仿真模块。4.1 精细化路径时间估算“转运时间p_i”是模型的核心输入其准确性直接决定调度方案的真实有效性。不能简单用直线距离估算。构建医院路径图根据医院平面图将走廊交叉口、房间门口、电梯厅等设为节点。连接相邻节点形成边并为每条边赋予一个基础通行时间长度/步行速度通常步行速度按60-80米/分钟估算。重点建模电梯将每个楼层的电梯口设为节点电梯本身视为一种特殊的“边”或“资源”。电梯的运行时间包括呼叫等待时间、运行时间与跨越楼层数相关、开关门及人员进出时间。可以简化为一个固定周期如平均90秒加上每层额外的运行时间如10秒/层。动态路径时间基础最短路径使用Dijkstra或A*算法计算图中任意两点O_i, D_i之间的最短时间路径。拥堵效应在高峰期主要走廊和电梯可能出现拥堵。一个简化的建模方法是对某些关键边如通往影像科的主走廊和电梯根据当前时间段如9:00-11:00设置一个拥堵乘子如1.5将基础通行时间乘以该乘子。更复杂的模拟可以引入基于智能体的仿真让每个转运资源在图上移动实时占用和释放路径资源但这在数模竞赛中计算负担较重。4.2 基于离散事件仿真的方案评估我们设计出的调度算法效果如何不能只靠理论分析必须通过仿真来验证和比较。离散事件仿真DES是模拟此类排队系统的标准工具。定义事件整个系统的演进由一系列事件驱动。核心事件包括TaskArrival新转运任务到达服从某种随机分布如泊松过程。ResourceBecomesIdle资源完成当前任务变为空闲状态。StartTask调度器指派一个任务给一个空闲资源任务开始。FinishLeg资源完成一段移动如空驶到患者处或负载行驶到目的地。仿真流程维护一个未来事件列表FEL按事件发生时间排序。初始化设置资源初始状态生成第一批任务到达事件。主循环取出FEL中时间最早的事件处理它更新系统状态如资源位置、任务状态并可能触发新事件加入FEL如StartTask后会触发一个预计的FinishLeg事件。在ResourceBecomesIdle事件中调用我们的调度算法决定该资源下一个执行哪个任务或等待。持续运行直到模拟时间结束或所有任务完成。输出性能指标所有任务的平均等待时间、中位数等待时间。任务完成时间的分布特别是高优先级任务。资源利用率忙碌时间/总时间。系统吞吐量单位时间完成的任务数。绘制甘特图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. 论文撰写与结果呈现要点数学建模竞赛最终比拼的是论文。模型再精巧说不清楚也白搭。问题重述与分析不要照抄题目要用自己的语言提炼核心矛盾、约束和目标并画出系统示意图任务流、资源流。模型假设清晰列出所有假设并说明其合理性。例如“假设同一楼层的转运速度恒定”、“假设电梯等待时间服从均匀分布U[30s, 150s]”。这是建模工作的起点。符号说明在模型建立前用三线表列出所有使用的主要变量、符号及其含义。模型建立分步骤、分层级地阐述。先给出整体框架如滚动时域再分别描述路径规划子模型、调度优化子模型、仿真评估子模型。关键公式必须给出并解释其物理意义。算法设计用流程图或伪代码说明算法的步骤。特别是遗传算法要说明编码方式如何用一条染色体表示一个调度方案、交叉变异操作、适应度函数如何定义。仿真实验与结果分析这是论文的重头戏。参数设置详细说明所有实验参数如医院规模节点数、资源数量、任务生成规则到达率、时空分布。基准对比将自己的算法与几种经典的调度规则如FCFS先到先服务、SPT、EDD进行对比。使用表格和图表展示各项性能指标平均等待时间、资源利用率等的对比结果。敏感性分析改变关键参数如资源数量、任务到达强度观察系统性能的变化趋势并分析原因。例如绘制“资源数量 vs. 平均等待时间”的曲线图找到性能拐点为医院资源配置提供建议。可视化善用图表。除了折线图、柱状图还可以绘制资源移动的热力图发现拥堵区域、甘特图、调度时序图等让结果一目了然。模型评价与推广客观评价自己模型的优点如综合考虑了动态性和优先级、缺点如未考虑电梯容量限制并提出可能的改进方向。说明模型稍加修改后也可用于物流仓库的拣货员调度、机场的地勤服务车辆调度等类似场景。最后想说的是这道题的魅力在于它扎根于真实世界。解决它不仅需要数学和编程能力更需要一种系统思维和将复杂现实抽象化的能力。在构建模型时要时刻问自己我这个假设是否合理这个简化会不会丢失关键信息我的方案真的能让医院的转运护士用起来吗多从实际应用的角度去思考你的模型才会更有生命力你的论文也才能打动评委。在实际编程实现时不妨先用小规模数据比如5个资源20个任务跑通整个流程确保仿真逻辑正确无误再逐步扩展到竞赛要求的规模这样可以避免在最后阶段被一些隐蔽的bug搞得焦头烂额。