摘要：为在发生重大化工火灾时科学制定泡沫应急调度方案，研究不同算法在方案制定中的效果。通过对泡沫储备点选择问题的分析，确定问题模型；选用贪心算法和遗传算法，分析各个算法在制定泡沫应急调度方案中的思路；利用实例进行仿真比较不同算法产生的方案效果，给出各自的优缺点，并对算法进行优化。结果表明：在不同决策目标下选用合适的算法可达到该目标下最佳效果，基本满足泡沫应急调度决策的需要。

关键词：化工火灾；泡沫调度；贪心算法；遗传算法;应急救援

在重大石油化工灾害事故中，在明确火场需要的泡沫灭火剂数量后，选择泡沫储备点并将泡沫及时运输到火灾现场成为急需解决的问题。由于泡沫储备点位置较为分散，每一储备点的泡沫储存量不相同，从储备点调运至火灾现场的运输时间存在很大差异。因此，在进行泡沫灭火剂应急调运储备点选择决策时，需要综合考虑储备点的泡沫数量和从储备点到达火灾现场所需要的时间。

针对石油化工火灾应急物资调度问题，学者们运用双层规划模型、混合粒子群算法、改进人工蜂群算法等制定方案，但在泡沫这种单一物资调度中并不适用。笔者采用贪心算法，结合遗传算法优化给出泡沫应急调度方案。

一、问题描述与建模

假设情景为化工厂区发生重大火灾，急需泡沫量X吨才能发起总攻。全国的泡沫储备点有m个，每个储备点的储量为x_i（i∈[1,m]），每个储备点在最优运输方式下将泡沫运输至火场所用时间为t_i（i∈[1,m]），其利用GIS显示泡沫储备点相关数据。此时,需要决策的问题是选择n个泡沫储备点，使得这n个泡沫储备点所储备的泡沫总量大于所需泡沫量，且这n个泡沫储备点调泡沫到火场所用的最长时间t要达到最小，当t相等时则选择储备点数量最小，则相应的数学模型为： 

二、调度算法求解

2.1贪心算法

用贪心算法求解泡沫应急调运储备点选择问题，首先要选出最优的度量标准。其基本思想是从问题的某一个初始解开始，根据最优度量标准，每一步选择都要确保能够获取局部最优解。每一步只考虑一个数据，该数据满足局部优化的条件，若下一个数据不满足最优条件即不再考虑该数据。根据该问题描述，可以选择泡沫储量、运输时间以及储备点的储量与到达时间的比值即储量密度这三个最优度量标准进行贪心算法求解。

2.1.1泡沫储量

该最优度量标准是指在每一次选择储备点时都按照储备点储量最大进行选择，直至满足所需泡沫量。因此，对所有储备点按照泡沫储备量进行排序，即x₁≥x₂≥…≥x_m。当选择的前n个泡沫储备点所储备的泡沫量恰好满足火场需求时，比较n个泡沫储备点的运输时间，选择其中最长运输时间作为该泡沫应急调运方案所需要的时间。

2.1.2运输时间

该最优度量标准是指在每次选择储备点时都按照所用运输时间最短进行选择，直至满足所需泡沫量。因此，对所有储备点按照运输时间进行排序，即t₁≤t₂≤…≤t_m。当所选的n个储备点泡沫储备量恰好满足所需泡沫量时，比较n个泡沫储备点的运输时间，选择其中最长运输时间作为该泡沫应急调运方案所需的时间。

2.1.3储量密度

该最优度量标准是指在每次选择储备点时都按照储量密度最大进行选择，直至满足所需泡沫量。储量密度表示的是单位时间内可以运输的泡沫量，其值越大则单位时间内可以运输的泡沫量越多，越应被优先选为泡沫应急调运点。若用ρ表示储量密度，则对所有储备点按照储量密度进行排序，即ρ₁≥ρ₂≥…≥ρ_m。当选择的前n个泡沫储备点所储备的泡沫量恰好满足火场需求时，比较该n个泡沫储备点的运输时间，选择其中最长运输时间作为该泡沫应急调运方案所需要的时间。

