防疫抗疫物资装配优化方案研究

Study on Assembly Optimization Scheme for Epidemic Prevention and Anti-Epidemic Materials

摘要: 本文以防疫抗疫物资装配为研究对象，通过防疫抗疫物资和保障人员组合、装配工具之间的关系，选取装配时间最短和满装配量为目标函数，建立了装配物资的数学模型；采用改进的遗传算法，构建了装配工具的装载和调度问题的有效算法；通过数值仿真给出了装配工具装载物资和人员以及调度的方案。这为提高抗疫防疫物资装配的科学性和时效性具有重要意义。

Abstract: This paper considers epidemic prevention and anti-epidemic materials as the research object. Based on the relationship among epidemic prevention and control materials, support personnel, and assembly tools, the mathematical model of assembly materials was established with the shortest transportation time and full load as the objective function. An improved genetic algorithm proposed a practical algorithm for loading and scheduling assembly tools. The loading materials, personnel, and scheduling scheme were given through numerical simulation. It was of great significance for improving the scientific and timeliness of the assembly of anti-epidemic materials.

1. 引言

近几年，新冠疫情的大面积传播影响着全世界每一个人，随着新冠病毒的不断变异，病毒的传播途径越来越隐秘。一旦发现疫情，必备的防疫抗疫物资的准备和保障，是抗击病毒的关键环节，是完成抗疫任务的关键一环。因此，在防疫抗疫过程中，如何科学地安排装配方案，使防疫物资尽可能地满足医护人员的需求，使基本生活物资满足隔离人员的生活保障，是防疫抗疫过程急需解决的重要问题。

该问题的实质是带组合约束的装载输送问题，具有很强的现实需求，国内外学者已经做了大量的研究。Shachnai [1] 提出了有类型约束的装箱问题，Hoto [2] 给出了分区背包问题的材料切割实例。徐清华等 [3] 根据装配特点建立了多目标装载规划模型，并利用智能算法和计算机编程工具实现配置规划模型的优化解算法。吴晓东等 [4] 考虑物资与运输工具关系，建立了积载模型。许建强等 [5] 选取运输成本最小化为目标函数，建立了不同载运工具配载方案。张文斌等 [6] 采用模拟退火法建立了运输装载模型给出了最优的装载方案。宋英华等 [7] 基于最小化医院物资集散点需求最小化和物资购买集中点分配最大化，建立了储备库选址–分配模型。和媛媛等 [8] 考虑多品种应急物资多批次合车运输，建立多救援点、多疫区和多物资品种的应急物资配送模型。

在上述研究的基础上，本文以防疫抗疫物资、保障人员及其组合、装配工具之间的组合配送关系为研究对象，以不同防疫抗疫物资组合为约束的装配模型，以装配工具满载和运输时间最短为约束条件，以最大程度地装载最多的防疫抗疫物资和保障人员及其组合为目标，通过抗疫防疫物资装载和调度问题的有效算法，给出防疫抗疫物资和保障人员的具体装配方案。

2. 装配模型

在组织有效防疫抗疫过程中，通常涉及到当地和外地驰援医护工作者的基本医疗防护物资的供给，例如专用防护服、防护面罩、防护口罩、防护鞋套、医用酒精等；医护工作者和志愿者等的基本生活物资的供给，例如棉衣棉被、防疫帐篷、简易折叠床等；待检样本的时效问题，例如检测样本的三小时送检和检测报告的快速给出等；疫区地居民的基本生活物资保障，例如米、面、油、肉、蛋、奶、蔬菜等等。在组织诸如此类的多头绪多任务的物资装配时，通常会涉及的装配工具的类型、数量较多，载运防疫防护物资和对应的保障人员组合的类型、数量较多。而这些因素都直接影响输送保障任务完成的效率。通过构建装配方案优化模型，使得在最短的时间内完成整个装配任务，提高工作效率，是提高装载输送任务效率的有力方法。

2.1. 装配分类

为更好地描述上述问题，要将不同类型的装配工具、需载运防疫抗疫物资和相关的保障人员进行组合分类。

1) 装配工具按照其使用方式划分 $t\_n_1$ 类型，每种类型为 $t\_n_1\_m_{n1}$ 种型号。

2) 输送防疫抗疫物资和对应保障人员组合按照不同功能和不同需要等特点，包括专用医疗物资、基本医疗物资、运载危重病人、基本生活物资等分为 $c\_n_2$ 种组合。

进一步分析，考虑到实际情况，输送物资–人员组合与运载工具之间存在不同的装配组合。比如：组合 $c\_1$ 只能装配在 $t\_n_1\_1$ 型装配工具，不适合在 $t\_n_1\_2$ 和 $t\_n_1\_3$ 型装配工具；组合 $c\_2$ 只能配置在 $t\_n_1\_1$ 型装配工具或 $t\_n_1\_2$ 型装配工具，不适合在 $t\_n_1\_3$ 型装配工具。

2.2. 装配模型

设完成某次输送任务所需输送防疫防护物资和对应的保障人员组合的总数为

