基于遗传算法的河南省应急物流中心选址研究

Genetic Algorithm-Based Site Selection Study of Emergency Logistics Center in Henan Province

摘要: 以河南省为例，通过分阶段递进式的方法进行初步选址和最终选址。首先根据影响应急物流能力的主要因素形成指标数据，将其带入熵权评价模型，得到河南18个地区应急物流能力评价指数排名，采用Ward聚类法将18个地区分为4类，并剔除4个地区。再将剩余14个地区设为物资供应点，全省109个节点为需求点，通过遗传算法求解满足需求加权距离最小化且带有容量限制和时间窗约束的选址模型，通过多次实验将数据带入模型得到最终理想选址方案，既能提高应急物流中心的响应速度，也能减少建设成本，最大程度的保证应急物流中心选址的合理性。

Abstract: In recent years, all kinds of natural disasters have been high, seriously affecting the normal order of society and the safety of people’s property. The state attaches great importance to the comprehensive management of natural disasters and emergency response capacity building, and vigorously carries out all emergency management work. For the emergency logistics center as an important part of the emergency logistics system and emergency logistics network and key nodes, its scientific and reasonable location planning can improve rescue efficiency, reduce emergency costs, reduce losses from natural disasters. Therefore, at the pre-disaster stage, how to build an emergency logistics center at a key location in a region and reserve materials in advance, so that emergency materials can be delivered in a timely and efficient manner to the point of demand for disaster relief after the disaster has occurred will become very meaningful and critical, which is precisely the focus of this paper. Taking Henan Province as an example, the preliminary site selection and final site selection were carried out through a phased progressive approach. Firstly, the index data is formed according to the main factors affecting the emergency logistics capacity, which is brought into the entropy power evaluation model to get the ranking of the emergency logistics capacity evaluation index of 18 regions in Henan, and the Ward clustering method is used to divide the 18 regions into 4 categories and eliminate 4 regions. Then, the remaining 14 regions are set as material supply points, and 109 nodes in the province are demand points. The location model with the minimum weighted distance of demand and with capacity constraints and time window constraints is solved by genetic algorithm. The final ideal location scheme is obtained by bringing data into the model through multiple experiments, which can not only improve the response speed of the emergency logistics center, but also reduce the construction cost, to ensure the rationality of emergency logistics center location to the greatest extent.

1. 引言

近年来，河南省因其独特的地理位置、地貌特征和气候条件等因素，使得自然灾害频发、受损严重且波及广泛，如干旱、洪涝、风雹、生物灾害等，部分低温冷冻、雪灾、地震、滑坡也不同程度发生，给全省人民生活和生产造成严重威胁，其中以2021年河南省遭遇特大暴雨尤为严重，发生严重洪涝灾害和地铁灌水事件，造成重大人员伤亡和财产损失，灾害共造成河南省150个县市区1478.6万人受灾，因灾死亡失踪398人，其中郑州市380人、占全省95.5%；直接经济损失1200.6亿元，其中郑州市409亿元、占全省34.1%。以上发生的突发事件，既面对自然灾害和新冠疫情双重遭遇，还面临暴雨过后鼠疫瘟疫等次生灾害的影响。由此可见，河南省面临的突发事件种类多、复杂交错，具有致灾性和毁灭性，对其建设和社会生产造成不可挽回的后果。自然灾害突发后，物流支撑着整个应急救援活动，保障着应急物资平稳运行。应急物流中心作为应急物流系统和应急物流网络中重要组成部分和关键节点，其科学合理的选址规划能够提高救援效率、降低应急成本、减少自然灾害事故损失。

2. 文献综述

应急物流系统主要包括了应急物流中心的选址和应急物资派送的路径。对于应急物流中心选址的问题研究，不少学者认为时间、距离、救援成本等是其影响因素。张旭敏(2008)将影响应急物流中心选址的因素分为内部因素和外部因素，外部因素为不由自身控制的地理自然环境因素、政治经济因素，内部因素为应急设施的仓储容量、种类分类、数量等微观因素 [1] 。张铱莹(2011)指出应急物流救援是个多阶段的动态过程，根据灾难发生的不同阶段，选址因素会有区别。灾难未发生时，选址侧重于经济、交通建设良好的地区，旨在发挥城市物流能力；而灾难发生时，侧重于时间紧迫性、救援效率等因素 [2] 。谷玲玲(2018)在评估应急物流设施选址的问题上，对影响因素分级处理，得到技术因素、经济因素、环境因素、社会因素4个一级因素 [3] 。Feng (2020)等提出了一个考虑更多实际因素的选址数学模型，其优化目标是使总运输长度和运输成本最小 [4] 。

