英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

一种基于多目标优化算法的有效应急物流调度模型

丁志明，杨曹，元英志，徐旭丽，芮瑶，林利民

信息技术学院 北京工业大学 北京 中国

摘要：近年来，频繁的公共事业已经造成重大人员伤亡和经济损失。在紧急救援的早期阶段，紧急救援资源需求量严重超出了供应量。紧急资源调度作为应急资源调度的一个重要部分，是应急资源调度的重要体现。当前，许多应急资源调度是多目标优化问题。它们关注的是总的紧急成本，并根据每个紧急救援点的实际灾难情况来评估应急资源分配。甚至于，它们不考虑道路问题。然而，实际上，道路状况直接影响到了成本。在这个问题上，我们提出了基于多目标优化算法的有效应急记录调度模型。我们从时空轨迹数据中获取道路信息。本文对应急资源调查的研究有助于在限制紧急情况资源的同时，提高资源的利用率，减少资金损失。

CCS概念：bull;信息系统→地理信息系统;bull;计算方法→规划和调度;bull;计算理论→生物激励优化;

关键字：应急物流调度，多目标优化算法，路网状况，轨迹矢量特征

ACM参考格式：丁志明，杨曹，元英志，徐旭丽，芮瑶，林利民，2018。基于多目标优化算法的有效应急物流调度模型。在第四届ACM SIGSPATIAL国际安全与复原研讨会（EM-GIS18），2018年11月6日，华盛顿州西雅图，美国。 ACM，纽约，纽约，美国，6页https://doi.org/10.1145/3284103.3284113

1 介绍

近年来，突发事件频繁发生，造成了巨大的人员伤亡和经济损失。例如，2015年8月，天津港爆炸造成165人死亡，数百人受伤。经济损失达700亿美元。对于大多数紧急情况，最佳救援时间在72小时之内，这是紧急救援的“黄金时期”[15,22,24]。这是为了解决搜救，食品供应和伤病员等其他问题。这个阶段需要很大的紧急救援物资的数量。但是，在紧急情况开始时，当地应急资源的数量和类型通常是不够的，所以有必要及时分配有限的资源，合理地对每个灾害现场。

可以看出，应急物流调度的水平是直接关系到应急救援工作的顺利进行和紧急救援工作的效率，这是对于紧急救援的非常有意义的。

救灾中的应急物流调度可分为四种情况：单一救援点到单一灾点，单一救援点到多个灾点，多个救援点到单个灾点，多个救援点到多个灾点。其中，前三个场景仅涉及资源点内部调度或路径优化。在多个救援点到多个灾点的资源调度中，有必要考虑救援时间[6]和运输的成本。因此，在有限的资源下，应尽可能满足每个灾区的需求。

很容易知道救援成本与救灾物资灾难的满意度相冲突。这是一个多目标优化问题（MOP）。在当前的多目标资源调度研究[5,11,28]中，应急资源调度的目标是减少总的紧急时间和成本。应急资源调度的有效性和满意度不能作为参与模型构建的相应评价指标来量化。此外，大多数调度模型[10,11,18,27]不考虑道路状况，实际救援中运输道路的拥堵直接影响救援时间成本[4]，进而影响到调度策略。针对这些问题，本文提出将道路状况和救援满意度作为应急资源调度的指标，从三个方面构建多目标资源调度模型：优化应急资源交付时间，分配成本和资源可用性。

本文的其余部分结构如下：第2节给出了问题描述和多目标优化算法。 第3节详细介绍了基于多目标优化算法的最优应急资源调度模型。 第4节说明了实验评估。 第5节回顾了我们的相关工作。 第6节最后总结了本文。

2 初步措施

2.1问题定义

对于大规模灾难中的资源调度，经典模型需要考虑时间成本和交付成本。 也就是说，我们的模型中有两个目标。 第一个目标是尽可能地减少时间成本f_T。 第二个目标是最小化交付成本f_R，旨在指导救援队选择适当和有效的道路。

定义2.1（最优调度成本）

minf(X)=min[f_T,f_R] （1）

其中f_T是救援计划的时间成本，包括资源准备，运输，装卸。 在本文中，我们只考虑运输时间。 f_R是指运输救援物资的成本。传统的数学规划技术是耗费时间来解决这种复杂的优化问题。 在本文中，我们提出了多目标优化算法来解决它。为方便参考，我们首先给出了多目标优化问题（MOPs）的定义[25]。

定义2.2（MOPs）

minf(X)=min[f₁(X),f₂(X),...,f_m(X)] （2）

其中fi（X）表示第i个目标函数; X =(x₁, x₂, ..., x_n) isin;Rⁿ是具有n维变量的解向量;

定义2.3（帕累托优势）

对于解向量X_a =(x^a₁ , x^a₂ , ..., x^a_D)^T和X_b =(x^b₁ , x^b₂ , ..., x^b_D)^T，当且仅当满足以下两个条件时

forall;i isin; {1, 2, ...,n} : x^a_i le; x^b_i

exist;i isin;{1, 2, ...,n} : x^a_i lt; x^b_i （3）

这样，存在显性关系，X^a帕累托显性X^b。 这可以写成X^a ≺ X^b。

定义2.4（帕累托最优集）

帕累托最优集定义为

PS = {X^lowast; |不存在 x isin; Omega; : X ≺ X^lowast;} （4）

