考虑时效的应急物资配送路径优化方法

梁永梅 房志明 黄嘉豪

摘  要：针对城市区域的应急医疗物资配送问题，把医疗点作为节点，医疗点之间的路径作为边，构建了相应的应急医疗物资配送的图模型。提出了两种面向实际需求的模型求解目标，一种是路径最短，该目标追求配送路径/用时最短，另一种是时效性最优，该目标追求人均可利用配售时间最多，以减轻人群聚集情景。建立了基于遗传算法的应急医疗物资配送模型求解方法，并针对一个实例进行了计算分析，结果表明，路径最短的配送方案不一定能达到最优的人均配售时间，而如果想实现较多的人均配售时间，则可能需要花费较多的配送成本。

关键词：医疗物资;配送;路径;时效;遗传算法

中图分类号：F252.14    文献标识码：A

Abstract： In the event of an infectious disease epidemic， the rational dispatch and distribution of emergency medical supplies is the basis for epidemic prevention to ensure the safety of people's lives. Aiming at the problem of emergency medical supplies distribution in urban areas， taking medical points as nodes and paths between medical points as edges， a corresponding graph model of emergency medical material distribution is constructed. Two model solution goals oriented to actual needs are proposed. One is the shortest path， which pursues the shortest delivery route/time， and the other is the best timeliness， which pursues the maximum time available for allotment to reduce crowd gathering. A genetic algorithm-based emergency medical supplies distribution model solution method is then established， and calculation and analysis for an example is carried out. The results show that the shortest path distribution plan may not achieve the optimal per capita distribution time， and more per capita distribution time may require more travel costs.

Key words： medical supplies; distribution; routing; timeliness; genetic algorithm

0  引  言

自2019年底開始的新型冠状病毒肺炎疫情，给全球公共卫生带来了严峻的挑战。尤其2020年初，口罩、医用防护服等重要医疗物资一直处于极度短缺状态，应急医疗物资的生产与配送成为应对新冠肺炎疫情的关键。以口罩为例，作为阻断新冠肺炎疫情在普通民众间传播的最经济且有效的工具，其需求量急剧攀升，且远远超出了日常产量。在口罩产能不足之时，为了保障居民的正常生活需求，国内各地一度对口罩配售实行统一调度：居民在所属地实名预约，口罩配送至定点药店，居民凭预约信息至定点药店购买。其中，口罩配送方案与路径是否最优决定了统一调度是否高效。因此，研究口罩等应急医疗物资的配送优化问题具有重要现实意义。

李元亨等人[1]以新型冠状病毒肺炎疫情应对中的医疗物资配置为例进行分析，发现突发公共卫生事件应急管理已经从本质上异于或超越了传统的制度主义基本逻辑范畴。张丽娜等人[2]以新冠疫情发生后的医用口罩需求动态为观测点，搜集相关新闻、评论，发现应急医疗物资在疫情蔓延早期面临着价格暴涨、质量良莠不齐、保障不足与分配失衡等问题，由此引发的民众脆弱性和政府信任危机给疫情防治带来了巨大挑战。褚永华等人[3]探索了医院医疗物资应急保障机制，指出医院医疗物资保障团队需要依据“开源节流、量出为入”的原则，实行积极的物资采购策略，根据风险等级制定物资分配优先级，以存量与用途为依据统一发放物资，并实行捐赠物资的可追溯化管理。韦艳等人[4]调研了新疆179家二级以上医院的应急资金及物资管理、急救设备配备等情况，指出各级医院的应急救援物资管理现状不容乐观，存在突发事件医疗救援应急资金储备、设备管理体系建设不完善，急救设备不齐全，消毒净化能力薄弱等问题。潘婷[5]针对突发事件下应急医疗物资的配送问题，根据受灾区的灾情等级、伤亡人数和交通路况等灾情信息已知的情况，构建了完全灾情信息下的应急医疗物资分配方法和运送模型，结合模糊数相关基本理论，构建了不完全灾情信息下的应急医疗物资分配方法和运送模型。能够依据受灾区的具体实际受灾情况，确定为各个受灾区分配与其情景相符合的应急医疗物资的比例及数量，然后确定分配给各受灾区的应急医疗物资分别由哪个或者哪几个供应点提供以及提供多少，并将其及时有效地运送到各个受灾区，以达到缓解灾情、减少损失的目的，也可提高有限的应急医疗物资在应急响应中的使用效率。陈波[6]针对突发事件不确定性和紧急性，建立了应急医疗物资调度中的车辆路径优化模型，设计有效的遗传算法对模型进行求解，并用实例验证了应急医疗物资调度中的车辆路径优化模型及算法的有效性和可行性。陈思地[7]根据传染疾病的特点探讨了建立医疗物资生产基地、基于大数据确保安全库存、通过ABC分类进行配送的方案，指出确保运输道路畅通、市民有序理智购买预防物资对有效抗击传染疾病有重大意义。