对于应急物流设施的选址问题，国内外既有文献大致分为两种解决方案：第一种，采用运筹学的思想方法构建混合整数线性规划模型；第二种，主要考虑各种选址方案的指标特性。Caunhye A M (2012)等增加了了P中心模型的服务点容量约束条件，采用了一种基于时间复杂度的启发式算法 [5] 。Nyimbili等(2020)考虑到单一赋权的弊端，采用CRITIC法赋权和变异系数赋权法相结合的方法 [6] 。罗凌珊(2021)考虑到时间在突发事件的关键作用，在覆盖模型的基础上，引入时间满意度函数，使每个需求点的时间满意水平得到衡量，最大限度保障应急设施的覆盖率 [7] 。仇明艳等(2021)首先考虑到区域的投入产出效率，构建基于DEA的区域物流效率评价模型，将确定的效率值作为子目标，构建DEA、传统选址相结合的多目标选址模型 [8] 。刘明(2020)提出了以应急时效性为目标的动态多周期应急物流网络优化模型并运用遗传算法进行求解，从而确定每个周期内最优的应急选址 [9] 。郑琰(2020)将影响选址的影响因素分为定性因素和定量因素，包括地理因素、交通因素和经济因素 [10] 。倪卫红(2021)考虑到各个受灾地区有不同的需求量，将不确定的需求量作为动态应急设施选址的影响因素 [11] 。

从目前文献来看，国内外学者在研究应急物流选址规划问题上已取得了丰富的研究成果，为应急物流中心选址提供了不同的研究思想角度和技术方法。

3. 熵权综合评价模型

3.1. 应急物流能力指标选取

基于自然灾害和应急物流的相关特点，影响应急物流能力的因素主要分为区域经济发展水平、物流基础运作能力、区域资源配置能力、基础建设支撑能力、信息保障能力等5个方面 [6] [7] 。区域经济发展水平是应急物流发展的硬性条件和驱动力，包括城市GDP、物流增加值、物流固定投资额占比。物流基础运作能力是衡量物流能力的关键因素，是区域内物流规模、物流企业量、货运量及周转量等的动态有机整体。资源配置能力是区域内对应急物流活动提供物资、人员、资金、服务等保障条件的能力。基础建设支撑能力是为应急物流活动提供交通和物流网络服务的支撑能力。信息保障能力是开展应急物流活动必要的先决条件，伴随着物资清单、需求清单、伤亡人数等一系列数据的顺利开展，贯穿了应急物流活动的始终。根据该5项影响因素形成区域应急物流能力评价指标体系(见表1)，并对河南省18个地区2017~2021近五年的相关数据进行统计。

3.2. 构建熵权评价模型

1) 数据标准化处理。

对区域应急物流能力评价指标进行数据标准化处理，主要采用极值标准化方法：

对于正向指标：

$a_{ij}=\frac{x_{ij}-\min x_j}{\max x_j-\min x_j}$ (1)

对于负向指标：

$a_{ij}=\frac{\max x_j-x_{ij}}{\max x_j-\min x_j}$ (2)

其中，x_ij和a_ij分别表示第i个城市第j项指标的原始值和标准化处理后的数值， $i=1,2,\cdots ,m$ ， $j=1,2,\cdots ,n$ ； $\max x_j$ 和 $\min x_j$ 分别表示所有城市第j项指标数据统计值的最大值和最小值。

2) 指标权重计算。

采用熵值法计算区域应急物流能力评价指标权重，过程如下：

① 计算指标相对比重。p_ij表示第j项指标下第i个城市指标的变异程度：

$p_{ij}=\frac{a_{ij}}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{a}_{ij}}}$ (3)

② 计算指标熵值。e_j表示第j项指标的信息熵值：

$e_j=-f{\displaystyle \underset{i=1}{\overset{m}{\sum }}{p}_{ij}}\ln p_{ij}$ (4)

其中， $f=\text{1}/\text{ln}\left(m\right)$ 。

③ 计算冗余度。h_j表示第j项指标的信息熵冗余度：

$h_j=1-e_j$ (5)

其中，h_j越大，表示指标在评价中重要性越大。

④ 计算权重结果。

$w_j=\frac{h_j}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{h}_j}}$ (6)