X *isin;Omega;是Pareto最优解，满足不存在x isin; Omega; :X ≺ X^lowast;。所有帕累托最优目标的集合称为帕累托前沿; 也就是说，对应于在目标空间中设置的帕累托最优解的点集是帕累托前沿。

2.2基于群体智能的多目标优化

对于多目标优化问题，群体智能算法是一种有效的解决方案。群体智能算法通过学习自然界中的生命或自然现象来解决问题。这些算法包括自组织，自学习和自适应的特征。他们通过获取计算的信息来使群体能够搜索解空间。在搜索中，在搜索中，人口根据适者生存和适者生存的预先设定的适应度函数的值进化。因此，群体智能算法可以有效地解决复杂问题。

许多经典的优化算法，如MOPSO [7]，MOCS [23,25]，已成功应用于MOP。塔瓦纳等人。 [21]使用NSGA-III和MOPSO算法来解决多目标Xbar控制图设计问题。曹等人。 [2]采用MOCS进行软件缺陷预测问题。他们设计了一种基于双支持向量机和MOCS的新型SDP模型。他们将检测概率和误报概率设置为SDP目标。真实数据集上的实验结果表明，与其他SDP模型相比，他们的方法实现了良好的性能。张等人。 [25]提出了一种混合多目标布谷鸟搜索与动态局部搜索（称为HMOCS）来解决数值优化问题。

面对本文多目标优化问题的挑战，我们采用MOPSO和MOCS来优化应急资源调度。它们被提出用于多目标优化问题。 MOCS来自高效的布谷鸟搜索，这是一种新的群体智能优化算法，其灵感来自于布谷鸟在其他寄主鸟巢中搜寻和产卵的行为。自提出MOCS以来，由于其在解决许多优化问题及其对实际应用的适用性方面具有良好的搜索能力，因此引起了很多关注。

算法1中列出了基于群智能（基于SI的MOP）的多目标优化伪码。对于每个粒子p，初始化函数用于初始化其位置，速度（如果需要）和参数; evaluate函数用于使用非支配关系评估其适应度;函数updatePosition用于根据规则更新其位置。 createExternalArchive和updateArchive函数分别用于创建和更新外部存档。最后，当满足停止准则时，我们获得了多目标函数f（x）的最优解。

3 建议模型

紧急需求满足率取决于为满足资源需求而提供的资源数量，即在时间限制下尽可能多地满足多灾难点所需的资源数量。 资源调度具有成本效益，因为灾害应急救援具有时效性，与普通资源调度不同的是，应急资源调度的最大成本是时间成本，时间意味着生命。 同时，在灾害的初始阶段，无法确定灾害的规模，无法确定对资源的需求。 为了应对这一挑战，本文提出了一种考虑道路拥堵的新型多目标区域应急资源调度模型。

3.1 假设和符号定义

灾难发生后，我们应该考虑各种因素来建立一般的物质调度模型。假设在一个紧急救援中，有供应点S = [1,2，...，m]，n个灾难点D = [1,2，...，n]，以及可用的紧急资源类型供应点是C = [1,2，...，h]。为了尽快从供应点向灾区调度资源，我们应该有效地为每辆车分配调度任务，并输出最优车辆路线调度计划。以下是我们模型中使用的一些假设。

（1）每个供应点的资源是已知的。

（2）调度过程中不考虑转运站，这意味着应急资源直接从供应点转移到受影响点。

（3）有足够的卡车可用。

（4）在这个调度阶段，道路是连续可用的，拥堵保持不变。

下表中使用的符号和说明如表1所示。

3.2多目标优化模型

我们的模型有两个目标。 第一个目标是尽可能快地缩短交付时间并满足灾区人民的需求。 该目标的正式定义如下：

f₁(x)= (lambda;^j_i*p^j_i*d^j_i/v) （5）

其中，p^j_i表示救援点i到灾难点j的可能性，d^j_i是供给点i和灾难点j之间的距离。 理想情况下，资源交付的时间与距离成线性关系.lambda;^j_i表示从供应点i到灾害点j的道路拥堵系数，这将在下一小节中详细给出。资源分配成本由预定的车辆数量决定，调度次数由调度到灾难点的资源总量决定。 应急资源调度的成本函数正式定义如下：

f₂(x)= p^j_i*c^j_i （6）

其中，p^j_i表示救援点i到灾难点j的可能性，c ^j_i是从供应点i到灾害点j所需的车辆数量。应急资源调度的有效性由灾点的警戒级别，需求决定 用于资源和资源调度的数量。 对灾点j的资源需求为R_j = [r^j₁，r^j₂，...，r^j_h]。 从供应点i到灾难点j的资源是X^j_i = [x^j_i1，x^j_i2，...，x^j_ih]。 应急资源调度的满意功能正式定义如下：

f₃(x)= (l_j*p^j_i*|X^j_i|/L|R^j|) （7）

目标函数可以如下给出：

f (X) = min(alpha;・f₁ beta;・f₂ gamma;・1/f₃) （8）

s.t.

p^j_i = 1, |Xji | gt; 0,

0, others （9）

forall;j isin; D, forall;k isin; C, （10）

forall;j isin; D,p^j_ile;m （11）

p^j_ile;mn （12）

|X^j_i | =x^j_ik

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19602]，资料为PDF文档或Word文档，PDF文档可免费转换为Word