本文关注应急医疗物资配送路径优化问题，在考虑最短路径配送基础上，引入配送时效性概念，从最短路径和实效性两方面构建应急医疗物资配送模型，并建立基于遗传算法的模型求解方法。

1  模  型

1.1  模型构建

本文关注某一城市或区域的简化应急医疗物资配送问题，假设有n个定点配售点，只有1只配送队伍负责将应急医疗物资由起始位置运送至各个配售点。基于图论构建上述问题数学模型：

（1）假设应急医疗物资配送需求n个医疗点，每个医疗点作为节点，医疗点之间的距离记做d，则可用简单图G

=V，E，D描述该问题，其中V为节点集合，数量为n;E为每两个节点之间边的集合;D为每两个节点之间距离的集合，节点与自身的距离记为0，不直接连通节点之间的距离记为∞。

（2）进一步，可用如下邻接矩阵表示该模型，矩阵中的元素记录的是每两个节点之间的距离。

（1）

（3）记起始位置为Sx，y，该配送问题即为从S位置出发，遍历图中每个节点。

1.2  模型求解目标

针对上述配送问题，本文提出两种求解目标：

目标一：路径最短。该目标下，配送队伍从起始位置出发，遍历每个节点所用路径最短，不考虑路况影响，此时的用时也最少。对有n个节点的图，记路径中到第i-1节点到第i节点的距離为d，则该最优目标可表示为：

min∑d                                                （2）

目标二：时效性最优。由于城区居民分布及医疗点分布不均匀，各个医疗点服务的人群数量有可能差异较大。因此，本文认为在配送过程中，需要考虑各节点（医疗点）的权重（服务人群数量），使得人均可利用配售时间最多。以口罩统一配送为例，各个医疗点的预约人群数量不一样，为了减少不必要的人群排队聚集，应该使得人均购买配时（医疗点的统一配售时间

/医疗点的预约人数）越大越好。记总的可用时间为T，配送速度为v，则第i节点可用的配售时间为t=T-∑d/v，记每个节点的权重为w（值越大代表服务人数越多），则时效性最优目标可表示为：

max∑T-/w                                           （3）

1.3  基于遗传算法的模型求解方法

本文研究的配送问题属于一个典型的NP-hard问题，这类问题通常无法通过精确算法进行求解，只能利用近似算法求取近似最优解。常见的近似算法有贪心算法、遗传算法、概率算法等。而遗传算法作为一种近似算法，在求解较为复杂的组合优化问题时，相对一些常规的优化算法，通常能够较快地获得较好的优化结果，并且具有群体搜索的特点，它的搜索过程是从一个具有多个个体的初始群体开始的，这样既可以有效地避免搜索一些不必搜索的点，同时也能避免传统的单点搜索方法的弊端，不会陷入某个局部极值点，有着非常好的并行化和全局搜索性。因此本文采用遗传算法来求取模型的最优解。

在本文模型与常规遗传算法逻辑基础上，求解算法设计如下：

（1）遗传编码的设计

基因编码目的在于使求解的目标问题与所要用的遗传算法的染色体之间建立联系。本文选取实物编码作为编码方式，首先对模型中每一个节点（医疗点）都按照一定规律进行编号，再利用编号排列的先后顺序来表示救援路径。其中，每个节点编号抽象为一个基因编码，一条完整的配送路径的节点编号序列抽象成一条染色体。

（2）种群的初始化

种群规模的初始化设置会对问题的优化程度产生较大影响，因为初始化设置的种群的质量会直接影响遗传算法的收敛速

度[8]。若种群规模过小，将不利于增加种群的样本多样性，可能会在后面的迭代过程中造成收敛过快的现象，从而丢失最优点，而最终收敛于局部最优解。反之若种群规模过大，将会极大地增加算法的计算量和算法的收敛时间。依据经验，本文将种群规模设计为150。

（3）适应度函数的设计

适应度函数是遗传算法中的一种评判的标准，作为一种重要选择机制，和后续的选择和交叉工作有着密切的关系。本文的目标函数是求最短路径或最大的配时，直接从种群中挑选出达到相应目标的路径作为最优解，即把目标函数直接设置为适应度函数。

（4）遗传操作

设定好适应度函数后，通过适应度函数可以得到不同个体的适应度大小，但是真正的筛选过程则需要经过一系列的遗传操作，对优劣程度不同的个体进行筛选。以下是三种操作过程：

①交叉操作

遗传算法交叉操作模拟的是生物体在有性繁殖过程的基因重组过程，两个配对好的染色体通过某种方式交换它们各自部分基因，从而产生出两个新的个体。交叉操作的过程中需要确定交叉概率和交叉操作模式。本文中，一个基因表示一个医疗点，所以在新生成的染色体中，原有的基因不能消失，也不能重复。根据以上特点，本文选择采取两点交叉的操作模式。根据经验，设定交叉概率为0.8，即对每一条染色体，在0到1间随机生成一个数，对生成的随机数小于交叉概率的染色体进行交叉操作。