3) 计算区域内各城市应急物流能力评价值。

$y_i={\displaystyle \underset{j=1}{\overset{n}{\sum }}{w}_j}\times p_{ij}$ (7)

3.3. 熵权模型结果分析

Table 1. Evaluation index information entropy and weight

表1. 评价指标信息熵值与权重

依据上文建立的区域应急物流能力评价指标体系，将统计数据代入熵权评价模型求得各指标对应的信息熵值和权重，如表1所示；以及河南省18个地区应急物流能力综合评价指数，将各地区综合评价数按降序排列，如表2所示。

Table 2. Comprehensive evaluation index of emergency logistics capacity in various regions of Henan province

表2. 河南省各地应急物流能力综合评价指数

为了进一步分析河南省整体与各地方应急物流能力状况，本文采用Ward法–聚类分析对表2中各地区综合评价指数进行分类处理。

由图1聚类谱系图分析可知，河南省各地区根据应急物流能力可分为四大类。因此，在进行河南省应急物流中心选址时，应急物流中心的数量和位置应尽量向郑州、南阳、洛阳、周口、商丘和焦作等地区倾斜，适当的偏离新乡、驻马店、信阳、平顶山等地区，开封、鹤壁等地区不予考虑，以达到节省投入资金，降低建设成本的目的。

Figure 1. Cluster genealogy of evaluation index for various regions in Henan province

图1. 河南各地区评价指数聚类谱系图

4. 构建选址模型

4.1. 问题描述

自然灾害发生后，应急物流需要在有限的时间、空间及资金、人力物力等条件下将应急物资及时送到灾区。这就需要应急物流中心的选址科学合理，综合考虑应急救援效率和应急救援成本，文章将根据每个受灾点其受灾严重程度产生的需求差异，进而产生的救援时间要求设为约束条件，在满足该时间约束条件下，采用权重距离最短化来表示应急效率最大化的模型目标，其中权重采用受灾点的需求量进行表示。在拟建的选址模型中，第一阶段应急物流能力较强的14个城市作为物资供应备选点，需求点为区域内其他所有城市。再建立带有时间约束和容量限制的选址–分配模型，要求在满足所有约束条件下，确定具体选址位置和应急物资分配方案，最终使得目标函数值达到最优，从而使应急效率最大化。

4.2. 模型假设

1) 文章所研究问题是静态问题。2) 应急物流中心至受灾点的运输方式为公路运输，并具备可通达性。3) 运输物资车辆的速度和受灾需求点的需求量已知。4) 应急物流中心和受灾需求点的地理位置已知。5) 运输物资车辆足够多。6) 各应急物流中心的物资储备容量上限已知，应急物流中心可正常运转不受灾害影响。7) 应急救援时间由应急物流中心响应时间、应急物流中心至受灾点的运输时间构成。

4.3. 模型参数与变量定义

4.3.1. 集合含义

I：备选点集合， $I=\left\{\text{1},\text{2},\cdots ,n\right\}$ ；

J：受灾需求点集合， $J=\left\{\text{1},\text{2},\cdots ,m\right\}$ ；

Q：区域所有点集合， $Q=\left\{1,2,\cdots ,m+n\right\}$ 。

4.3.2. 参数含义

h_j：受灾点的物资需求量， $j\in J$ ；

g_ij：备选点i至受灾需求点j的物资运输量， $i\in Q$ ， $j\in Q$ ；

p_ij：备选点i至受灾需求点j的距离， $i\in Q$ ， $j\in Q$ ；

通过欧式距离计算求得，其中 $p_{ij}=\sqrt{{\left(c_i-d_i\right)}^2+{\left(c_j-d_j\right)}^2}$ ，(c_i,c_j)和(d_i,d_j)分别表示备选点与受灾需求点的坐标；

v：运输物资车辆的运行速度；

o：允许建设应急物流中心的数量；

e_i：备选点i的应急物流中心的应急响应时间， $i\in I$ ；

r_ij：备选点i至受灾需求点j的运输时间，其中 $r_{ij}=\frac{d_{ij}}{v}$ ， $i\in Q$ ， $j\in Q$ ；

t_ij：备选点i至受灾需求点j的应急救援时间， $i\in Q$ ， $j\in Q$ ；

K_i：备选点应急物流中心最大容量限制， $i\in I$ ；

T_j：受灾需求点j能接受的最长救援等待时间， $j\in J$ 。