2.2遗传算法

遗传算法是一类借鉴生物界的进化规律，即适者生存的遗传机制演化而来的随机搜索方法。其基本思想是将最优化问题理解为一定数量的初始解通过筛选变异向着最优解进行进化的过程。在该问题中则表现为先随机选择几组方案作为初始解，这几组方案中可能有一些方案并不满足火场所需泡沫液的要求或运输所用时间不是最短，而另一些方案则能满足。此时，通过设置的筛选机制淘汰掉不符合要求的方案，留下表现良好的方案并将保留下来的方案中部分储备点选择情况进行互换交叉，产生新的方案，再重复上述步骤从而使每次保留的方案有更好的效果。为防止新的方案陷于局部最优解，设置一定的几率使新方案中某一储备点从被选中变为不被选中或是相反，从而产生新的可能方案使其脱离局部最优解，向全局最优解探索。具体过程如下：

2.2.1基因编码

在此问题中，所有储备点的数量为m个，如果将一个方案看作一个染色体，则该染色体中的基因数为m，其中用1表示储备点被选中，0表示储备点没有被选中。如果某一方案中前n个储备点被选中，其余储备点没有选中，则该方案可以表示为：

2.2.2初始群体选择

初始群体是所有初始染色体的总和，即所有初始方案的总和。每一个方案都采用随机的方式生成，防止过早地陷入局部最优群体。初始群体的个数越多，寻找到全局最优解的可能性越大，但计算量也越大，故根据储备点的数量选择相应的初始群体规模。

2.2.3适应度计算

适应度是用来评价方案的。适应度越大，方案的效果越好，其一般是由目标函数变换而得。由于该问题的目标函数是求运输时间最小值，因而，需要将其转换为求最大值问题。其中一种转换方法是求出所有储备点均被选中时的最大运输时间t_max，用该最大运输时间减去其他方案的最大运输时间t，以差值表示适应度F，见式（1）。

F=t_max-t   (1)

另一个筛选条件是计算方案所选储备点的泡沫储量总数，若小于火场所需泡沫液量则直接淘汰不参与后面的交叉变异。淘汰后，需选择进行繁衍的染色体进行交叉变异。为使新方案有更好的效果，需要使适应度高的方案有更大概率进行繁衍。因此，采用经典的轮盘赌方法进行选择，即用每个方案的适应度除以所有方案的适应度总和的值表示该方案被选中的概率P，见式（2）。

(2)式中：N为可选的泡沫应急调运方案数；F_i为可选方案中第i个方案的适应度。

2.2.4交叉计算

交叉计算是将两个染色体按某种方式相互交换部分基因，从而产生两个新的个体，笔者使用基本的交叉算子即单点交叉算子。如果两条染色体的基因如下：

笔者随机选择的交叉点为第h个位置处，则将第h个位置处之后的基因相互交换，生成两个新的基因，即两个新的方案：

2.2.5变异计算

变异计算是使染色体中的某些基因值发生改变从而产生新的个体，是产生新个体的辅助方法，变异基因的个数不宜太大，否则会使表现优异的染色体变为适应度不高的染色体，从而无法找到更佳的方案。笔者采用基本位变异运算，随机选择一位或某几位进行变异计算，若某一染色体第1位发生变异，则变异后的新方案如下：

2.2.6迭代计算

在完成变异后即为完成一代的繁衍，通过重复上述繁衍从而产生更多的新方案，直至种群的适应度函数值基本不再增加而处于收敛状态时结束繁衍，找出其中最优的解即为最后的泡沫应急调运方案。

三、实例仿真及分析

案例情景为化工区储罐发生重大火灾，现场紧急需要1500t泡沫，此处参照漳州古雷火灾。假设全国泡沫应急调运储备点共50个，每个储备点的泡沫储备量由随机函数产生，单储备点泡沫储备量最大设为300t，最小设为10t，每个储备点到火场的运输时间也用随机函数产生，最大设为48h，且运输时间与泡沫储备量相互独立，其结果见表1所示。

3.1基于泡沫储量的贪心算法

