鹿国伟,段德光,陶学强,张泽瑞

(军事科学院系统工程研究院,天津 300161)

1 引言

军队医疗救治系统涉及大量医护人员和各型医疗装备,它们共同作用构成了一个复杂系统,广泛运用于作战行动、自然灾害、传染病救治等突发紧急救援情景[1]。特别是战时伤病员大量集中产生,由于医疗救治系统装备类型和数量有限,经常出现伤员拥挤状况,造成伤员救治不及时,错过最佳处置时间。多类别装备资源和多样化装备数目需求组成的伤员救治排序构成了多资源调度问题,以往关于军队医疗救治系统调度研究较少,且缺乏系统性、整体性[1-2],因此,如何立足现有军队医疗救治系统编配装备进行伤员救治排程,发掘医疗救治系统运用潜力具有重要研究价值。

2 医疗救治系统数学模型

2.1 问题描述

伤员由救护车辆运送至军队医疗救治系统后,根据其伤情主要占用医疗救治系统的检伤分类模块、紧急救治模块、基本检查模块、外科手术模块、重症监护模块和伤员留治模块,总体过程如图1。伤员救治过程是一个对于连续性和协调性要求很高的活动,前一个救治步骤没有完成,都不能进行下一个救治步骤。由于轻伤员对时间敏感性较小,时效性要求不高,对于伤员救治及时率影响不大,且涉及的装备较少,因此为了便于研究,本文以重伤员在医疗救治系统中调度优化为研究目标,并根据装备分类将伤员救治简化为检伤分类、紧急救治、基本检查、外科手术、重症监护等5个阶段,各伤员根据其伤情对应不同的装备选择和处置时间。

图1 伤员在医疗救治系统内流转情况

医疗救治系统中不仅涉及到大量医疗装备资源,而且伤员类型多样性和个体的差异性造成了医疗救治过程和装备占用时间不尽相同。因此,如何对伤员救治进行排程,发挥医疗救治系统装备的最大效能至关重要。军队医疗救治系统调度实质是在现有装备编配基础上对到达系统的各类伤员分配最佳救治顺序和装备资源,是非确定性多项式难题(NP-hard)的组合优化问题。由于上述多类别资源和多样化的资源数目需求组成的伤员救治排序构成了多资源的调度问题,可以将其抽象成多资源约束的柔性作业车间调度模型[3-6]。

2.2 模型对比

医疗救治系统调度与柔性作业车间调度对比见表1,可以看出两者在调度对象、约束和规则等方面具有非常大的相似性,医疗救治系统调度是柔性作业车间调度问题在多重医疗装备资源约束条件下的变形和扩展。医疗救治系统调度问题不仅涉及多类装备资源,而且不同伤员占用各类资源时间不尽相同,同时由于伤员救治的特殊性,相对于车间调度增加了一些实际约束,比如救治时效窗口问题、伤员到达和死亡问题。

表1 医疗救治系统调度与柔性作业车间调度问题对比

2.3 模型构建

医疗救治系统调度问题的数学模型可做如下描述:I为救治伤员集合,M为装备类型集合,J为救治阶段集合,EJ为伤员的核心处置阶段,ET为伤员的最佳处置时间;Sijm表示伤员i在j阶段在装备m上的开始救治时间;Tijm为伤员i在j阶段在装备m上的处置时间(处置时间随伤情变化);在建模过程中对于该调度问题做出如下假设:

1)所有装备、伤员是相互独立的,不会相互影响;

2)救治装备资源数量及状态在调度开始前已知;

3)救治装备不会发生故障,准备时间忽略不计;

4)伤员所需装备和时间在调度前已知,且不会随着排序而发生变化;

5)再调度时,装备是非抢占式的,正被占用装备不受影响。

假设该模型的调度目标是在考虑装备资源类型、数量变化和可用时间的相互约束影响下,确定伤员救治排程以使得伤员救治及时率最大。定义救治及时率为F,即

(1)

(2)

约束条件:

1)装备约束:定义当“伤员i(p)在j(q)阶段在装备m上救治”事件为真时,yijm和ypqm为1,否则为零。同一装备资源在同一时刻只能处理一名伤员,即伤员i在时刻t阶段j时有

∃yijm=ypqm=1,则p=i时,q=j必不成立

(3)