$S_c=\left\{S_{c\_1},S_{c\_2},S_{c\_3},\cdots ,S_{c\_n_2}\right\}$ (1)

其中， $S_{c\_k}$ 分别为第k组合的数量。

可用于输送装载的装配工具总数为

$S_t=\left\{S_{t\_1\_1},\cdots ,S_{t\_1\_m_1},S_{t\_2\_1},\cdots ,S_{t\_2\_m_2},S_{t\_n_1\_1},\cdots ,S_{t\_n_1\_m_{n1}}\right\}$ (2)

其中， $S_{t\_i\_j}$ 表示第i类装配工具m_i型号 $M_{t\_i\_j}$ 的数量，第k组合配置给 $M_{t\_i\_j}$ 型号装配工具的数量分别为 $S_{t\_i\_j}^{c\_k}$。不同组合相应的装配工具的装载所消耗的时间为 $t_{t\_i\_j}^{c\_k}$，各装配工具完成具体装载任务所消耗的时间为 $T_{t\_i\_j}$。

为了合理规划组合的配置方案，计算各种组合完成装配任务的时间，建立多目标装配模型，即

$\min F\left\{S_{t\_i\_j}^{c\_k}\right\}$ (3)

$s.t.\{\begin{array}{l}F\left\{S_{t\_i\_j}^{c\_k}\right\}=\max \left\{T_{t\_1\_1},\cdots ,T_{t\_1\_m1},T_{t\_2\_1},\cdots ,T_{t\_2\_m2},\cdots ,T_{t\_n_1\_1},\cdots ,T_{t\_n_1\_m_{n1}},\right\}\\ T_{t\_i\_j}=\frac{1}{S_{t\_i\_j}}{\displaystyle \underset{k,i,j\in N_1}{\sum }{S}_{t\_i\_j}^{c\_k}{t}_{t\_i\_j}^{c\_k}}\\ S_{c\_k}={\displaystyle \underset{k,i,j\in N_2}{\sum }{S}_{t\_i\_j}^{c\_k}}\\ i=1,2,\cdots ,n_1\end{array}$ (4)

在此假设：所有防疫抗疫物资和对应的保障人员均折算为标准单元；每个装配工具以及不同装配工具的装配组合是独立的；为充分利用运力，所有的装配组合都必须满载。

3. 改进遗传算法

抗疫防疫物资的装配优化所要解决的是实现整体装配时间最短的问题，这属于多目标规划问题。结合遗传算法在物资选址–分配模型和配送策略中应用 [7] [8]，根据上述装配模型和约束条件，给出装配优化模型遗传算法的流程图，如图1所示。

4. 数值仿真

为实现防疫抗疫任务需要，假设输送物资–人员组合与运载工具之间存在不同的装配组合有8个 $c\_1$ 组合，6个 $c\_2$ 组合，3个 $c\_3$ 组合。防疫抗疫集结点有 $t\_1$ 、 $t\_2$ 和 $t\_3$ 种运载工具，其各有三种型号。为简化计算，其中每种装配工具可调用1种型号，为完成以上装配任务，本文通过上述模型和算法给出此次装载任务的配置方案。

Figure 1. Flow chart of improved genetic algorithm based on assembly model

图1. 基于装配模型的改进遗传算法的流程图

Table 1. Assembly resource information of material reserve

表1. 物资储备地的装配资源信息

利用遗传算法，选取下列参数：选取种群数量值100，交叉概率0.9，变异概率0.1，得到最终的装配方案：

1) $t\_1$ 运载工具：安排 $t\_1\_1$ 型运载工具，4个 $c\_1$ 组合，4个 $c\_2$ 组合，装载时间3.2小时；

2) $t\_2$ 运载工具：安排 $t\_2\_1$ 型运载工具，4个 $c\_1$ 组合，2个 $c\_2$ 组合，装载时间4.2小时；

3) $t\_3$ 运载工具：安排 $t\_3\_3$ 型运载工具，3个 $c\_3$ 组合，装载时间3小时；

4) 装载顺序：首先，安排 $t\_3\_3$ 运载工具装载，装载次数3次；然后，安排 $t\_1\_1$ 运载工具装载，装载次数4次；最后，安排 $t\_2\_1$ 运载工具装载，装载次数3次；

5) 全部输送装载完毕需要最短时间为： $\max \left\{3.1,4.1,2.9\right\}=4.1\text{h}$。

进一步分析，如果每种运载工具存在不同的可调度的型号，其实质是按照此思路再一次分配问题，在此不再论述。

5. 结论

考虑到防疫抗疫物资的高效供给性，本文利用多目标规划和遗传算法理论构建抗疫防疫物资和相关保障人员组合和运载工具之间的装配方案优化模型，有效解决了物资和人员组合的装配优化问题，提高了防疫抗疫工作的科学性和时效性。但装配问题是典型的NP-Hard问题，随着抗疫防疫物资和相关保障人员组合和运载工具的种类及数量的增加，还需进一步改进算法提高效率。