②变异操作

变异操作可以有效地增加种群数目，首先在种群中选择出要变异的个体，再选择个体中的染色体上要进行变异的基因。本文中的基因不能凭空消失，也不能任意的插入其他染色体中。根据这个特点，本文采用换位变异的方式，变异概率的值则设为0.002。在选出要进行变异的染色体之后，需要对它的每位基因都取一个0到1之间的随机数，然后交换随机数最大的两个基因，以达到变异的目的。

③选择操作

选择操作指按照某种特定的规则，在之前得到的种群中不同个体的适应度值中，选出适应度较好的个体遗传到下一代的过程[9]。基因的选择方式有很多种。本文选择采用轮盘赌方式，轮盘赌方式是一种基于适应度比例的选择方法，能够增大适应度大的个体遗传到下一代的概率。假设个体i的适应度为F，则所有个体适应度的总和为∑F，这样就得到了i的选择概率如公式（4）所示：

P=                                               （4）

其中： N=150表示种群规模的大小。

（5）终止条件

为了提高运算效率并且得到满意的运算结果，需要对遗传算法设置进化的终止条件，本文选择在迭代的次數达到30 000次时终止。

2  实例分析

为了检验模型，假设一个实例进行分析，该实例如表1所示，主要元素及模型参数设置如下：

（1）假设有18个医疗点，标记其ID为1～18，每个医疗点的坐标值及权重在表1中给出;

（2）表1中ID为0点作为起始位置，即S0，0点为起始点;

（3）起始点与各个节点、各个节点之间的距离即是坐标点之间的直线距离;

（4）假设T=24，v=50。

分别针对公式（2）与公式（3）的目标，基于遗传算法进行分析计算，结果如表2和图1所示。可以看到，两种目标下的结果并不一致：（1）到达各个医疗点的次序不同，时效性最优目标下甚至出现了路径交叉的情况（图1b）;（2）路径最短目标下的路径长度为281.36，时效性最优目标下为341.53，高出了21.39%;（3）路径最短目标下的时效为8.55，时效性最优目标下为8.63，多出了0.94%。结果表明路径最短的配送方案不一定能达到最优的人均配售时间，而如果想实现较多的人均配售时间，则可能需要花费较多的配送成本（路径增加导致的成本增加）。

3  结  论

针对城市区域的应急医疗物资配送问题，把医疗点作为节点，医疗点之间的路径作为边，构建了相应的应急医疗物资配送的图模型。并给出了两种模型目标以对应两种实际需求，一种是路径最短，该目标追求配送路径/用时最短，另一种是时效性最优，该目标追求人均可利用配售时间最多，以减轻人群聚集情景。

建立了基于遗传算法的应急医疗物资配送模型求解方法，该方法中将节点作为基因，将配送路径试做染色体，并把模型的目标函数设置为适应度函数。针对一个实例进行了计算分析，结果表明，路径最短的配送方案不一定能达到最优的人均配售时间，而如果想实现较多的人均配售时间，则可能需要花费较多的配送成本（路径增加导致的成本增加）。本文建立的模型能够从两种不同的角度考虑应急医疗物资配送问题，可供决策者视实际需求而选择合适的配送方案。

参考文献：

[1] 李元亨，王亦冬，赵思奇，等. 新型冠状病毒肺炎疫情防控医疗物资配置策略研究[J]. 中国医院管理，2020，40（4）：5-7.

[2] 张丽娜，峗怡. 以医用口罩为例探讨新型冠状病毒肺炎疫情中政府应急卫生资源保障对策[J]. 中国医疗管理科学，2020（3）：15-17.

[3] 褚永华，邹瞿超，谢慧玲，等. 新冠肺炎疫情下医院医疗物资应急保障机制探索[J]. 中华医院管理杂志，2020，36（4）：345-348.

[4] 韦艳，李伟. 新疆179家医院突发事件医疗救援应急物资管理现状调查[J]. 职业卫生与应急救援，2020，38（4）：381-384.

[5] 潘婷. 突发事件下应急医疗物资配送问题研究[D]. 西安：西安工程大学（硕士学位论文），2019.

[6] 陈波. 应急医疗物资调度中的车辆路径优化研究[D]. 武汉：武汉理工大学（博士学位论文），2013.

[7] 陈思地. 传染疾病情景下的应急物流研究[J]. 物流工程与管理，2020，42（4）：103-104.

[8] 张立仿，张喜平. 量子遗传算法优化BP神经网络的网络流量预测[J]. 计算机工程与科学，2016（1）：114-119.

[9] 吴志杰，孔凡敏，李康. 基于遗传算法的BP神经网络的LED寿命预测模型[J]. 半导体技术， 2018，43（5）：62-67.