4.3.3. 决策变量

$x_i=\left\{0,\text{1}\right\}$ ，在第i个备选点建立应急物流中心时x_i = 1，否则为0；

$y_{ij}=\left\{0,\text{1}\right\}$ ，第i个备选点上的应急物流中心向受灾需求点j提供服务时y_ij = 1，否则为0。

4.4. 模型建立

基于以上问题说明和参数设定，选址模型的目标函数如下：

$\min w={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{h}_j}}{p}_{ij}{y}_{ij}$ (8)

约束条件如下：

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{y}_{ij}}=1\text{,}\forall j\in J$ (9)

$y_{ij}\le x_i,\forall i,j\in Q$ (10)

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{x}_i}=o,\forall i\in I$ (11)

$t_{ij}=e_i+u_{ij},\forall i,j\in Q$ (12)

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{g}_{ij}{x}_i}}={\displaystyle \underset{j=1}{\overset{n}{\sum }}{h}_j},\forall i,j\in Q$ (13)

${\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{g}_{ij}}}{y}_{ij}\le K,\forall i,j\in Q$ (14)

$t_{ij}\le T_{ij},\forall i,j\in Q$ (15)

$x_i=\{0,1\},y_{ij}=\{0,1\},\forall i,j\in Q$ (16)

模型中，目标函数(8)为应急物流中心选址–分配模型的总目标，通过令应急物流中心至受灾需求点的加权距离最小化，从而体现应急救援效率最大化；(9)表示任一一个受灾需求点都会满足一个应急物流中心向其提供服务；(10)中有当备选点被选中时，该点建立的应急物流中心才会向受灾需求点提供服务；(11)表示备选点建立应急物流中心的个数限制；(12)表示备选点应急物流中心至受灾点的救援时间为应急物流中心的响应时间加备选点至受灾需求点的运输时间；(13)表示区域内应急物流中心的物资运输量都可以满足受灾需求点的总需求量；(14)表示每个应急物流中心向受灾点分配的物资量不超过其容量限制；(15)表示受灾需求点在最长等待救援时间内可以得到应急物流中心向其提供服务；(16)为决策变量函数。

5. 算法设计

5.1. 编码方法设计

文章构建的选址模型属于NP-hard选址问题，其最大特点是多维、精度高的0~1规划选址问题，文章采用浮点数编码，需要拟建8个应急物流中心，即个体染色体的基因位为模型节点数，基因值为1至8的随机数，当基因位出现某一基因值时，表示在备选点选中并且向该节点供应物资，编码示意图2所示。该方法可保障每个节点都有一个备选供应点对其供应物资，满足物资需求。

Figure 2. Encoding diagram

图2. 编码示意图

5.2. 生成初始种群

针对文章的选址模型，一个种群个体表示一种选址方案，通常计算机会随机生成若干数量初始种群，即若干随机的选址方案，前期种群规模的大小影响着后续选择、交叉、变异等遗传算子和整个计算效率，因此文章将设置不同的种群规模，通过多次实验测试对比，找到适合本模型的种群规模。

5.3. 确定适应度函数

遗传算法中目标函数与适应度函数具有联系和相互作用，通过求得目标函数值便可进行下一步相关搜索，而求目标函数值是建立在评价个体适应度的基础上的。由上述建模可知，文章建立了需求加权距离最小化的目标函数，对应的适应度函数为目标函数的倒数，即：

$f\left(x\right)=\frac{1}{F\left(x\right)}$ (17)

其中，f(x)为适应度函数，F(x)为目标函数。

5.4. 选择算子设计

文章采用轮盘赌的方法对种群个体进行筛选，每个个体的相对适应度类比所占轮盘的面积大小，保证种群个体被选中的概率与个体通过计算的适应度呈正相关。其个体被选概率与适应度函数的映射关系如下：

$p_i=\frac{f\left(x_i\right)}{{\displaystyle \underset{i=1}{\overset{N}{\sum }}f\left(x_i\right)}}$ (18)

其中，N表示种群规模，p_i表示个体i被选中的概率。

5.5. 交叉算子设计

交叉算子是种群多样性、产生新个体的重要遗传操作环节，选择算子设计中被选中的R个群体个体通过随机配对的方式组成R/2个配对小组，然后再采用一定方法进行交叉运算。由于单点交叉中交叉位置相对少，不会过多破坏个体染色体基因表现型的优良模式，对于后续的遗传搜索、算法收敛性都有好的促进作用，因此文章采用单点交叉的方法，单点交叉运算示意图如下图3：