2)处理约束:不同伤员间的处置顺序之间没有先后约束,同一伤员的处置顺序之间有先后约束,即伤员i在阶段j时有

(4)

3)连续性约束:装备在任一阶段被占用时不能中断。

3 改进粒子群算法

3.1 算法整体流程

基于柔性作业车间调度的医疗救治系统调度问题为离散的组合优化问题,目前求解算法主要分为人工智能算法和局部搜索算法等类型[7],这些算法各有优劣,采用单一算法很难实现快速求解目标函数的最优解。本文以粒子群算法(Partical Swarm Optimization,PSO)为基础[4,8-10],融合遗传算法(Genetic Algorithm,GA)和变邻域搜索算法(Variable Neighborhood Search,VNS)[11]思想,PSO具有计算简单和效率高特点,但存在易早熟和陷入局部最优的缺点,而GA具有较强的多样性和群体寻优能力,同时考虑到两种算法都存在局部寻优能力差的缺点,引入VNS,从而提高算法的效率和准确性。

算法流程如图2,首先,设置粒子群大小N、迭代次数gen等相关参数;然后,随机产生N个调度方案初始化粒子群,并计算适应度,记录个体最优粒子pBest和全局最优粒子gBest;其次,在粒子位置迭代更新时,将粒子作为GA的初始种群,通过选择、变异和交叉等方式更新粒子位置,产生性能更优的新一代群体,并计算适应度,更新pBest和gBest;接着,采用VNS算法的插入、交换、倒置等方式进行局部寻优,更新pBest和gBest;最后,判断是否到达最大迭代次,输出最优解和调度方案,并画出甘特图。

图2 算法流程图

3.2 算法原理描述

3.2.1 粒子编码与解码

良好的编码与解码是实现调度优化算法的首要问题。本文中伤员各阶段之间联系紧密,前一阶段对后续阶段的影响较大,借鉴目前柔性作业车间调度中大多数采用基于工件排列的单层实数编码方式,将伤员救治按照顺序排队,即每个粒子编码位为伤员顺序号。如图3,粒子编码为“13231321”,编码出现的次数代表阶段数,即在第1阶段伤员救治排序为“J11J31J21”,在第2阶段伤员救治排序为“J32J12J22”,在第3阶段伤员救治排序为“J33J13”。

图3 粒子编码

3.2.2 粒子初始化与位置更新

相较于经典粒子群优化算法,本文中粒子群变化是离散的[12-15],初始化时首先将粒子进行伤员救治排序的随机赋值;然后,重新定义离散粒子群优化算法的位置更新式(5),模拟当前状态、认知模式以及社会模式三部分对新位置的作用,并用工序顺序链表的更新代替新位置,同样记录pBest和gBest,通过不断迭代产生最优解。

(5)

(6)

(7)

(8)

3.2.3 粒子局部寻优

由于粒子群算法和遗传算法具有记忆和学习能力,信息共享是单向的,粒子只根据个体最优粒子位置信息和全局最优粒子位置信息进行更新,所以粒子收敛速度较快,但是搜索性能不够稳定,容易陷入全局最优解[8,15]。因此根据变邻域搜索算法思想,引入swap交换算子、invert倒置算子、insert插入算子三种邻域算子,对三种算子产生邻域解集合进行评价,扩大局部搜索范围,增强局部搜索能力,将适应度最优的解与历史最优解和个体最优解对比,用较优解覆盖种群中的粒子[11]。

以编码为“13231321”的粒子为例具体说明三种邻域算子:假设swap交换算子是随机选择第2位和第5位两个基因位置进行交换操作,变为“11233321”;假设insert插入算子是随机选取前三位基因插入粒子最后,变为“31321132”;假设invert倒置算子是将粒子基因顺序倒置,变为“12313231”。

3.3 算法再调度策略

由于战场形势的瞬息万变,造成了战时伤员变化的突发性,如伤员达到、死亡或装备故障等。这些动态事件的发生使得既定的初始调度方案无法继续执行,需要根据伤员的救治情况采取合适的再调度策略来确保救治任务的顺利完成。

再调度策略复杂度高,对系统的敏感性和实时性要求高,目前有事件驱动再调度、周期性再调度和基于周期与事件驱动的混合再调度三种类型[16-18]。考虑伤员存在到达、等待、死亡等救治状态变化,本文借鉴性与实际较为符合的基于周期与事件驱动的混合再调度策略,设定触发再调度的条件为伤员到达、死亡,或达到触发周期T。