由表1可知，将50个储备点按泡沫储量大小做降序排序，选择前6个储备点时，其泡沫液总数量为1520t，可满足火场所需泡沫量，此时选择方案为（40，13，35，32，11，18）或（40，13，35，32，11，28）或（40，13，35，32，18，28）。再计算这三种方案的运输时间分别为24、26、26h。所以选择第一种方案即（40，13，35，32，11，18），此方案可调运1520t泡沫，调运时间为24h。

3.2基于运输时间的贪心算法

将50个储备点按运输时间从小到大作升序排序。

方案一为（29,15,45,4,9,19,50,2,21，44，12,39，5,10,27，6,7,32），此时可调运总数量为1570t泡沫，调运时间为8h，选择18个储备点。

方案二为（29,15,45,4,9,19,50,2,21，44，12,39，5,10,27，6,32），此时可调运总数量为1520t泡沫，调运时间为8h，选择17个储备点。

方案三为（29,15,45,4,9,19,50,2,21，44，12,39，5,10,27，6，38,43,47），此时可调运总数量为1510t泡沫，调运时间为8h，选择19个储备点。

方案四为（29,15,45，4,9,19,50,2,21，44，12,39，5,10,27，7,32,38），此时可调运总数量为1500t泡沫，调运时间为8h，选择18个储备点。

方案五为（29,15,45，4,9,19,50,2,21，44，12,39，5,10,27，32，47），此时可调运总数量为1520t泡沫，调运时间为8h，选择17个储备点。

从储备泡沫量、调运时间和储备点数量看，方案二和方案五都有同样的效果，即可调运总数量为1520t，调运时间为8h且储备点数量为17个，因此，可以再从其他方面如储备点协调的难易程度进一步选择应急调运方案。

3.3基于储量密度的贪心算法

将50个储备点按储量密度大小做降序排序，选择前9个储备点可满足火场所需泡沫量，方案为(15,29,50,9,32,35,27,39,13)，此时可调运的总数量为1640t泡沫，调运时间为13h。

3.4遗传算法

由于使用的计算机处理器为i7-7700HQ，内存为8G。因此，根据其计算能力用随机函数产生10000个随机方案，用Python语言编写程序计算每一个方案的适应度，淘汰掉不能满足火场所需泡沫量的方案。让剩余符合要求的方案交换部分储备点选择情况，并随机将某些方案的储备点选择情况加以变化，产生新的方案后继续计算适应度直至适应度不再增加。由于遗传算法结果并不固定，还需设置额外的限制条件，如增加储备点选择数量极限，此处设置为10个储备点，经过多次运算得到的最佳结果方案为（9,10,15,26,27，29，32,35,39），最短运算时间为3s，此时方案可调运总吨数为1500t，调运时间为10h，选择储备点数为9个。在利用大数据Hadoop架构的情况下则可更快速处理复杂情况。

3.5算法结果比较

几种算法相比可以发现：

（1）基于泡沫储量的贪心算法选出的方案优势是选择的储备点数量少，但运输时间长；

（2）基于运输时间的贪心算法选出的方案优势是调运时间短，但选择的储备点数量多，且还可以去掉第4个储备点或第5个储备点，此时方案所调运的泡沫依次为1500、1510t，调运时间8h，选择的储备点数量16个；

（3）基于储量密度的贪心算法选出的方案优势是选择的储备点数量和运输时间都相对较好，但调运的泡沫液多，可以去掉储备量小于140t的储备点，使选择的储备点数变为8个；

（4）遗传算法在泡沫调运时间和选择的储备点数量上也表现出较好的效果，且不用再去掉某一储备点才能达到最佳效果，在考虑运输时间的因素下其效果比基于储量密度的贪心算法更好。但遗传算法的参数设置较为复杂，包括初始群体数量、交叉概率、变异概率、迭代次数、误差精度等参数，若没选好参数会使方案陷于局部最优，需人为尝试调参并训练多次才达到全局最优。

3.6算法改进