Figure 3. Schematic diagram of single point crossing

图3. 单点交叉示意图

5.6. 变异算子设计

文章采用基本位变异的方法对个体染色体的一个或某几个基因位对应的基因值作变异操作，由于物种变异概率较低，一般在0.001~0.01之间取值，为了符合遗传基本规律和提高局部遗传搜索能力，文章采用基本位变异的单点基因位随机变异方式，即通过设定物种变异概率，随机产生一个随机数替换原有个体染色体某一单点基因位的基因值。

5.7. 终止条件设定

由于迭代次数影响算法的运行时间与目标函数的收敛寻优度，文章设计不同迭代次数，通过实验对比的方法，找到合适的迭代次数。

6. 算例分析

由熵权模型初步选址结果可知应急物流中心备选点为郑州、南阳、洛阳、平顶山等共14个节点，从14个地区选择若干点，满足自身和周围需求点的物资供应。目前，河南省共有38个市和82个县，共计120个节点，将熵权模型剔除的4个地区内的节点作合并处理，共设置109个节点覆盖河南省所有行政区域及常驻人口，节点的经纬度坐标来源于国家地理经纬度网。基于以上数据，109个受灾需求点的需求量及时间窗约束如表3所示。其他数据由于篇幅原因不予体现。

Table 3. Table of material demand and time window constraints for disaster affected demand points

表3. 受灾需求点物资需求量与时间窗约束表

结合上述模型和算法设计，文章设计种群大小为300，最大迭代次数为5000，交叉概率Pm为0.9，变异概率Pc为0.05，并将借助软件Matlab R2016a实现，其中计算机运行配置CPU频率为1.6 Hz~2.0 Hz，安装内存为16 G，操作系统为Windows10。通过进行若干次实验取得一个较为理想的结果，最优选址–分配方案如图4所示。具体选址节点和物资分配方案如表4所示。

由运行结果可知，被选中的节点编号为1、9、19、32、61、73、81、99，分别对应郑州、洛阳、平顶山、新乡、南阳、商丘、信阳、驻马店8个地区，此时模型的目标函数值为109661416.79，该选址–分配方案满足了不同等级应急物流中心容量限制和时间窗约束。

综上所述，具体的选址方案为豫中核心经济区分别在郑州、洛阳、平顶山三个地区建立应急物流中心；豫北地区在新乡市建立一个应急物流中心；豫西地区在南阳市建立一个应急物流中心；豫东地区在商丘市建立一个应急物流中心；豫中南地区在驻马店市建立一个应急物流中心；豫南地区在信阳市建立一个应急物流中心，此外各应急物流中心还要负责各自辖区范围内的应急物资需求节点。上述实验结果可知，河南省提出“十四五”时期将建立“2 + 6”省级和区域性应急物资保障中心共8个应急物流中心，可考虑上述8个地区。

Figure 4. Optimal location allocation plan diagram

图4. 最优选址–分配方案图

Table 4. Emergency logistics center node selection and emergency material distribution volume

表4. 应急物流中心节点选择和应急物资配送量

7. 结论

应急物流中心选址问题是应急物流设施规划与布局中最关键的核心问题，其影响着整个应急物流网络和应急物流体系建设，合理科学的选址是区域提升应急物流能力、发挥应急物流效用的重要工程。本文通过对国内外应急设施选址相关文献的参考与分析，指出应急物流中心选址问题是个系统性的复杂工程，需要全面考虑选址的影响因素、选址方法和实际区域特色，基于此，结合河南省发展现状，选取了区域应急物流能力评价指标，然后采用分阶段选址的研究方法：第一阶段构建区域应急物流能力评价指标体系，并采用熵权综合评价模型对河南省18地区应急物流能力进行客观综合评价，采用Ward聚类法将河南省18地区分为4类，保留前三类共14地区作为初步选址方案。第二阶段构建应急物流中心备选点至受灾需求点需求加权距离最小化的选址–分配模型，并使模型满足受灾点时间窗约束与应急物流中心容量限制的条件，利用遗传算法进行求解，经过若干次实验得出河南省应急物流中心最终选址–分配方案。本文的选址研究使得河南省对自身应急物流发展状况有了更深层次的认识，对于河南省统筹协调该地区的应急物流发展和完善应急物流体系具有推动作用。

NOTES

^*通讯作者。