再调度流程如图4,将伤员分为未占用装备伤员集和占用装备伤员集两种。在调度开始前,所有伤员信息保存在未占用装备伤员集中,根据适应度函数的最优解,形成调度方案。若调度系统在运行过程中达到再调度条件,对未占用装备伤员集立即启动再调度,占用装备伤员集不进行再调度,直到所有伤员完成救治。

图4 算法再调度流程

4 实验与数据分析

4.1 实验设置和参数选择

本文采用Matlab2017实现改进粒子群算法,基于Anylogic8.4.0建模仿真软件从伤员库随机生成伤员和调用再调度算法,模拟伤员通过医疗救治系统时的调度情况。

1)装备设置

由于伤员救治流程涉及到的装备较多,把所有的装备都>纳入研究内容,复杂程度呈指数级增长,因此在前文研究的基础上,选择检伤分类模块、紧急救治模块、基本检查模块、外科手术模块、重症监护模块等作为研究目标装备。其中外科手术是重伤员救治的核心处置措施,比较它的处置是否在最佳处置时间内,从而得到伤员救治及时率。装备编号和数量设置见表2。

表2 各装备编号和数量设置

2)伤员设置

医疗救治系统设置接收两批伤员,第1批为10名伤员;间隔1小时后,到达第2批5名伤员。各伤员救治过程、占用装备和最佳救治时间不尽相同,假设15名伤员的救治装备和时间情况见表3。

表3 15名伤员救治装备和时间分布表

3)参数设置

通过大量阅读分析文献和多次参数试验,考虑到伤员的排程方案空间为伤员数量的全排列组合,将粒子群N设置为50,种群迭代次数gen为1000,局部搜索的迭代次数count为10;交叉概率Pc取值一般在[0.5,1]区间,变异概率Pm一般在[0,0.5]区间,本文经过多次实验测试分别设置为0.9和 0.1;认知系数c1、社会系数c2和惯性权重ω取值均在[0,1]之间,本文经过多次实验测试设置为0.7、0.7和0.3。

4.2 结果对比分析

在以往军队医疗救治系统调度中,伤员排程方案生成主要是按照先到先服务原则,当重伤员量较大时,各类装备资源紧张,这种调度方式存在较大随意性,缺乏从整体视角的伤员调度,不能充分发挥装备效能,从而影响伤员救治及时率。

如图5和图6,对比优化前后的甘特图可以发现,为了提高伤员救治及时率,1-3号重伤员全部被优化放至靠后位置。说明在以最大化救治及时率为目标时,实际上动态调整了伤员的救治优先级,当重伤员较为拥挤时,占用装备时间较长的重伤员会被安排在靠后救治,以保证在最佳救治时间内尽可能多的救治伤员,有利于提高整体救治及时率,符合伤员群体利益。

图5 优化前的甘特图

图6 优化后的甘特图

由于战场形势瞬息万变,不断有伤员到达、死亡或者满足再调度周期。当第二批5名伤员到达时触发再调度,此时,1号、2号、4号、5号、6号、7号和9号等重伤员均占用装备不参与调度,第二批与第一批未占用装备伤员集进行统一再调度,伤员救治排程甘特图如图7。从图中可以看出第一批的3号重伤员中已经错过最佳救治时间,为了不耽误第二批伤员救治,又将其置于整个伤员救治排程的最后。

图7 再调度后的甘特图

5 结论与展望

军队医疗救治系统作为一个复杂系统,各装备模块之间相互联系、相互作用,对其调度优化研究具有重要意义。本文基于柔性作业车间调度模型,构建起伤员排程和装备选择的数学模型,并通过改进粒子群调度算法实现了医疗救治系统调度优化。最后,通过两次调度实验探究医疗救治系统在最大化伤员救治及时率时的系统调度规律,发现受限于医疗救治系统中的装备数量,在两次调度优化后也难以保证每名重伤员得到及时救治,只能尽量使伤员和装备调度合理优化,为指挥员提供调度决策依据。此外,限于篇幅,本文仅以伤员救治及时率作为目标函数进行优化分析,在后续研究中还可以从最小化平均等待时间和最小化救治完成时间等视角探究医疗救治系统的调度优化问题。