Multi-objective Approach to Emergency Resource Allocation Using None-dominated Sorting Based Differential Evolution
-
摘要: 应急资源分配（Emergency resource allocation，ERA）是灾害应急管理中的核心环节，主要研究如何高效合理地把各储备点的应急救援物资分配给各发放点.然而，在大规模突发灾害发生后，每个发放点极可能会同时向多个储备点请求多种救援物资，从而带来潜在的应急资源冲突.为此，本文首先构建了考虑应急资源冲突消解的多储备点、多发放点、多种救援物资的应急资源多目标优化模型，并提出了一种基于非支配排序差异演化和编码修正机制的应急资源多目标分配算法.对比实验结果表明，该算法在大规模样本下能够从全局角度同时给出多个发放点的应急资源分配方案，有效实现多个储备点同时为多个发放点协同配备应急资源，而且不会产生任何应急资源冲突，为解决应急资源受限情况下的大规模应急资源分配问题提供了一个有益的尝试.Abstract: Emergency resource allocation (ERA) is a key topic in emergency management for sudden natural disasters, which mainly deals with how to reasonably and efficiently allocate the emergency relief supplies at reserve points to dispatch points. However, when an extraordinarily serious natural disaster occurs, each dispatch point may ask for many different emergency relief supplies at multiple reserve points at the same time, which will bring potential conflicts over emergency resources. To tackle this problem, a multi-objective optimization model is constructed considering multiple reserve points, multiple dispatch points, multiple emergency resources and emergency resource conflicts resolution. In addition, a multi-objective optimization algorithm for ERA is developed by using none-dominated sorting based differential evolution and encoding repair mechanism. Finally, comparative experimental results from large-scale samples show that our approach can deal with the ERA problem from an overall point of view, simultaneously give the allocation schemes of multiple reserve points for multiple dispatch points, realize different reserve points cooperate with each other on ERA for different dispatch points without any emergency resource conflict, which may provide a useful attempt to solve large-scale ERA problems under limited emergency resources.
-
近年来, 地震、洪水、泥石流、台风等自然灾害对人类社会造成的损失越来越严重.例如, 2008年汶川7.9级大地震造成69 225人死亡, 379 640人受伤, 17 939人失踪, 至少500万人无家可归, 经济损失达1 000亿美元[1-2].因此, 灾害应急管理作为一门新兴的研究领域正引起各国政府和学者的高度关注[3], 并已在灾情评估[4-5]、应急资源储备[6]和分配[7]、应急疏散路径选择[8-9]、应急能力评价[10]和应急方案评估[11]等方面展开了研究.其中, 应急资源分配(Emergency resource allocation, ERA) 是灾害应急管理的核心环节, 是应对灾害突发事件和开展灾害救援的基础, 主要研究如何在灾害发生时迅速有效地利用智能决策理论和计算机辅助工具, 高效合理地把各储备点(Reserve points) 的应急救援物资(Emergency relief supplies) 分配给各发放点(Dispatch points), 最大程度地减少灾害带来的损失[7].
1. 相关工作分析
ERA方案的优劣直接决定了应急救援的成功与否, 对保护人民生命财产安全、减少社会危害和经济损失具有重要的现实意义.因此, 国内外学者已对ERA问题开展了大量的研究.
Fiedrich等[12]构建了一种针对地震灾后, 以资源为约束、以最大化应急资源的利用率为目标的应急资源分配模型. Sherali等[13]从考虑公平性入手, 构建了以资源为约束、以最小化灾害风险为目标的线型规划模型. Arora等[14]针对医疗应急资源分配展开研究, 建立了在费用约束的情况下以最大化救助率为目标的优化模型, 但模型只考虑了一个物资储备点一种应急资源的情况. Zhu等[15]构建了一种以药品资源为约束, 最小化各发放点不满足度的单目标优化模型, 在模型中也只考虑了一种应急资源. Peng等[16]针对灾害发生时需求不确定的情况, 基于灰色预测和情景分析的方法对各发放点所需的应急资源进行预测, 但并没有给出具体的应急资源分配方法. Wang等[17]考虑到应急资源有限, 构建了一种基于工作流的决策模型, 按照最小应急资源需求量的原则决定每个发放点的分配顺序和应急资源量, 但是其模型中的最小应急资源需求量如何确定非常困难, 而且也没有考虑多种应急资源的情形. Wang等[18]将应急资源选址与分配结合在一起, 建立了资源约束的单目标双层线性规划模型, 并采用粒子群优化预予求解, 但是其模型局限于某一区域的物资储备点只能响应该区域内的发放点, 而且也没有考虑分配过程中可能产生的应急资源冲突问题. Yang等[19]首先构建了一种多发放点、多储备点、多种应急资源的动态分配模型, 在不同时间段内进行应急资源的分配.但是, 其方法只是简单地在不同的时间段内分别优化, 属于分阶段静态优化, 而且虽然在模型中考虑了应急效果和成本这两个目标, 但在具体求解过程中仍然采用的是加权单目标优化. Altay[20]根据储备点的应急资源总量与发放点的需求量之间的关系, 分别构建了两种基于能力的整数规划模型解决多种应急资源分配问题, 但是并没有给出具体的求解方法, 也没有考虑多发放点之间的应急资源冲突问题. Wang等[21]考虑应急任务的重要性和相互关系, 基于雪球效应构建了一种应急任务网络, 然后通过对应急任务网络的分析实现了单种应急资源的分配. Wex等[22]构建了一种针对多发放点、以最小化总完成时间为目标的应急资源分配模型, 但仍然只考虑单种应急资源. Liu等[23]基于Petri网构建多种应急资源在不同应急周期内的分配模型, 并设计了有效的机制来检测不同周期内可能的应急资源冲突, 但此模型局限于单发放点的应急需求. Zhang等[24-25]针对多发放点构建了多种应急资源分配模型, 并基于图论中的网络优化方法和线性规划优化思想设计了一种启发式搜索算法进行求解, 但其方法为了解决应急资源冲突问题, 只是简单地对各发放点的需求按照串行顺序依次进行求解, 在大规模样本下求解效率较低, 而且会带来极大的计算开销. Wang等[26]基于非合作博弈理论构建了多发放点多种应急资源的分配模型, 并采用蚁群优化进行求解, 但是其方法只考虑多个发放点同时竞争单个物资储备点的应急资源.大连理工大学的王旭坪等[27-29]在应急资源分配中分别考虑了公众心理风险感知程度、物资未满足度、时间满意度、需求满意度、效用满意度、灾民损失和车辆调度费用等因素.浙江大学的刘南等[30-31]基于贝叶斯理论构建了多储备点、多发放点、多阶段应急资源分配模型, 并采用遗传算法进行求解.此外, 清华大学、西安电子科技大学、南京航空航天大学、重庆大学等高校的研究团队[32-38]也从不同的层面对应急资源分配问题进行了研究.但是, 在这些工作中, 或者考虑单一应急资源的分配, 或者假设应急资源是无限的, 或者对多发放点之间的应急需求按照优先级以串行的方式依次进行分配以避免多发放点之间的救援物资竞争, 极大影响了应急资源分配的效率, 难以适应大规模应急场景.
事实上, 在实际的应急决策情境中, 应急资源通常是多种多样的, 同一储备点通常会存储多种应急资源, 而同一种应急资源也常常会存储在不同的储备点.而且, 一个救援物资发放点可能同时需要多个储备点为其提供多种应急资源, 而单个储备点又可能同时为不同发放点提供多种不同的应急救援物资.因此, 多储备点、多发放点和多种救援物资的ERA问题是一个极其复杂的组合优化问题.尤其是当一个发放点同时向多个储备点发出救援物资请求时, 多个储备点提供的应急资源总量一般很容易满足该发放点的需求, 但是当多个发放点同时向同一个物资储备点发出应急请求时, 由于该储备点的某些应急资源有限, 不可能同时满足这么多个发放点的应急需求, 这时就会发生应急资源冲突.因此, 如何在ERA问题建模和求解时实现应急资源冲突消解是一个值得深入研究而又极具应用价值的课题.
基于上述背景, 本文在整理和分析已有工作的基础上, 首先构建了考虑应急资源冲突消解的多储备点、多发放点、多种救援物资的ERA多目标优化模型, 并设计了一种基于非支配排序差异演化和编码修正机制的ERA多目标求解算法, 最后通过对比实验验证了本文方法的有效性.
2. 问题分析与建模
对于多储备点、多发放点、多种救援物资的ERA问题, 其难点在于如何在储备点应急资源有限的情况下, 解决各发放点对关键应急资源的需求冲突问题.为此, 本文引入合作博弈论中的“协作联盟”[39-40]概念以期实现多种救援力量的统筹调度和协同作战.当大规模自然灾害发生后, 把多个储备点的应急资源融合在一起, 快速有效地组成一个团队来满足发放点的应急资源需求, 如图 1所示, 我们把这样的团队称为应急联盟(Emergency coalition, EC).
EC是在大规模自然灾害发生后, 各储备点为迅速响应灾害救援而快速结成的动态协作联盟.联盟中的这些储备点通常称之为合作伙伴, 每个伙伴在各自的优势领域(如物资供给、医疗服务、救助设备等) 为EC贡献自己的核心应急资源, 相互联合起来实现优势互补和应急资源共享.
据此, 多储备点、多发放点、多种救援物资的ERA问题就是为每个发放点快速寻找EC.其中, 应急响应时间通常是衡量EC性能的首要目标.为了及时响应救援需求, 一个储备点可能同时为多个发放点供应多种应急资源, 而一个发放点可能同时需要多个储备点的多种应急资源.也就是说, 只要储备点拥有足够多的应急资源, 则允许其参与多个EC.同时, 如果一个EC的应急资源充分, 则允许其负责多个发放点的救援.显然, 这样的情形可以最大限度地提高应急资源的利用率.
但是, 当一个储备点同时需要为多个发放点提供多种应急资源时, 首先需要考虑的是如何将该储备点的有限资源在多个EC之间合理地配置以避免应急资源冲突和实现最大的救援效果.如果应急资源分配不当, 使得某些灾害点的应急救援物资缺乏, 则会造成灾害损失的进一步加大, 相反的, 如果对某些灾害点供应救援物资过多, 则会导致应急资源浪费.
此外, 随着应急救援任务的推进, 参与救援的储备点及其可提供的应急资源数量不断增加, 同时地域差异还可能带来不同的应急资源成本和运输成本, 因此, ERA问题还需要考虑如何选择合适的储备点来降低应急成本.
综上, 在对多储备点、多发放点、多种救援物资的ERA问题进行建模时, 需要同时考虑应急响应时间和应急成本两个目标, 并能在模型中刻画和描述每个储备点对每个发放点的实际应急资源贡献量以实现应急资源冲突消解.
2.1 数学模型
ERA问题的建模与求解主要是为国家高效、有序地应对突发灾害提供科学的决策参考, 因此, 和已有工作一样[12-38], 我们首先可作如下考虑: 1) 大规模自然灾害发生后, 存在多个需要响应的应急救援物资发放点; 2) 应急专家根据受灾情况可以粗略估算出各发放点所需要的应急资源种类和数量, 并以整数计数, 即应急资源需求量是一个定量值; 3) 存在多个分布于不同地域的应急救援物资储备点, 且每个储备点拥有有限的救援物资种类和数量(定量), 并以整数计数; 4) 同一种类的应急救援物资由于地域性等差异, 在各储备点具有不同的单位成本(包含购买、存储、维护等), 并以整数计数; 5) 由于地域性等差异, 对于每种救援物资, 从各储备点运输到各发放点分别具有不同的运输成本, 并以整数计数; 6) 依据各储备点到各发放点的广义时间距离(以整数计数) 来设定应急响应时间, 暂不考虑其他影响因素.
基于上述思想, 我们给出如下定义:
定义 1. $T = \{ t_1, \cdots, t_j, \cdots, t_m \}$ 表示m个救援物资发放点, $j \in \{1, \cdots, m\}$ , $m\in \bf{N}$ .
定义 2. 表示 $t_j$ 对r种应急资源的需求量, 其中, 以整数计数, 表示 $t_j$ 对第k种应急资源的需求量, , r $\in \bf{N}$ .
定义 3. $\pi_j\geq 0$ 为 $t_j$ 的应急响应时间要求, 以整数计数, 表示应急资源必须在应急响应时间 $\pi_j$ 内到达发放点 $t_j$ .
定义 4. 表示n个物资储备点, $i\in \{1, \cdots, n\}$ , .
定义 5. 表示 $a_i$ 对r种应急资源的储备量, 其中, $b_k^i\geq 0$ 以整数计数, 表示储备点 $a_i$ 对第k种应急资源的储备量.
需要注意的是, 考虑到应急物资之间本身的替换性和搭配性, 不同储备点和发放点的 $d_k^j$ 和 $b_k^i$ 可以根据实际物资储备和应急需求动态调整, 决策者可以根据需要进行自由设置和搭配.例如, 现考虑大米、面粉、水、帐篷、棉被5种应急物资, 储备点1有5吨大米、1吨水, 则 ${\pmb B}_1 = [5,0,1,0,0]$ (假设食物以“吨”为单位), 储备点2有1吨面粉、1 000顶帐篷, 则 (假设帐篷以“千顶”为单位), 储备点3有1 000张棉被, 则 ${\pmb B}_3 = [0,0,0,0,1]$ (假设棉被以“千张”为单位).
定义 6. $C_j\subseteq A$ , $C_j\neq\emptyset$ , 表示为响应发放点 $t_j$ 而组成的应急联盟. 表示应急联盟 $C_j$ 中成员所贡献的救援物资总量, 其中, 以整数计数, 表示 $C_j$ 对第k种应急资源的拥有量.显然, $C_j$ 是有效的, 当且仅当对 $\forall k \in \{1$ , $\cdots$ , $r\}$ , 满足 $b_k^{C_j }\geq d_k^j$ , 即 ${\pmb B}^{C_j }\geq {\pmb D}_j$ .
定义 7. 为了刻画每个储备点在各个发放点上的救援物资贡献状况, 设储备点 $a_i$ 对发放点 $t_j$ 的实际应急资源贡献量为, 其中, 以整数计数, 为 $a_i$ 向 $t_j$ 实际提供的第k种应急资源量.显然对 $\forall k \in \{1, \cdots, r\}$ , $w^{ij}_k \leq b^i_k$ , 且 $b_k^{C_j } = \sum\nolimits_{a_i\in C_j}{w^{ij}_k}$ .注意, 如果 ${\pmb W}^{ij}=0$ , 则表示 $a_i$ 没有参与 $C_j$ .
定义 8. 表示救援物资单位成本向量, 其中, $\phi^i_k\geq 0$ 以整数计数, 表示 $a_i$ 储备的第k种救援物资的单位成本.
定义 9. 表示单位运输成本向量, 其中, $\theta^{ij}_k\geq 0$ 以整数计数, 表示第k种应急资源从 $a_i$ 运输到 $t_j$ 的单位运输成本.
定义 10. $\mathbf{\Gamma}_i=[\gamma^{i1}, \cdots, \gamma^{ij}, \cdots, \gamma^{im}]$ 表示 $a_i$ 与各发放点之间的单位广义时间距离, 其中, 以整数计数, 表示单位应急资源从储备点 $a_i$ 到发放点 $t_j$ 的响应时间.
基于上述定义, 多储备点、多发放点、多种救援物资的ERA问题可描述为
$ \min f_1 =\displaystyle{ \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {\left( { \gamma ^{ij} \times\sum\limits_{k = 1}^r {w_k^{ij} } } \right)} } }\notag \\[2mm] \min f_2 =\displaystyle{ \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {\sum\limits_{k = 1}^r {{[(\phi _k^i+\theta^{ij}_k) \times w_k^{ij} } } ]} }}\\ \,{\rm s.t.}\notag $
(1) $ \displaystyle\sum\limits_{j = 1}^m {{\pmb D}_j } \le \sum\limits_{i = 1}^n {{\pmb B}_i } $
(2) $ \displaystyle\sum\limits_{i = 1}^n {{\pmb W}^{ij} = {\pmb D}_j},\ \,j \in \{1,\cdots,m\} $
(3) $ \displaystyle\sum\limits_{j = 1}^m {{\pmb W}^{ij} } \le {\pmb B}_i,\ \,i \in \{1,\cdots,n\} $
(4) $ %\begin{equation}\hfill \setcounter{equation}{5} \sum\limits_{i = 1}^n {\left( {\gamma ^{ij} \times \sum\limits_{k = 1}^r {w_k^{ij} } } \right) \le \pi _j },\ \,j \in \{1,\cdots,m\} %\end{equation} $
(5) 其中, 目标函数 $f_1$ 表示应急资源的应急响应总时间, 目标函数 $f_2$ 表示应急资源总成本(包含救援物资成本和运输成本).约束条件(2) 表示所有储备点的应急资源量之和必须能够满足所有发放点的救援物资总需求, 注意, 在应急响应初期, 这一条件不一定能严格满足, 这时可以通过调整和缩小各发放点的物资需求量以期满足这一约束, 以保证优化算法可以顺利执行, 发放点未达的应急需求可以在储备点救援物资充实后再次进行优化.约束条件(3) 表示应急联盟 $C_j$ 的应急资源持有量要能满足发放点 $t_j$ 的应急需求.约束条件(4) 表示储备点向其响应的所有发放点实际贡献的应急资源量之和不能超过其自身的应急资源储备量.约束条件(5) 表示应急联盟 $C_j$ 的响应时间不能超过发放点 $t_j$ 的响应时间需求.
2.2 模型分析
由第2.1节可以看出, 本文针对多储备点、多发放点、多种救援物资的ERA问题所构建的模型, 既允许各储备点自由竞争救援任务, 又能充分考虑各储备点的应急资源负荷状况.而且, 式(1) 是一个多目标优化问题(Multi-objective optimization problems)[41], 如下所示:
$ \max {\pmb z}= f({\pmb x})= (f_1({\pmb x}),f_2({\pmb x}), \cdots ,f_{p}({\pmb x}))\notag\\ \,\rm {s.t.}\notag \\ \qquad \begin{cases} e({\pmb x})= (e_1({\pmb x}),e_2({\pmb x}), \cdots ,e_{q}({\pmb x}))\leq 0\\ {\pmb x}= (x_1,x_2,\cdots ,x_n ) \in {\pmb X}\\ {\pmb z}= (z_1,z_2,\cdots ,z_n ) \in {\pmb Z} \end{cases} $
(6) 其中, ${\pmb x}$ , ${\pmb X}$ , ${\pmb z}$ 和分别称为决策向量、决策空间、目标向量和目标空间. 为待求解问题的第l个目标函数, $l=1, \cdots, p$ . 为待求解问题的第s个约束条件, $s=1, \cdots, q$ .
若一个决策向量 ${\pmb x}$ 同时满足q个约束条件, 则称其是一个可行解(Feasible solutions).所有可行解的集合称为可行解集(Feasible solution set).设和 ${\pmb x}_2$ 为两个可行解集, 如果 $\forall l = 1, \cdots, p$ , 有 $f_l({\pmb x}_1) \geq f_l({\pmb x}_2)$ , 且, 满足, 则称 ${\pmb x}_1$ 支配 ${\pmb x}_2$ , 记为 ${\pmb x}_1 \succ {\pmb x}_2$ [41].
在可行解集中, 如果满足 $\neg \exists {\pmb x} \in {\pmb X}_f$ , ${\pmb x} \succ {\pmb x}^\ast$ , 则称 ${\pmb x}^\ast$ 为Pareto最优解.所有Pareto最优解的集合称为Pareto最优解集, Pareto最优解集相对应的目标函数向量所构成的集合被称为Pareto前沿.对于多目标优化问题, 最终的目的是寻找或逼近问题的Pareto最优解集以及Pareto前沿.因此, 衡量一个多目标优化算法的标准通常是看它能否找到或很好地逼近问题的Pareto最优解集[41].
在求解多目标优化问题时, 传统的方法是将多个目标转化为单个目标, 再利用单目标优化方法预予求解, 但这种方法难以实现真正的多目标.近年来, 研究者基于Pareto解集概念已发展了多种多目标优化方法, 如非支配排序遗传算法(Non-dominated sorting genetic algorithm, NSGA)[41]、改进的NSGA-Ⅱ[42]、多目标粒子群优化[43]等.其中, NSGA-Ⅱ无论是在一系列测试函数上, 还是在电网规划、软件测试等实际应用中都表现了超强的性能[44-46], 已经成为解决多目标优化问题的标准选择方案.但是NSGA-Ⅱ是在标准遗传算法基础上加入非支配排序机制设计而成的, 与遗传算法相比, 差异演化(Differential evolution, DE)[47-48]无论是进化速度还是搜索结果都要优于遗传算法.因此, 我们尝试利用NSGA-Ⅱ中的非支配排序机制来提高DE的多目标优化性能, 并根据ERA数学模型中各分量之间的内在联系来修正非法编码, 拟提出一种带有编码修正机制的非支配排序差异演化算法(Encoding repair and none-dominated sorting based differential evolution, ERNS-DE) 来求解本文的多目标ERA问题.
3. 基于ERNS-DE求解多目标ERA
本节首先给出标准的DE/rand/2/bin算法[47], 然后给出编码修正机制, 推演了编码修正机制的若干重要性质, 并详细介绍了变异操作、交叉操作和基于非支配排序的选择操作, 最后给出具体的ERNS-DE算法步骤.
3.1 标准DE算法
DE算法是模拟个体进化的随机计算模型, 通过设计目标函数, 能让对环境适应能力强的个体存活下来, 而对环境适应低的个体会被淘汰, 符合适者生存的规律[47].由于DE算法使用实数编码, 在解的质量上能达到很高的精度, 适合求解一些规模较大的问题, 已被应用到许多学科[49-50].标准DE算法一般包含变异、交叉、选择等算子, 基本流程图如图 2所示.
3.2 参数预处理
如果, 则所有储备点的应急资源总量不能满足所有发放点的需求, 如前所述, 在应急决策中, 为了尽可能地减少灾害损失, 对所有发放点都应该有所响应, 而不能舍弃某些发放点的请求, 因此, 需要对T中的所有 $t_j$ 的应急需求进行适当缩减, 即
For $j:=1$ to m do
For $k:=1$ to r do
End For
End For
通过上述缩放处理很容易验证, , 从而可以保证DE算法的顺利执行.
3.3 编码方案与种群初始化
从直观上看, 考虑多储备点、多发放点和多种救援物资的ERA问题恰似一个二维组合优化问题.而二维整数向量编码不仅方式简单、容易理解, 而且从根本上与本文的ERA问题的二维本质相适应, 从而为问题的求解奠定了良好的基础, 并为设计出性能优良的搜索算法提供了极为广阔的空间, 因此本文将每个个体从传统的一维实数编码扩充到二维整数向量编码.
如图 3所示, 每一行代表一个储备点, 每一列代表一个发放点, 第i行第j列的元素 ${\pmb W}^{ij} =[w^{ij}_1$ , $\cdots$ , $w^{ij}_k$ , $\cdots$ , $w^{ij}_r]$ 表示储备点 $a_i$ 向发放点 $t_j$ 提供的实际应急资源量.如果 ${\pmb W}^{ij}>0$ , 则储备点 $a_i$ 参与了发放点 $t_j$ 的救援, .如果 ${\pmb W}^{ij}=0$ , 则 $a_i$ 没有响应发放点 $t_j$ 的应急需求, $a_i \notin C_j$ .
假设种群规模为 $PS$ , 初始种群中的每个个体的编码按照如下方式生成:
For $i:=1$ to n do
For $j:=1$ to m do
For $k:=1$ to r do
$w^{ij}_k\leftarrow {\rm rand}[0, \min\{b^i_k, d^j_k\}]$
End For
End For
End For
其中, 表示在 $[0, \min\{b^i_k, d^j_k\}]$ 之间生成一个随机整数.
虽然这种编码生成方式可以保证储备点 $a_i$ 向发放点 $t_j$ 实际提供的应急资源量不超过自身所拥有的资源量 ${\pmb B}_i$ , 但是, 对于每个个体来说, 可能存在以下两种情况:
1) 对于每一列来说, 如果 $\exists k \in \{1, \cdots, r\}$ , 使得 $b_k^{C_j}< d_k^j$ , 即 $C_j$ 中的所有成员对发放点 $t_j$ 贡献的应急资源量之和不能满足 $t_j$ 的应急需求, 这时应急联盟 $C_j$ 是无效的, 该编码即为一个非法编码.
2) 对于每一行来说, 如果 $\exists k \in \{1, \cdots, r\}$ , $\exists i$ $\in \{1$ , $\cdots$ , $n\}$ , 使得 $\sum\nolimits_{j=1}^m{w^{ij}_k}>b^i_k$ , 即储备点 $a_i$ 为其参与的发放点提供的应急资源量之和超出了其自身的应急资源拥有量, 这时就会产生应急资源冲突, 该编码也是非法的.
其实, 对于任一编码来说, 上述问题中的任何一个都会导致其成为非法个体.而大量的非法编码不利于解的探索, 会大大延缓算法的进化, 降低算法的求解效率.因此, 如何把非法编码修正为一个合法编码是我们需要面对的一个首要问题.
3.4 编码修正机制
正如前述, 不对编码进行修正, 不解决编码中潜在的应急资源冲突问题, 我们根本无法知道哪些储备点响应了哪些发放点的请求, 也就无法同时给出多个发放点的救援物资分配方案.编码修正的目的就是为了确保为每一个发放点找到一个合法的应急联盟, 同时每一个储备点不存在任何应急资源冲突.因此, 在修正过程中必须动态跟踪每个储备点 $a_i$ 对其响应的发放点 $t_j$ 的实际应急资源贡献量, 以及 $a_i$ 当前可用的应急资源储备量 ${\pmb B}_i$ , 一旦 $a_i$ 的当前应急资源储备量 ${\pmb B}_i=0$ , 则 $a_i$ 将不再响应其他发放点的应急请求.
基于上述思想, 编码修正机制如下:
步骤 1. 随机选择一个未分配的发放点 $t_j$ (即随机选择一个还未检查过的列j), $C_j\leftarrow \emptyset$ .对 $\forall k= 1$ , $\cdots$ , r:
步骤 1.1. 对 $\forall i=1, \cdots, n$ , 如果, $w_k^{ij} \leftarrow b_k^i$ .
步骤 1.2. 如果, 即储备点目前提供的应急资源不能满足发放点 $t_j$ 对第k种救援物资的需求, 则在第j列随机选择一个储备点 $a_{i^\ast}$ , 满足, 执行
$ w_k^{i^\ast j}\leftarrow\min\left\{w_k^{i^\ast j}+\left(d^k_j-\sum\limits_{i = 1}^n w_k^{ij}\right), b_k^{i^\ast}\right\} $
(7) 重复这个步骤, 直到 $\sum\nolimits_{i = 1}^n w_k^{ij}=d^k_j$ .
步骤 1.3. 如果, 即储备点目前提供的应急资源超出了发放点 $t_j$ 对第k种救援物资的需求, 则在第j列随机选择一个储备点 $a_{i^\ast}$ , 满足 $w_k^{i^\ast j} >$ $0$ , 执行
$ w_k^{i^\ast j}\leftarrow \max\left\{0,w_k^{i^\ast j}-\left(\sum\limits_{i = 1}^n w_k^{ij} - d^k_j\right) \right\} $
(8) 重复这个步骤, 直到 $\sum\nolimits_{i = 1}^n w_k^{ij}=d^k_j$ .
步骤 1.4. 对 $\forall i=1, \cdots, n$ , 如果 $w_k^{ij}>0$ , $b^k_i \leftarrow b^k_i-w_k^{ij}$ .
步骤 2. 对 $\forall i=1, \cdots, n$ , 如果, 则 $C_j \leftarrow C_j \cup \{a_i\}$ .
步骤 3. 如果所有发放点分配完毕(即所有列检完毕), 则结束编码修正, 否则转步骤1继续进行.
经过上述编码修正, 任一个非法编码都能调整为一个合法的编码(见命题1).此外, 步骤1.4是为了实时更新各储备点当前可用的应急资源量, 步骤1.1可以确保对于后续列的检查均是基于各储备点当前可用的应急资源量, 从而有效避免应急资源冲突问题(见命题2).而且, 在修正过程中, 计算每个储备点的实际应急资源贡献量 $w_k^{ij}$ 是为了确保候选储备点提供的应急资源总量恰好满足所对应发放点的应急需求, 以杜绝应急资源的浪费, 而且可以实现应急资源量多的储备点多贡献, 体现能者多劳, 从而减少候选储备点的规模, 利于应急救援活动的有效和迅速展开, 同时, 节省下来的剩余应急资源可以响应其他发放点, 从而尽可能地满足更多的应急需求, 计算简单有效, 额外开销少(见命题3).
命题 1. 只要满足, 则任一个非法编码都能修正为一个合法的编码.
证明. 本文设计的编码修正机制旨在满足T中的每个发放点, 因此, 从列的角度采用数学归纳法加以证明.
当 $m=1$ 时, 编码中仅有一列, 即只存在一个发放点, 又因为 $\sum\nolimits_{{a_i} \in A} {\pmb B}_i \geq {\pmb D}$ , 此时只需要根据 ${\pmb D}$ 的多少, 让有限的储备点贡献应急资源即可满足该发放点的应急需求.
现假设当 $m=m^\ast-1$ 时命题成立, 即 $n \times (m^\ast -$ $1)$ 的编码能被调整为一个合法编码, 即修正后的 $m^\ast-1$ 列均为有效列.此时, 只需证明当 $s=m^\ast$ 时命题成立即可.
当 $m=m^\ast$ 时, 由假设可知, 编码中至少有 $m^\ast - 1$ 列(不妨设前 $m^\ast-1$ 列) 可以被修正为有效列, 只需证明剩下的一列(即第 $m^\ast$ 列) 也能被修正为一个有效列即可.
因为编码修正能够确保候选储备点提供的应急资源总量恰好满足所对应发放点的应急需求, 所以对于前 $m^\ast-1$ 列, 有
$ \sum\limits_{j = 1}^{m^\ast-1} \sum\limits_{i = 1}^n { {{{\pmb W}}^{ij} } = \sum\limits_{j = 1}^{m^\ast-1}{{\pmb D}}_j} $
又因为
$ \sum\limits_{i = 1}^n {{\pmb W}}^{ij} \geq \sum\limits_{j = 1}^{m^\ast}{{\pmb D}}_j $
则
$ \sum\limits_{i = 1}^n {{\pmb W}}^{ij}- \sum\limits_{j = 1}^{m^\ast-1} \sum\limits_{i = 1}^n {\pmb W}^{ij} \geq \sum\limits_{j = 1}^{m^\ast}{{\pmb D}_j}-\sum\limits_{j = 1}^{m^\ast-1}{{\pmb D}_j} $
即
$ \sum\limits_{i = 1}^n {{\pmb W}}^{ij}- \sum\limits_{j = 1}^{m^\ast-1} \sum\limits_{i = 1}^n {\pmb W}^{ij} \geq {\pmb D}_{m^\ast} $
从上式可以得到, 储备点在响应了前 $m^\ast-1$ 个发放点之后的剩余应急资源量之和仍然能够满足第 $m^\ast$ 个发放点的需求, 可以按照编码修正机制轻松完成 $t_{m^\ast}$ 的分配.因此, 当 $m=m^\ast$ 时, $n\times m^\ast$ 的编码也能被修正为一个合法编码,
命题 2. 经过编码修正后的合法编码中不存在任何应急资源冲突.
证明. 要证明修正后的编码不存在任何应急资源冲突, 需要证明对于 $\forall a_i \in A$ , 都满足
$ \sum\limits_{j = 1}^m {{\pmb W}}^{ij}\leq {\pmb B}_i $
在编码修正机制中, $a_i$ 参与后续列的前提是其当前应急资源储备量 ${\pmb B}_i > 0$ , 否则 $a_i$ 将不再响应其他发放点的应急请求.不妨设 $a_i$ 参与发放点 $t_j$ 后的当前应急资源储备量为
$ {\pmb B}^j_i = {\pmb B}^{j-1}_i - {{\pmb W}}^{ij}\geq 0 $
其中, 为 $a_i$ 参与发放点 $t_{j-1}$ 后的当前应急资源储备量, 满足
$ {\pmb W}^{ij} = {\pmb B}^{j-1}_i - {\pmb B}^j_i \geq 0 $
由上式可得
$ \sum\limits_{j = 1}^{m}{{\pmb W}}^{ij} = \sum\limits_{j = 1}^{m} ({\pmb B}^{j-1}_i - {\pmb B}^j_i) \geq 0 $
又因为
$ \sum\limits_{j = 1}^{m} ({\pmb B}^{j-1}_i - {\pmb B}^j_i) =\\ \ \,({\pmb B}^{0}_i - {\pmb B}^1_i)+ ({\pmb B}^{1}_i - {\pmb B}^2_i)+ \cdots +({\pmb B}^{m-1}_i - {\pmb B}^m_i)=\\ \ \,{\pmb B}^{0}_i - {\pmb B}^m_i $
所以有
$ \sum\limits_{j = 1}^{m}{{\pmb W}}^{ij}={\pmb B}^{0}_i - {\pmb B}^m_i $
其中, ${\pmb B}^{0}_i$ 为初始时刻的应急资源储备量, 即, 而为响应了m个发放点后剩余的应急资源储备量, 满足, 因此有
$ {\pmb B}_i - \sum\limits_{j = 1}^{m}{{\pmb W}}^{ij}\geq 0 $
即
$ \sum\limits_{j = 1}^m {{\pmb W}}^{ij}\leq {\pmb B}_i $
命题 3. 编码修正机制的计算复杂度至多为 ${\rm O}(n^3)$ .
证明 . 本文设计的编码修正机制的计算复杂度主要集中在步骤1, 最多需要分配m个发放点, 而对于每个发放点, 又需要检查r种救援物资是否满足应急需求.具体来说, 对于第k种救援物资, 如果 $\sum\nolimits_{i = 1}^n w_k^{ij}<d^k_j$ , 则在步骤1.2中至多需要挑选n个新的储备点加入应急联盟才能实现.如果, 则在步骤1.3中, 至少要在应急联盟中保留一个储备点, 因此至多只可能挑选n -1个储备点不再贡献第k种救援物资给发放点 $t_j$ .显然, 编码修正机制的计算复杂度至多为 ${\rm O}(m\times r \times n) ={\rm O}(n^3)$ .
为了进一步验证编码修正机制的有效性, 下面以一个实例进行详细说明.假设有4个储备点 $a_1$ , $a_2$ , $a_3$ 和 $a_4$ , 各自的救援物资储备量为
$ \pmb{B}_1=[5,3],\,\,\,\,\pmb{B}_2=[4,4],\,\,\,\,\pmb{B}_3=[6,2],\,\,\,\,\pmb{B}_4=[3,8] $
此外, 假设有3个发放点 $t_1$ , $t_2$ , $t_3$ 提出了应急请求, 其救援物资需求量为
$ \pmb{D}_1=[9,7],\ \, \pmb{D}_2=[5,5], \ \, \pmb{D}_3=[3,5] $
考虑如下的一个非法编码:
$ \left( {{\begin{array}{*{20}c} a_1t_1 \hfill & a_1t_2 \hfill & a_1t_3\\ a_2t_1 \hfill & a_2t_2 \hfill & a_2t_3\\ a_3t_1 \hfill & a_3t_2 \hfill & a_3t_3\\ a_4t_1 \hfill & a_4t_2 \hfill & a_4t_3\\ \end{array} }} \right)\!=\!\left( {{\begin{array}{*{20}c} {[3,\,2]} \hfill & {[1,\,1]} \hfill & {[0,\,0]}\\ {[1,\,3]} \hfill & {[2,\,0]} \hfill & {[1,\,1]}\\ {[0,\,0]} \hfill & {[3,\,2]} \hfill & {[3,\,2]}\\ {[3,\,4]} \hfill & {[3,\,1]} \hfill & {[1,\,5]}\\ \end{array} }} \right) $
具体修正步骤如下:
步骤 1. 第2列被首先随机选中, 对每一维应急资源分别进行检查.
步骤 1.1. 对于第1维应急资源, 对于 $\forall i=1$ , $\cdots, n$ , 有 $w_1^{i2} \leq b_1^i$ .由于, $a_1$ 被随机选中, 执行
$ w_1^{12}\leftarrow\max\{0, 1-(9 - 5) \}=0 $
紧接着 $a_2$ 被选中
$ w_1^{22}\leftarrow\max\{0, 2-(8 - 5) \}=0 $
依然存在应急资源浪费, $a_4$ 又被随机选中
$ w_1^{42}\leftarrow\max\{0, 3-(6 - 5) \}=2 $
此时满足 $\sum\nolimits_{i = 1}^4 w_1^{i2}= d^1_2$ .又 $w_1^{32}>0$ , $w_1^{42}>0$ ,
$ b^3_1\leftarrow b^3_1-w_1^{32}=6-3=3\\ b^4_1\leftarrow b^4_1-w_1^{42}=3-2=1 $
编码如下所示:
步骤 1.2. 对于第2维应急资源, 对于 $\forall i=1$ , $\cdots, n$ , 有 $w_2^{i2} \leq b_2^i$ .由于, 应急联盟的救援物资不够充分, $a_2$ 被随机选中, 执行
$ w_2^{22}\leftarrow\min\{0+(5-4), 4\}=1 $
此时 $\sum\nolimits_{i = 1}^4 w_2^{i2}=d^2_2$ .又 $w_2^{12}>0$ , $w_2^{22}>0$ , $w_2^{32}>0$ , $w_2^{42} > 0$ ,
$ b^1_2\leftarrow b^1_2-w_2^{12}=3-1=2\\ b^2_2\leftarrow b^2_2-w_2^{22}=4-1=3\\ b^3_2\leftarrow b^3_2-w_2^{32}=2-2=0\\ b^4_2\leftarrow b^4_2-w_2^{42}=8-1=7 $
编码如下所示:
至此, 第2列检查完毕, 应急联盟为
$ C_2\leftarrow\{a_1,a_2,a_3,a_4\} $
步骤 2. 第1列被随机选中, 对每一维应急资源分别进行检查.
步骤 2.1. 对于第1维应急资源, 对于 $\forall i=1$ , $\cdots$ , n, 由于 $w_1^{41}=3>b_1^4=1$ ,
$ w_1^{41}\leftarrow b_1^4=1 $
由于 $\sum\nolimits_{i = 1}^4 w_1^{i1}=3+1+1=5 < d^1_1=9$ , $a_1$ 被随机选中, 执行
$ w_1^{11}\leftarrow\min\{3+(9-5), 5\}=5 $
应急资源仍然不够, $a_2$ 又被选中
$ w_1^{21}\leftarrow\min\{1+(9-7), 4\}=3 $
此时满足 $\sum\nolimits_{i = 1}^4 w_1^{i1}=d^1_1$ .又 $w_1^{11}>0$ , $w_1^{21}>0$ , $w_1^{41} > 0$ ,
$ b^1_1\leftarrow b^1_1-w_1^{11}=5-5=0\\ b^2_1\leftarrow b^2_1-w_1^{21}=4-3=1\\ b^4_1\leftarrow b^4_1-w_1^{41}=1-1=0 $
编码如下所示:
步骤 2.2. 对于第2维应急资源, 对于 $\forall i=1$ , $\cdots, n$ , 有 $w_2^{i1} \leq b_2^i$ .由于, $a_1$被随机选中, 执行
$ w_2^{11}\leftarrow\max\{0, 2-(9 - 7) \}=0 $
此时满足 $\sum\nolimits_{i = 1}^4 w_2^{i1}=d^1_2$ .又 $w_2^{21}>0$ , $w_2^{41}>0$ ,
$ b^2_2\leftarrow b^2_2-w_2^{21}=3-3=0\\ b^4_2\leftarrow b^4_2-w_2^{41}=7-4=3 $
编码如下所示:
至此, 第1列检查完毕, 应急联盟为
$ C_1\leftarrow\{a_1,a_2,a_4\} $
步骤 3. 选择最后的第3列, 对每一维应急资源分别进行检查.
步骤 3.1. 对于第1维应急资源, 对于 $\forall i=1$ , $\cdots$ , n, 由于 $w_1^{43}=1>b_1^4=0$ ,
$ w_1^{41}\leftarrow b_1^4=0 $
由于 $\sum\nolimits_{i = 1}^4 w_1^{i3}=1+3=4 > d^3_1=3$ , 存在应急资源冗余, $a_2$ 被随机选中, 执行
$ w_1^{23}\leftarrow\max\{0, 1-(4 - 3) \}=0 $
此时恰好满足 $\sum\nolimits_{i = 1}^4 w_1^{i3}=d^3_1$ .又 $w_1^{33}>0$ ,
$ b^3_1\leftarrow b^3_1-w_1^{33}=3-3=0 $
编码如下所示:
步骤 3.2. 对于第2维应急资源, 对于 $\forall i=1$ , $\cdots, n$ , 由于 $w_2^{23}=1>b_2^2=0$ , $w_2^{33}=2>b_2^3=0$ , $w_2^{43} = 5>b_2^4=3$ ,
$ w_2^{23}\leftarrow b_2^2=0\\ w_2^{33}\leftarrow b_2^3=0\\ w_2^{43}\leftarrow b_2^4=3 $
由于 $\sum\nolimits_{i = 1}^4 w_2^{i3}=3 < d^3_2=5$ , 应急联盟救援物资不充分, 只有 $a_1$ 还有所需的应急资源, 执行
$ w_2^{13}\leftarrow\min\{0+(5-3), 2\}=2 $
此时 $d^3_2$ 被满足.又 $w_2^{13}>0$ , $w_2^{43}>0$ ,
$ b^1_2\leftarrow b^1_2-w_2^{13}=2-2=0\\ b^4_2\leftarrow b^4_2-w_2^{43}=3-3=0 $
编码如下所示:
至此, 第3列检查完毕, 应急联盟为
$ C_3\leftarrow\{a_1,a_3,a_4\} $
通过上例可以看出, 编码修正机制可以保证每个发放点的应急联盟所拥有的应急资源总量恰好能够满足其应急需求, 可以有效避免应急资源浪费.同时, 虽然很多储备点同时响应了多个不同的发放点的应急请求, 但应急联盟之间不存在任何应急资源冲突, 保障了应急联盟的可执行性, 从而可以充分发挥各应急联盟的救援能力.
3.5 变异操作
在DE/rand/2/bin算法[47]中, 变异操作是从初始种群 ${\pmb{P}}^0$ 中随机选择5个不同的个体 $p^1$ , $p^2$ , $p^3$ , $p^4$ 和 $p^5$ , 然后基于差异向量构造一个新个体 $p^\ast$ , 即对于 $\forall i=1, \cdots, n$ , $\forall j=1, \cdots, m$ , 执行
$ {\pmb{W}}^{ij}_{p^\ast}\leftarrow {\pmb {W}}^{ij}_{p^1}+F\times({\pmb{W}}^{ij}_{p^2}- {\pmb{W}}^{ij}_{p^3})\,+\notag\\ F\times({\pmb{W}}^{ij}_{p^4}-{\pmb{W}}^{ij}_{p^5}) $
(9) 其中, F称为缩放因子, 一般为 $(0, 2)$ 之间的一个常数.重复上述操作即可生成一个新的种群 ${\pmb{P}}^1$ .
3.6 交叉操作
在变异操作之后, 对初始种群 $\pmb{P}^0$ 和变异种群 $\pmb{P}^1$ 进行交叉操作.分别从 $\pmb{P}^0$ 和 $\pmb{P}^1$ 中各自挑选一个个体 $p^0$ 和 $p^1$ , 对于 $\forall i=1, \cdots, n$ , $\forall j=1, \cdots, m$ , 按如下进行交叉产生两个新的个体 $p^2$ 和 $p^3$ :
$ \begin{aligned} &\text{If}~~{\rm rand}(0,1)\leq CR~~\text{then}\\ &\;\;\;\;\;\;\;\;\pmb{W}_{p^2}^{ij}\leftarrow \pmb{W}^{ij}_{p^1}\\ &\;\;\;\;\;\;\;\;\pmb{W}_{p^3}^{ij}\leftarrow \pmb{W}^{ij}_{p^0}\\ &\text{Else}\\ &\;\;\;\;\;\;\;\;\pmb{W}_{p^2}^{ij}\leftarrow \pmb{W}^{ij}_{p^0}\\ &\;\;\;\;\;\;\;\;\pmb{W}_{p^3}^{ij}\leftarrow \pmb{W}^{ij}_{p^1} \end{aligned} $
(10) 其中, ${\rm rand}(0, 1)$ 表示在 $(0, 1)$ 之间生成一个随机数, $CR$ 称为交叉概率, 通常为 $(0, 1)$ 之间的一个常数.通过上述交叉操作即可生成两个新的交叉种群 $\pmb{P}^2$ 和 $\pmb{P}^3$ .
3.7 基于非支配排序的选择操作
为了评估每个个体对于式(1) 中两个目标函数值的优劣, 我们将NSGA-Ⅱ中的非支配排序思想引入到DE/rand/2/bin算法的选择操作中.如图 4所示, 我们将当前的初始种群 $\pmb{P}^0$ 和两个交叉种群 $\pmb{P}^2$ , $\pmb{P}^3$ 合并成一个大种群(规模为 $3\times PS$ ), 根据非支配排序和个体拥挤度排序从大种群中选择出 $PS$ 个最优个体组成新一代种群, 作为下一次迭代的初始种群 ${\hat{\pmb{P}}}^0$ .
具体地说, 首先根据非支配排序对这个大种群进行分层.设 $num_x$ 表示在可行解空间中可以支配解x的所有解个数, $set_x$ 表示被解x所支配的解集合, 分层操作的基本思想如下:
1) 首先计算大种群中每个个体的支配个数 $num_x$ 和被支配解集合 $set_x$ , 将 $num_x=0$ 的所有个体作为Pareto第1层 $\Gamma_1$ .
2) 然后按顺序访问第1层个体的 $set_x$ 集合, 对其所有个体的 $num_x$ 值进行减1操作, 并将 $num_x = 0$ 的所有个体作为Pareto第2层 $\Gamma_2$ .
3) 再按顺序访问第2层个体的 $set_x$ 集合, 对其所有个体的 $num_x$ 值进行减1操作, 并将 $num_x=0$ 的所有个体作为Pareto第3层 $\Gamma_3$ .
4) 重复上述操作, 直到将个个体全部分配了相应的Pareto层次.
显然, 在图 4中, 分层是根据 $num_x$ 的值决定解x在解集中的层次, 层次越高, 解的质量就越好, 因此, 我们依次把高层次中的所有个体加入到新种群 $ {\hat{\pmb P}}^0$ 中.如果把某一层中的全部个体加入到 ${\hat{\pmb{P}}}^0$ 中使得种群规模超过了 $PS$ , 我们就需要从这一层中挑选出某些较优个体进入下一代种群, 这时就需要对这一层次的个体按照拥挤度进行排序.
设 $f_1^x$ 和 $f_2^x$ 分别表示x对应式(1) 中的两个目标函数值, $f_1^{\max}$ , $f_1^{\min}$ , $f_2^{\max}$ , $f_2^{\min}$ 分别表示目标函数 $f_1$ 和目标函数 $f_2$ 的最大和最小值.我们分别按照目标函数 $f_1$ 和 $f_2$ 对这一层中的所有个体按照函数值升序进行排序, 并令排序后的第一个个体和最后一个个体的拥挤度为无穷大, 则第x个个体的拥挤度 $\delta_x$ 计算如下:
$ \displaystyle\delta_x =\frac{ f_1^{x+1}-f_1^{x-1}} {f_1^{\max}- f_1^{\min}}+\frac{f_2^{x+1}-f_2^{x-1}} { f_2^{\max}- f_2^{\min}} $
(11) 显然, 对于这一层的每个个体来说, 拥挤度越大, 解的质量就越好.因此, 可以根据需要从这一层中选择若干个拥挤度较大的个体进入以满足种群规模 $PS$ .
3.8 ERNS-DE算法描述
ERNS-DE算法以式(1) 为目标函数值, 基于第3.2节对ERA参数进行预处理, 采用第3.3节的编码和初始化方案生成初始种群, 基于第3.4节的编码修正机制将每个个体修正为合法的编码, 然后执行变异、交叉和非支配排序选择生成一个新种群, 将这个新种群作为下一代初始种群继续进化, 直到达到最大迭代次数, 其基本流程图如图 5所示.其中, DE参数设置主要是指设置ERNS-DE算法的初始参数, 包括种群规模、最大迭代次数、缩放因子、交叉概率等.此外, 每个个体在进行了变异和交叉后编码模式很可能会发生变化, 原来合法的个体很可能又变成非法的, 所以必须在非支配排序选择前对所有个体重新进行编码修正, 以确保其合法性, 从而确保非支配排序选择操作的顺利进行, 保障种群的进化.
4. 实验与结果分析
为了验证本文所提ERNS-DE算法的有效性, 我们首先给出我们的实验环境, 然后将ERNS-DE算法与经典的多目标优化算法在不同的ERA环境中进行对比分析, 最后将ERNS-DE算法与已有的代表性ERA方法进行对比实验.
4.1 实验环境设计
对于优化算法来说, 算法参数取值不同可能会导致算法性能的波动.目前常用确定参数的方法是通过大量测试获得. 表 1为我们结合已有工作[49-50]并通过大量测试所获得的ERNS-DE算法相关参数值.
表 1 ERNS-DE算法的参数设置Table 1 Parameters setting for ERNS-DE最大迭代次数 种群规模PS 缩放因子F 交叉概率CR 500 30 0.55 0.76 考虑如下两种ERA环境:
En 1. 3种应急资源、10个储备点和5个发放点, 各ERA参数( $\pmb{D}_j$ , $\pi_j$ , $\pmb{B}_i$ , $\mathbf{\Phi}_i$ , $\mathbf{\Gamma}_i$ ) 按照图 6所示的分布图的广义距离随机生成.
En 2. 3种应急资源、20个储备点和10个发放点, 各ERA参数( $\pmb{D}_j$ , $\pi_j$ , $\pmb{B}_i$ , $\mathbf{\Phi}_i$ , $\mathbf{\Gamma}_i$ ) 按照图 7所示的分布图的广义距离随机生成.
在每种实验环境中, 我们还考虑如下两种ERA参数情形:
Case 1. 所有储备点的应急资源总量远大于发放点的应急需求, 即, 该情形一般对应着灾害应急响应的中后期.
Case 2. 所有储备点的应急资源总量恰好等于发放点的应急需求, 即, 该情形一般对应着灾害应急响应的初期.
注意, 在应急响应初期, 所有储备点的应急资源总量可能会小于发放点的应急需求, 根据ERNS-DE算法中的ERA参数预处理(见第3.2节) 我们知道, 可以将所有发放点的应急需求按比例缩小以满足应急需求恰好等于所有储备点的应急资源总量, 此即为Case 2情形, 因此, 我们对应急救援物资不充分的情形不再重复测试, 因为可以通过ERA参数预处理转化为Case 2情形讨论.
4.2 ERNS-DE与经典多目标算法的对比
选取目前公认效果较好的三种经典多目标算法: NSGA-Ⅱ[42]、多目标粒子群优化(Multi-objective particle swarm optimization, MOPSO)[43]和多目标差分进化(Multi-objective differential evolution, MODE)[48]与本文ERNS-DE算法进行对比分析, 前三种算法中的基本参数均与文献[42]、文献[43]和文献[48]保持一致, 且每种算法各独立运行15次.
图 8给出了四种算法15次独立实验的CPU运行时间.从图 8可以看出, 无论是在En 1环境中还是在En 2环境中, 当储备点所能提供的应急资源之和远大于发放点的应急需求时(即Case 1情形), ERNS-DE算法所消耗的时间平均要略微多于NSGA-Ⅱ、MODE和MOPSO三种算法, 这是由于在此情形下, 应急资源足够充分, 各发放点的应急需求很容易被满足, 因而种群中存在大量的合法个体, 而非法个体相对较少, 即使丢弃了若干非法个体, 也可以保证NSGA-Ⅱ、MODE和MOPSO三种算法能够较快地找到可行解, 而ERNS-DE算法需要在每一代对变异、交叉操作产生的每一个个体进行编码修正, 从而带来一定的时间开销.
当储备点所能提供的应急资源量之和恰好等于发放点的应急需求时(即Case 2情形), 此时的应急资源冲突最为严重, ERNS-DE算法所消耗的时间反而低于NSGA-Ⅱ、MODE和MOPSO三种算法, 其原因在于ERNS-DE算法的编码修正机制可以把每个个体都修正为合法的编码, 从而可以尽可能地保留个体的有用信息, 加快种群进化的速度, 使得ERNS-DE算法可以在较少的时间内搜索到较优的应急资源分配方案.而对于NSGA-Ⅱ、MODE和MOPSO三种算法来说, 由于在每次的迭代过程中都会存在大量的非法编码, 而这些非法编码都是不可行解, 从而使得种群的有用信息变得非常有限, 种群进化异常缓慢, 需要耗费更多的时间才能找到理想的可行解.
图 9和图 10分别给出了在En 1环境中, 四种算法在两种ERA参数情形下的Pareto最优解个数进化曲线和Pareto解集.如图 9 (a)所示, 在Case 1情形下, ERNS-DE算法能够找到30个Pareto最优解, 而MOPSO、NSGA-Ⅱ和MODE三种算法搜索到的Pareto最优解至多为21个.由图 10 (a)可见, ERNS-DE得到的解在应急资源总成本和应急响应总时间之间分布较密集和均匀, 相似度较高, 且解的质量较好, 而MOPSO、NSGA-Ⅱ和MODE三种算法得到的解在两个目标之间分布则较为分散, 解的质量也明显不如ERNS-DE.
图 9 En 1环境中四种算法的Pareto最优解个数Fig. 9 Numbers of Pareto solutions obtained by the four algorithms in En 1
图 10 En 1环境中四种算法的Pareto最优解集Fig. 10 Pareto solution sets obtained by the four algorithms in En 1在Case 2情形下, 由于储备点所能提供的应急资源之和恰好等于发放的应急需求, 因此, 所有储备点都要贡献全部的应急资源储备量, 从而使得救援物资成本始终保持一个定值, 但不同的应急联盟具有不同的运输成本, 由图 9 (b)可见, ERNS-DE算法能够找到11个Pareto最优解, 而MOPSO、NSGA-Ⅱ和MODE三种算法搜索到的Pareto最优解至多为5个.由图 10 (b)可见, ERNS-DE得到的解的质量要明显好于MOPSO、NSGA-Ⅱ和MODE三种算法.
图 11和图 12分别给出了En 2环境中, 四种算法在两种ERA参数情形下的Pareto最优解个数进化曲线和Pareto最优解集.在Case 1情形下, 由图 11 (a)可见, 由于该环境相对于En 1储备点和发放点数目都大幅增加, 搜索空间进一步加大, ERNS-DE算法仍能搜索到30个Pareto最优解, 而MOPSO、NSGA-Ⅱ和MODE三种算法搜索到的Pareto最优解还不到15个.由图 12 (a)可见, ERNS-DE得到的解的质量明显占优, 分布也较为均匀.在Case 2情形下, 由图 11 (b)可见, ERNS-DE算法搜索到13个Pareto最优解, 而MOPSO、NSGA-Ⅱ和MODE三种算法搜索到的Pareto最优解最多也才8个.由图 12 (b)可见, ERNS-DE算法的结果依然要好于MOPSO、NSGA-Ⅱ和MODE三种算法.
图 11 En 2环境中四种算法的Pareto最优解个数Fig. 11 Numbers of Pareto solutions obtained by the four algorithms in En 2
图 12 En 2环境中四种算法的Pareto最优解集Fig. 12 Pareto solution sets obtained by the four algorithms in En 2从上述的实验结果可以看出, 针对不同的ERA参数情形, 虽然ERNS-DE算法可能会多耗费些计算时间, 但是ERNS-DE算法对解的探索能力要明显优于MOPSO、NSGA-Ⅱ和MODE三种算法, 说明本文在ERNS-DE算法中嵌入的编码修正机制效果显著, 可以保证将种群中的每个个体都修正为合法的个体, 也就是每个个体都是一个可行解, 从而扩大了种群的探索空间, 大大提高了种群的有效性和多样性, 为种群的进化提供强有力的启发式信息, 而嵌入的非支配排序选择则可以最大限度地保留种群中的优秀个体, 从而提高种群的进化效率.
4.3 ERNS-DE与代表性ERA方法的对比
在文献[25]中, Zhang等构建了多发放点、多储备点、多种救援物资的ERA模型, 并基于线性规划(Linear programming) 和网络优化(Network optimization) 方法设计了一种启发式算法(LPNO-HA) 来搜索最优解, 其所提模型与本文思想最为接近, 因此我们选择经典的LPNO-HA算法作为对比对象. LPNO-HA算法属于单目标优化, 追求的是资源约束下的应急响应总时间最小, 而且对于多发放的的应急需求采用串行分配方式以避免潜在的应急资源冲突.为了对比的公平性, 我们根据LPNO-HA算法给出的应急资源分配方案来推算其应急资源总成本.
表 2和表 3分别给出了在En 1环境中和En 2环境中, 两种ERA参数情形下得到的Pareto最优解.可以看出, LPNO-HA算法只能给出单一的决策方案, 决策者在评估时别无选择.本文的ERNS-DE算法可以给出更多的Pareto最优解, 从而可以为实际的应急决策提供更多可供选择的应急资源分配方案, 决策者可以根据实际需求合理选择合适的应急方案, 例如在应急响应初期, 一般要求尽可能地降低应急响应总时间, 而在应急响应的中后期, 则可以更多地着眼于尽可能地降低应急资源总成本.
表 2 两种算法在En 1环境中Pareto最优解Table 2 Pareto solutions obtained by two algorithms in En 1ERA参数情形 算法 Pareto最优解集(f1, f2) Case 1 ERNS-DE (162, 242), (181, 218), (185, 214), (171, 228), (164, 235), (187, 212),
(169, 230), (173, 226), (154, 252), (180, 219), (189, 210), (175, 224),
(155, 250), (168, 231), (165, 234), (194, 208), (183, 216), (184, 215),
(170, 229), (167, 232), (179, 220), (166, 233), (178, 221), (163, 236),
(186, 213), (176, 223), (172, 227), (182, 217), (157, 247), (177, 222)LPNO-HA (155, 275) Case 2 ERNS-DE (194, 302), (205, 287), (193, 303), (209, 285), (199, 294), (191, 308),
(192, 306), (201, 291), (187, 312), (189, 309), (195, 300)LPNO-HA (196, 303) 表 3 两种算法在En 2环境中Pareto最优解Table 3 Pareto solutions obtained by two algorithms in En 2ERA参数情形 算法 Pareto最优解集(f1, f2) Case 1 ERNS-DE (158, 252), (181, 218), (188, 211), (166, 233), (169, 230), (177, 222),
(159, 246), (182, 217), (187, 212), (176, 223), (185, 214), (170, 229),
(180, 219), (165, 235), (173, 226), (163, 239), (164, 237), (172, 227),
(189, 210), (168, 231), (157, 253), (183, 216), (175, 224), (193, 209),
(186, 213), (156, 254), (178, 221), (167, 232), (154, 259), (196, 208)LPNO-HA (155, 283) Case 2 ERNS-DE (203, 274), (205, 271), (199, 276), (189, 289), (187, 293), (183, 313), (196, 278)
(185, 306), (200, 275), (192, 286), (195, 281), (180, 320), (190, 288)LPNO-HA (189, 293) 进一步来说, ERNS-DE算法得到的Pareto最优解要好于LPNO-HA算法.例如, 在Case 1情形下, ERNS-DE在En 1环境中给出的(154, 252) 和(155, 250) 均优于LPNO-HA得到的(155, 275), ERNS-DE在En 2环境中给出的(154, 259) 也要好于LPNO-HA得到的(155, 283).在Case 2情形下, ERNS-DE在En 1环境中给出的(194, 302)、(193, 303) 和(195, 300) 均优于LPNO-HA得到的(196, 303), ERNS-DE在En 2环境中给出的(189, 289) 和(187, 293) 也好于LPNO-HA得到的(189, 293).可见, 在应急救援物资最为紧张、应急资源冲突最为严重的Case 2情形下, ERNS-DE算法挖掘Pareto最优解的能力明显好于LPNO-HA算法, 仍然能给出多个可供选择的应急方案, 而Case 2一般为应急响应初期的常态, 因此, 与LPNO-HA算法相比, ERNS-DE算法具有更好的应急环境适应能力.
图 13给出了ERNS-DE和LPNO-HA两种算法在En 1和En 2两种应急环境中得到的应急联盟(EC) 分布图.
具体来说, 在En 1环境中Case 1情形下, 见图 13 (a), 两种算法得到的 $EC_1$ 、 $EC_2$ 、 $EC_3$ 和 $EC_4$ 差异不大, 但ERNS-DE算法得到的 $EC_5=\{a_8, a_{10}\}$ , 而LPNO-HA算法的 $EC_5=\{a_6, a_7, a_8, a_{10}\}$ .显然, 从广义距离来看, LPNO-HA算法的 $EC_5$ 会带来更大的运输成本.同样, 在En 1环境中Case 2情形下, 见图 13 (b), 虽然LPNO-HA算法得到的比ERNS-DE算法的 $EC_5= \{a_7, a_8, a_{10}\}$ 稍微合理一些, 但ERNS-DE算法得到的 $EC_2=\{a_3, a_4, a_5\}$ 和 $EC_3=\{a_5, a_6\}$ 要远比LPNO-HA算法得到的 $EC_2=\{a_3, a_4, a_7\}$ 和 $EC_3 = \{a_5, a_6, a_7\}$ 合理的多.
在En 2环境中Case 1情形下(见图 13 (c)), 大多数的应急联盟差别不大, 但ERNS-DE算法得到的 $EC_2=\{a_1, a_7\}$ 和 $EC_8=\{a_8, a_{12}\}$ 要比LPNO-HA算法给出的 $EC_2=\{a_1, a_6\}$ 和 $EC_8=\{a_7, a_8\}$ 合理得多.在En 2环境中Case 2情形下(见图 13 (d)), ERNS-DE算法得到的 $EC_8=\{a_8, a_{12}\}$ 和 $EC_9 = \{a_{13}, a_{14}\}$ 要比LPNO-HA算法给出的 $EC_8 = \{a_8, a_{11}, a_{12}\}$ 和 $EC_8=\{a_8, a_{13}\}$ 合理一些.
上述实验结果表明, LPNO-HA算法对多个发放点采取串行方式依次分配, 这种串行分配方式在处理后续发放点的应急需求时, 各储备点的应急救援物资状况已发生变化(因为参与了前面发放点的分配), 这时解空间已发生变化, 从而很可能牺牲一些较优解(如表 2和表 3所示).而ERNS-DE算法对所有发放点在同一解空间中进行并行分配, 可以充分考虑各储备点的应急救援物资分布状况, 同时能有效解决多发放点同时竞争同一储备点的救援物资时可能带来的冲突, 因而能够从整体上统筹考虑和合理、均衡配置应急资源分配, 从而能最大限度地发挥救援物资储备点的利用率和功效.
5. 结论与下一步工作
本文针对多储备点、多发放点、多种救援物资的应急资源并行分配这一难点问题展开研究, 首先基于合作博弈理论中的协作联盟概念构建了ERA多目标优化模型, 然后设计了一种基于编码修正机制和非支配排序差异演化的ERA多目标优化算法.对比实验结果表明, 本文方法能够从全局角度同时为多个发放点给出应急资源分配方案, 实现了一个储备点能同时为多个发放点协同配备应急资源, 而且不会产生任何应急资源冲突.在应急资源受限情况下, 本文方法可以在一定程度上提高大规模应急资源分配的效率, 为政府的应急决策提供更多合理可靠的选择.
本文的工作属于静态优化方法, 要求发放点和应急需求已知并固定, 主要适用于灾害应急响应的中期和后期, 也适用于灾情稳定的应急响应初期.但是, 本文的主旨并不是要强调所提的ERNS-DE会一直优于MOPSO、NSGA-Ⅱ、MODE和LPNO-HA算法, 本文的工作可以看作是从多目标优化视角下对多储备点、多发放点、多种救援物资情形下的应急资源分配问题进行的一个初步探索, 希望能对政府的灾害应急响应决策提供有益的技术支撑.
本文仍有如下问题需要在未来工作中进一步加以考虑:在一些特大灾害的应急响应初期, 有可能会发生次生灾害.例如2008年汶川大地震还相继引发了洪水、泥石流、山体滑坡等次生灾害, 此时发放点和应急需求是动态变化的, 如何解决类似的动态约束多目标应急资源分配问题是我们未来的一个研究方向.此外, 灾害应急响应不仅牵涉到应急资源分配.应急资源的调度, 即各储备点到各发放点运输路径的选择, 也是一个极其重要的问题, 直接关系到应急响应时间的长短, 但应急资源的运输时间又与应急资源分配方案密切关联, 因此, 如何将多目标应急资源分配和调度集成起来统一优化也是未来一个非常有实际意义的研究课题.
-
图 9 En 1环境中四种算法的Pareto最优解个数
Fig. 9 Numbers of Pareto solutions obtained by the four algorithms in En 1
图 10 En 1环境中四种算法的Pareto最优解集
Fig. 10 Pareto solution sets obtained by the four algorithms in En 1
图 11 En 2环境中四种算法的Pareto最优解个数
Fig. 11 Numbers of Pareto solutions obtained by the four algorithms in En 2
图 12 En 2环境中四种算法的Pareto最优解集
Fig. 12 Pareto solution sets obtained by the four algorithms in En 2
表 1 ERNS-DE算法的参数设置
Table 1 Parameters setting for ERNS-DE
最大迭代次数 种群规模PS 缩放因子F 交叉概率CR 500 30 0.55 0.76 
下载: 导出CSV
表 2 两种算法在En 1环境中Pareto最优解
Table 2 Pareto solutions obtained by two algorithms in En 1
ERA参数情形 算法 Pareto最优解集(f1, f2) Case 1 ERNS-DE (162, 242), (181, 218), (185, 214), (171, 228), (164, 235), (187, 212),
(169, 230), (173, 226), (154, 252), (180, 219), (189, 210), (175, 224),
(155, 250), (168, 231), (165, 234), (194, 208), (183, 216), (184, 215),
(170, 229), (167, 232), (179, 220), (166, 233), (178, 221), (163, 236),
(186, 213), (176, 223), (172, 227), (182, 217), (157, 247), (177, 222)LPNO-HA (155, 275) Case 2 ERNS-DE (194, 302), (205, 287), (193, 303), (209, 285), (199, 294), (191, 308),
(192, 306), (201, 291), (187, 312), (189, 309), (195, 300)LPNO-HA (196, 303)
下载: 导出CSV
表 3 两种算法在En 2环境中Pareto最优解
Table 3 Pareto solutions obtained by two algorithms in En 2
ERA参数情形 算法 Pareto最优解集(f1, f2) Case 1 ERNS-DE (158, 252), (181, 218), (188, 211), (166, 233), (169, 230), (177, 222),
(159, 246), (182, 217), (187, 212), (176, 223), (185, 214), (170, 229),
(180, 219), (165, 235), (173, 226), (163, 239), (164, 237), (172, 227),
(189, 210), (168, 231), (157, 253), (183, 216), (175, 224), (193, 209),
(186, 213), (156, 254), (178, 221), (167, 232), (154, 259), (196, 208)LPNO-HA (155, 283) Case 2 ERNS-DE (203, 274), (205, 271), (199, 276), (189, 289), (187, 293), (183, 313), (196, 278)
(185, 306), (200, 275), (192, 286), (195, 281), (180, 320), (190, 288)LPNO-HA (189, 293)
下载: 导出CSV
-
[1] Wang Z F. A preliminary report on the great Wenchuan earthquake. Earthquake Engineering and Engineering Vibration, 2008, 7(2):225-234 doi: 10.1007/s11803-008-0856-1 [2] Yuan Y F. Impact of intensity and loss assessment following the great Wenchuan earthquake. Earthquake Engineering and Engineering Vibration, 2008, 7(3):247-254 doi: 10.1007/s11803-008-0893-9 [3] Bilham R. Disaster management:preparing for the worst. Nature, 2013, 502(7472):438-439 https://www.researchgate.net/publication/303241398_Disaster_management_Preparing_for_the_worst [4] Nourbakhsh I, Sargent R, Wright A, Cramer K, McClendon B, Jones M. Mapping disaster zones. Nature, 2006, 439(7078):787-788 doi: 10.1038/439787a [5] Sun B Z, Ma W M, Zhao H Y. A fuzzy rough set approach to emergency material demand prediction over two universes. Applied Mathematical Modelling, 2013, 37(10-11):7062-7070 doi: 10.1016/j.apm.2013.02.008 [6] Başar A, Çatay B, Ünlüyurt T. A taxonomy for emergency service station location problem. Optimization Letters, 2012, 6(6):1147-1160 doi: 10.1007/s11590-011-0376-1 [7] Lee Y M, Ghosh S, Ettl M. Simulating distribution of emergency relief supplies for disaster response operations. In:Proceedings of the 2009 Winter Simulation Conference. Austin, TX, USA:IEEE, 2009. 2797-2808 http://dl.acm.org/citation.cfm?id=1995837 [8] Su Z P, Jiang J G, Liang C Y, Zhang G F. Path selection in disaster response management based on Q-learning. International Journal of Automation and Computing, 2011, 8(1):100-106 doi: 10.1007/s11633-010-0560-2 [9] 孙绪彬, 董海荣, 宁滨, 高童欣, 孔庆杰.基于ACP方法的应急疏散系统研究.自动化学报, 2014, 40(1):16-23 http://www.aas.net.cn/CN/abstract/abstract18262.shtmlSun Xu-Bin, Dong Hai-Rong, Ning Bin, Gao Tong-Xin, Kong Qing-Jie. ACP-based emergency evacuation system. Acta Automatica Sinica, 2014, 40(1):16-23 http://www.aas.net.cn/CN/abstract/abstract18262.shtml [10] Borell J, Eriksson K. Improving emergency response capability:an approach for strengthening learning from emergency response evaluations. International Journal of Emergency Management, 2008, 5(3-4):324-337 https://www.researchgate.net/publication/244924903_Improving_Emergency_Response_Capability_An_Approach_for_Strengthening_Learning_from_Emergency_Response_Evaluations [11] 苏兆品, 张婷, 张国富, 尤小泉, 蒋建国.基于云模型和模糊聚合的应急方案评估.模式识别与人工智能, 2014, 27(11):1047-1055 http://www.cnki.com.cn/Article/CJFDTOTAL-MSSB201411012.htmSu Zhao-Pin, Zhang Ting, Zhang Guo-Fu, You Xiao-Quan, Jiang Jian-Guo. Evaluation of emergency disposal schemes based on cloud model and fuzzy aggregation. Pattern Recognition and Artificial Intelligence, 2014, 27(11):1047-1055 http://www.cnki.com.cn/Article/CJFDTOTAL-MSSB201411012.htm [12] Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters. Safety Science, 2000, 35(1-3):41-57 doi: 10.1016/S0925-7535(00)00021-7 [13] Sherali H D, Desai J, Glickman T S. Allocating emergency response resources to minimize risk with equity considerations. American Journal of Mathematical and Management Sciences, 2004, 24(3-4):367-410 doi: 10.1080/01966324.2004.10737638 [14] Arora H, Raghu T S, Vinze A. Resource allocation for demand surge mitigation during disaster response. Decision Support Systems, 2010, 50(1):304-315 doi: 10.1016/j.dss.2010.08.032 [15] Zhu J M, Huang J, Liu D G. Equitable resource allocation problem with multiple depots in emergency management. In:Proceedings of the 2010 IEEE International Conference on Emergency Management and Management Sciences. Beijing, China:IEEE, 2010. 37-40 http://ieeexplore.ieee.org/abstract/document/5563509/ [16] Peng Y J, Hu Z B, Guo X. Research on the evolution law and response capability based on resource allocation model of unconventional emergency. Journal of Computers, 2010, 5(12):1899-1906 [17] Wang J C, Tepfenhart W, Rosca D. Emergency response workflow resource requirements modeling and analysis. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2009, 39(3):270-283 doi: 10.1109/TSMCC.2009.2009125 [18] Wang X P, Li D, Ma C, Chen M. Emergency resource location and allocation under uncertainty of disaster degree. ICIC Express Letters, 2011, 5(2):311-316 https://www.researchgate.net/publication/282630430_Emergency_resource_location_and_allocation_under_uncertainty_of_disaster_degree [19] Yang Z S, Zhou H X, Gao X Y, Liu S N. Multiobjective model for emergency resources allocation. Mathematical Problems in Engineering, 2013, 2013:Article ID 538695 http://www.oalib.com/paper/2318638 [20] Altay N. Capability-based resource allocation for effective disaster response. IMA Journal of Management Mathematics, 2013, 24(2):253-266 doi: 10.1093/imaman/dps001 [21] Wang D, Qi C, Wang H W. Improving emergency response collaboration and resource allocation by task network mapping and analysis. Safety Science, 2014, 70:9-18 doi: 10.1016/j.ssci.2014.05.005 [22] Wex F, Schryen G, Feuerriegel S, Neumann D. Emergency response in natural disaster management:allocation and scheduling of rescue units. European Journal of Operational Research, 2014, 235(3):697-708 doi: 10.1016/j.ejor.2013.10.029 [23] Liu C, Zeng Q T, Duan H, Zhou M C, Lu F M, Cheng J J. E-net modeling and analysis of emergency response processes constrained by resources and uncertain durations. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2015, 45(1):84-96 doi: 10.1109/TSMC.2014.2330555 [24] 李进, 张江华, 朱道立.灾害链中多资源应急调度模型与算法.系统工程理论与实践, 2011, 31(3):488-495 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201103012.htmLi Jin, Zhang Jiang-Hua, Zhu Dao-Li. Multi-resource emergency scheduling model and algorithm in disaster chain. Systems Engineering-Theory and Practice, 2011, 31(3):488-495 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201103012.htm [25] Zhang J H, Li J, Liu Z P. Multiple-resource and multiple-depot emergency response problem considering secondary disasters. Expert Systems with Applications, 2012, 39(12):11066-11071 doi: 10.1016/j.eswa.2012.03.016 [26] Wang Z Y, Xu W S, Yang J J, Peng J Z. A game theoretic approach for resource allocation based on ant colony optimization in emergency management. In:Proceedings of the 2009 International Conference on Information Engineering and Computer Science. Wuhan, China:IEEE, 2009. 1-4 [27] 王旭坪, 马超, 阮俊虎.考虑公众心理风险感知的应急物资优化调度.系统工程理论与实践, 2013, 33(7):1735-1742 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201307017.htmWang Xu-Ping, Ma Chao, Ruan Jun-Hu. Emergency supplies optimal scheduling considering the publićs psychological risk perception. Systems Engineering-Theory and Practice, 2013, 33(7):1735-1742 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201307017.htm [28] 王旭坪, 董莉, 陈明天.考虑感知满意度的多受灾点应急资源分配模型.系统管理学报, 2013, 22(2):251-256 http://www.cnki.com.cn/Article/CJFDTOTAL-XTGL201302015.htmWang Xu-Ping, Dong Li, Chen Ming-Tian. Multiple-area post-disaster resource distribution model considering perception satisfaction. Journal of Systems and Management, 2013, 22(2):251-256 http://www.cnki.com.cn/Article/CJFDTOTAL-XTGL201302015.htm [29] 王旭坪, 马超, 阮俊虎.运力受限的应急物资动态调度模型及算法.系统工程理论与实践, 2013, 33(6):1492-1500 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201306017.htmWang Xu-Ping, Ma Chao, Ruan Jun-Hu. Model and algorithm of relief materials dynamic scheduling without sufficient vehicle quantity. Systems Engineering-Theory and Practice, 2013, 33(6):1492-1500 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201306017.htm [30] Zhan S L, Liu N, Ye Y. Coordinating efficiency and equity in disaster relief logistics via information updates. International Journal of Systems Science, 2014, 45(8):1607-1621 doi: 10.1080/00207721.2013.777490 [31] 叶永, 刘南, 詹沙磊.基于信息更新的应急资源配置序贯决策方法.浙江大学学报(工学版), 2013, 47(12):2212-2220 http://www.cnki.com.cn/Article/CJFDTOTAL-ZDZC201312022.htmYe Yong, Liu Nan, Zhan Sha-Lei. Information update based sequential approach for emergency resources allocation planning. Journal of Zhejiang University (Engineering Science), 2013, 47(12):2212-2220 http://www.cnki.com.cn/Article/CJFDTOTAL-ZDZC201312022.htm [32] 张婧, 申世飞, 杨锐.基于偏好序的多事故应急资源调配博弈模型.清华大学学报(自然科学版), 2007, 47(12):2172-2175 http://www.cnki.com.cn/Article/CJFDTOTAL-QHXB200712020.htmZhang Jing, Shen Shi-Fei, Yang Rui. Preference-order-based game modeling of multiple emergency resource allocation. Journal of Tsinghua University (Science and Technology), 2007, 47(12):2172-2175 http://www.cnki.com.cn/Article/CJFDTOTAL-QHXB200712020.htm [33] 文仁强, 钟少波, 袁宏永, 黄全义.应急资源多目标优化调度模型与多蚁群优化算法研究.计算机研究与发展, 2013, 50(7):1464-1472 http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201307013.htmWen Ren-Qiang, Zhong Shao-Bo, Yuan Hong-Yong, Huang Quan-Yi. Emergency resource multi-objective optimization scheduling model and multi-colony ant optimization algorithm. Journal of Computer Research and Development, 2013, 50(7):1464-1472 http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201307013.htm [34] 高淑萍, 刘三阳.基于联系数的多资源应急系统调度问题.系统工程理论与实践, 2004, 23(6):113-115 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200306017.htmGao Shu-Ping, Liu San-Yang. Scheduling problem in multi-resource emergency systems based on the connection number. Systems Engineering-Theory and Practice, 2004, 23(6):113-115 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL200306017.htm [35] Chen C, Zhou D Q, Bai Y. Resource emergency dispatching mathematical model under transport capacity constraints. In:Proceedings of the 2009 IEEE International Conference on Grey Systems and Intelligent Services. Nanjing, China:IEEE, 2009. 559-563 [36] 于辉, 刘洋.应急物资的两阶段局内分配策略.系统工程理论与实践, 2011, 31(3):394-403 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201103003.htmYu Hui, Liu Yang. Two-stage online distribution strategy of emergency material. Systems Engineering-Theory and Practice, 2011, 31(3):394-403 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201103003.htm [37] 田军, 马文正, 汪应洛, 王刊良.应急物资配送动态调度的粒子群算法.系统工程理论与实践, 2011, 31(5):898-906 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201105016.htmTian Jun, Ma Wen-Zheng, Wang Ying-Luo, Wang Kan-Liang. Emergency supplies distributing and vehicle routes programming based on particle swarm optimization. Systems Engineering-Theory and Practice, 2011, 31(5):898-906 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201105016.htm [38] 王新平, 王海燕.多疫区多周期应急物资协同优化调度.系统工程理论与实践, 2012, 32(2):283-291 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201202009.htmWang Xin-Ping, Wang Hai-Yan. Optimal multi-period collaborative scheduling of emergency materials for multiple epidemic areas. Systems Engineering-Theory and Practice, 2012, 32(2):283-291 http://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201202009.htm [39] Su Z P, Jiang J G, Liang C Y, Zhang G F. A distributed algorithm for parallel multi-task allocation based on profit sharing learning. Acta Automatica Sinica, 2011, 37(7):865-872 doi: 10.1016/S1874-1029(11)60212-7 [40] Jiang J G, Su Z P, Qi M B, Zhang G F. Multi-task coalition parallel formation strategy based on reinforcement learning. Acta Automatica Sinica, 2008, 34(3):349-352 doi: 10.3724/SP.J.1004.2008.00349 [41] Srinivas N, Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evolutionary Computation, 1994, 2(3):221-248 doi: 10.1162/evco.1994.2.3.221 [42] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197 doi: 10.1109/4235.996017 [43] Beiranvand V, Mobasher-Kashani M, Abu Bakar A. Multi-objective PSO algorithm for mining numerical association rules without a priori discretization. Expert Systems with Applications, 2014, 41(9):4259-4273 doi: 10.1016/j.eswa.2013.12.043 [44] Ye C J, Huang M X. Multi-objective optimal power flow considering transient stability based on parallel NSGA-II. IEEE Transactions on Power Systems, 2015, 30(2):857-866 doi: 10.1109/TPWRS.2014.2339352 [45] Li Y H, Lu X M, Kar N C. Rule-based control strategy with novel parameters optimization using NSGA-II for power-split PHEV operation cost minimization. IEEE Transactions on Vehicular Technology, 2014, 63(7):3051-3061 doi: 10.1109/TVT.2014.2316644 [46] Wang Z, Tang K, Yao X. Multi-objective approaches to optimal testing resource allocation in modular software systems. IEEE Transactions on Reliability, 2010, 59(3):563-575 doi: 10.1109/TR.2010.2057310 [47] Das S, Suganthan P N. Differential evolution:a survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation, 2011, 15(1):4-31 doi: 10.1109/TEVC.2010.2059031 [48] Ali M, Siarry P, Pant M. An efficient differential evolution based algorithm for solving multi-objective optimization problems. European Journal of Operational Research, 2012, 217(2):404-416 [49] Cheng M Y, Tran D H. Two-phase differential evolution for the multiobjective optimization of time-cost tradeoffs in resource-constrained construction projects. IEEE Transactions on Engineering Management, 2014, 61(3):450-461 doi: 10.1109/TEM.2014.2327512 [50] Vincent L W H, Ponnambalam S G. A differential evolution-based algorithm to schedule flexible assembly lines. IEEE Transactions on Automation Science and Engineering, 2013, 10(4):1161-1165 doi: 10.1109/TASE.2012.2224107 期刊类型引用(18)
1. 崔志华，张茂清，常宇，张江江，王晖，张文生. 基于平均距离聚类的NSGA-Ⅱ. 自动化学报. 2021(05): 1171-1182 . 
本站查看2. 张国富，涂冰花，苏兆品，岳峰. 一种面向严重受损路网的抢修队调度算法. 控制与决策. 2021(07): 1663-1671 . 百度学术3. 陈友荣，卢俊杰，赵克华，刘半藤，孙萍，陈素明. 面向防汛物资动态变化的运输车辆调度优化算法研究. 计算机应用研究. 2021(08): 2435-2439 . 百度学术4. 姜子劼，宋贵宝，刘战，刘镇毓. 岸舰导弹作战单元多目标投送模型及解算方法. 火力与指挥控制. 2021(12): 159-165+170 . 百度学术5. 刘垚，郑琳，郑凯，王肃，廖启丹. 基于申威众核处理器的NSGA-Ⅱ并行和优化方法. 计算机应用研究. 2020(01): 96-101 . 百度学术6. 胡小璠. 模糊条件下境外应急物资自适应分配方法. 科技通报. 2020(06): 97-100 . 百度学术7. 李忠崴，蔡元启，李宝仁，李胜亮. EPC工程建设项目的应急资源优化配置研究. 中外能源. 2020(08): 79-85 . 百度学术8. 苏兆品，李沫晗，张国富，刘扬. 基于Q学习的受灾路网抢修队调度问题建模与求解. 自动化学报. 2020(07): 1467-1478 . 本站查看9. 严华健，张国富，苏兆品，刘扬. 救灾物资高维多目标自适应分配问题建模与求解. 计算机应用. 2020(08): 2410-2419 . 百度学术10. 林勇，肖骅，张立，漆磊. 震灾应急物资分配-运输优化模型及算法研究. 中国安全科学学报. 2020(10): 171-178 . 百度学术11. 高杨，郭红戈. 基于差分进化算法的动车组周转接续优化研究. 铁道运输与经济. 2019(04): 76-83 . 百度学术12. 赵星，吉康，林灏，徐鹏. 基于多目标路径规划的应急资源配置模型. 华南理工大学学报(自然科学版). 2019(04): 76-82 . 百度学术13. 盛虎宜，刘长石，鲁若愚. 震后初期应急物资短缺情景下的定位-路径问题研究. 运筹与管理. 2019(06): 41-47 . 百度学术14. 刘扬，张国富，苏兆品，蒋建国. 救灾物资多阶段分配与调度问题建模与求解. 控制与决策. 2019(09): 2015-2022 . 百度学术15. 胡红旗. 基于排序优化算法的电子通信信息存储研究. 电子设计工程. 2019(19): 80-84 . 百度学术16. 张晗，杨继斌，张继业，宋鹏云，徐晓惠. 燃料电池有轨电车能量管理Pareto多目标优化. 自动化学报. 2019(12): 2378-2392 . 本站查看17. 王艳，蒋天伦. 融合决策树的分布式多工厂协同生产调度方法. 系统仿真学报. 2019(11): 2181-2197 . 百度学术18. 刘长石，罗亮，周鲜成，黄福华. 震后初期应急物资分配-运输的协同决策:公平与效率兼顾. 控制与决策. 2018(11): 2057-2063 . 百度学术其他类型引用(30)
-
下载:
计量
- 文章访问数: 2150
- HTML全文浏览量: 410
- PDF下载量: 1217
- 被引次数: 48