由于贪心算法每一步都根据最优度量标准选择方案，致使最后储备点的选择会多出一部分，而遗传算法生成的初始解不稳定，难以快速确定最优方案。因此，将贪心算法与遗传算法相结合，利用贪心算法先生成初始最优解，再利用遗传算法在初始最优解的基础上继续寻找最优方案。如先利用基于储量密度的贪心算法获得初始解(15,29,50,9,32,35,27,39,13)，再利用遗传算法寻找最优解，得方案(15,29,50,9,32,35,27,13)。由结果可以看出，基于贪心策略的遗传算法可以使贪心算法结果处于最优状态，但如果想获得更多可能方案则要脱离贪心算法的影响，只使用遗传算法。 

四、结论

通过对比基于泡沫储量的贪心算法、基于运输时间的贪心算法、基于储量密度的贪心算法和遗传算法等四种算法在泡沫应急调运点选择问题中所给出的不同方案，得出各种算法所具备的优缺点。在只考虑运输时间最短时，则可用基于运输时间的贪心算法获得方案，并用遗传算法优化结果；在只考虑储备点数量最少时，则可用基于泡沫储量的贪心算法获得方案；在考虑综合运输时间和储备点数量时，则可用遗传算法获得方案，其效果要优于经过遗传算法优化的基于储量密度的贪心算法所获得的方案。

往期文章

连载：地球长寿之王、致癌毒物——PFAS的前世今生（一）！

连载：永生不灭的分子PFAS–从崭露头角到原形毕露（二）

连载：永生不灭的分子PFAS–众矢之的又成漏网之鱼（三）

连载：多方立法禁止“C8”-消防泡沫技术何去何从（四）？

整体认识PFAS——系谱图

欧盟对PFOS（全氟辛烷磺酰基化合物）的管理法令

C8污染“魔影”!!!（深度调查长文）

——————————————————————————

本文主要内容来自于：王进，胡人元，臧娜（中国人民警察大学，河北廊坊065000）

中图分类号：X937,TU998.1,TQ569文献标志码：A

文章编号：1009-0029（2019）03-0411-04

版权归属于原作者。

---------------------------------------

德国斯坦默公司全系列灭火剂产品

均不含PFOA和PFOS

符合所有当前限制条件！

---------------------------------------

众多客户选择的

斯坦默

全球认证

斯坦默 

关于PFAS(PFOS、PFOA等）消防领域更多危害科普文章如下：

不务正业的转载：《黑水DARKWATER》影评

高能预警||水成膜泡沫灭火剂致土壤污染的健康风险分析

松花江水系江水中全氟辛烷磺酸和全氟辛酸污染现状调查

水成膜泡沫（清水/轻水泡沫）AFFF消防泡沫的遗留问题

明知PFAS污染严重，两年来MDL基地无动于衷

驻日冲绳基地泄漏强致癌物，美军：一点点消防泡沫，你也有意见？

全氟辛烷磺酸对雄性鹌鹑生殖毒性影响

在21世纪，消防所面临的挑战日益严峻并且仍在不断发生变化。这不仅涉及灭火材料本身的性能，而且对灭火解决方案的环保性、社会认同性方面提出了更高的要求。预防性和防御性的消防任务特别复杂，并且解决方案需要考虑到各种细节。特别是在工业方面，只能通过丰富多样、成熟的产品，来实现灭火效率更高，成本更低廉的解决方案。从早期Richard.Sthamer博士创立公司，直至现在公司第5代管理人，我们的目标始终如一：提供高标准、高质量的产品，并且始终尽最大努力满足各类客户的不同需求。自公司于1886年成立于汉堡起，我们始终致力于研制优质的泡沫灭火剂。如今，Dr.Sthamer公司已经是主流的泡沫灭火剂制造商之一。作为一家中型、家族式企业，Dr.Sthamer具备充分的灵活性是商业成功并且使世界各地客户均满意的保证。

现在，Dr.Sthamer泡沫灭火剂已成为灭火材料的代名词。这既是我们的职责所在，也是激励我们不断前进的动力所在。 

欢迎关注JLH公众号，共同保护我们的家园，请使用环保无毒灭火剂。