《基于改进粒子群算法的多资源应急调度研究》-工学论文，工程论文-论文范文参考-科学狗论文网

标题

基于改进粒子群算法的多资源应急调度研究

范文

邵泽军陈凡红吕晓娜郭慧敏

摘要：针对多资源应急调度问题，建立了多资源时间-成本调度模型。为了避免标准粒子群算法陷入局部的最优解，有效提高算法的搜索精度，通过邻域重叠，惯性因子线性变化等方法，提出了全局和局部混合模式的改进粒子群算法。通过数值算例验证了模型的合理性和算法的可行性和有效性，算例结果并与其它算法进行了比较，结果表明，所提算法能够有效降低调度成本，是解决应急资源调度的一种有效方法。

Abstract： In view of the multi resource emergency scheduling problem， a multi-resource time-cost scheduling model is established. In order to avoid the standard particle swarm optimization algorithm falling into the local optimal solution and effectively improve the search accuracy of the algorithm， an improved particle swarm optimization algorithm with global and local mixed mode is proposed by means of neighborhood overlap. linear change of inertia factor and other methods is used. The rationality of the model and the feasibility and effectiveness of the algorithm are verified by numerical examples. The results of the examples are compared with other algorithms. The results show that the proposed algorithm can effectively reduce the scheduling cost and is an effective method to solve the emergency resource scheduling.

关键词：应急物资;资源调度;时间成本调度模型;粒子群算法

Key words： emergency supplies;resource scheduling;time-cost scheduling model;particle swarm optimization

中图分类号：O221;N945;TP301.6? ? ? ? ? ? ? 文献标识码：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章编号：1006-4311（2020）10-0243-03

0? 引言

近年来，世界各地的各种事故灾害，公共安全灾害和自然灾害层出不穷，我国在2003年发生的SARS，2008年汶川地震等灾害都对人们的生产生活造成了严重的危害。在事故和灾害发生时，怎样在短时间内，合理安排救援人员和救灾物资的调度，使灾害造成的伤害降到最低，这是国内外学者研究的核心问题。

Fiedich等[1]提出了时间和空间上的优化资源分配的动态组合优化模型;Barbarosoglu G等[2]针对地震这一自然灾害中的应急物资运输问题，提出了需求时间最小以及成本最小的两阶段随机规划模型;李建斌[3]建立了机会成本最小化为目标，提出了紧急求援资源调度模型，并采用模拟退火算法进行了求解;汪勇，金菲[4]建立了多资源-成本调度模型，采用改进的进化规划算法进行了求解;汪欲，何建敏[5]就一次性消耗系统为背景多资源出救方案进行了研究。戴更新、达庆利[6]针对单个应急点开始时间最早的多种资源应急调度问题建立了模型，并给出了算法和调度方案。魏国强等[7]针对出救时间不确定的连续消耗应急资源调度问题进行了研究，建立了连续性满足度调度模型。

针对应急物资的多资源调度问题，本文建立了应急时间和运输成本最低的多目标优化模型，并采用邻域重叠和惯性因子线性变化等方法，提出全局和局部混合模式的改进的粒子群算法对其进行了求解，并取得较好的运算结果。

1? 问题假设及建立模型

假设A为受灾地点，B1，B2，…，Bn为n个应急资源供给点，受灾点需要救灾物资种类为m种。其中符号定义如下：

Qij表示第i个供给点对第j种资源的储备量;

xij表示第i个供给点对第j种资源的调度数量;

Cij表示第i个供给点对第j种资源的单位运输成本;

Cij（t）表示第i個对供给点第j种资源的时间成本系数;

R1，R2，…，Rm分别表示需求点对m种资源需求量，其中 ;

tij表示为第i个供应点第j种资源的运输时间;

t0表示第j种资源运输到应急点的最短时间;

C0表示该供给点的单位条件的运输成本;

C0/t0表示该供应点的单位时间内的运输成本;

Tj表示为第j种资源的供应量满足一定应急系数w的时限，即在Tj时间内，第j种资源的供应量达到wRj。

本文依据文献[4]，建立多资源时间-成本调度模型。具体模型如下：

其中，f1（x）和f2（x）分别表示时间成本和运输成本，约束条件中：式（2）表示应急点调运的资源应该不少于应急系数w条件下的资源需求量，运输时间不超过;式（3）表示应急供给点的资源调度量要不少于受灾点的资源需求量;式（4）表示救灾供应点提供的应急资源的数量约束条件。为了便于计算，将时间成本系数Cij（t）与增加的运输时间通过式（5）转化为单位运输成本。

式（5）中：增加的单位时间的运输成本表示从其它供应点调度资源所产生的成本。

2? 改进粒子群算法求解

2.1 基本粒子群算法

Kennedy和Eberhart在1995年通过模拟飞鸟扑食提出了智能算法-粒子群优化算法（PSO）[8]。假设目标搜索空间为D维，群体的粒子数为n个，粒子群中的每个粒子在每一次进化中，都是通过跟踪自己的两个最优解来更新自己位置。一个是粒子本身所找到的最优解pbest，记为，一个是整个粒子群所找到的最优解gbest，记为。粒子更新粒子的速度和新的位置利用如下的公式：

式中：c1和c2为学习因子，ω称为惯性因子，r1和r2是介于[0，1]之间的随机数，α称为约束因子。

2.2 改进粒子群算法（Improved PSO IPSO）

粒子群算法（PSO）结构简单，易于实现，但是却容易陷入局部最优，且搜索精度不高的缺点。针对该问题，本文提出的改进粒子群算法（IPSO）主要从以下三个方面做了改进：

首先，基于邻域思想，本文提出用全局和局部混合模式的改进PSO算法。局部模式的算法同全局模式大体类似，最大的不同点就是利用局部最优解pl去替换粒子群中的全局最优解pg。其中，局部最优解为该粒子邻域向量空间通过历次迭代所能搜索到的最优解。公式如下：

其次，根据粒子群算法中惯性因子的特点，惯性因子ω的设置，可以调节算法的能力，惯性因子ω的取值越大，算法具有的全局搜索能力就越强;惯性因子的ω的取值越小，算法的局部搜索能力就越强。鉴于此，本文通过将变量惯性因子ω设置为从0.9到0.4随时间线性减少这种方法，使算法在搜索初期，粒子更加侧重于全局搜索，从而更容易得到较好的粒子;在算法的搜索后期，粒子更加侧重于区域的局部搜索，从而使算法更易于收敛于全局最优解。

再次，本文提出的改进的粒子群算法，算法初期，每个个体的邻域设置为其自身，在算法搜索中，适应度更好的个体存在于适应值较好的点的邻域范围内，这就使得粒子在搜索过程中不是开始就向全局的最优解附近搜索，而是首先向粒子邻域内的最优解搜索。由于两个相邻邻域内会有一部分公共的粒子，公共粒子之间可以通过两个邻域相互交换各自获得的信息。算法迭代次数的不断增加，使得邻域逐渐增大，直至覆盖整个种群。于是，本文提出的改进粒子群算法有效的使粒子跳出局部最优解，避免早熟，达到全局最优解。

2.3 改进粒子群算法（IPSO）步骤

①初始化一种群，其中每个粒子位置向量按照1～m×n之间的数随机取一个实数，每个速度向量按照-（m×n-1）～（m×n-1）之间实数随机取，并将粒子群空间划分为若干个两两重叠的相邻粒子群，设定参数c1，c2;

②计算每个粒子的适应值，最优解pbest为每个粒子的初始适应值，接着寻求群内的全局最优解gbest;针对每个粒子，把当前的适应值和其搜索过的最好位置pbest作比较，若当前适应值较好，就将作为最好的位置pbest;

③计算种群中的每个粒子的邻域取值范围，接下来，比较当前适应值与其邻域经过的最好位置lbest，若较差，则通过重新设置lbest进行搜索，否则，直接采用gbest作为最优;

④更新下一代的种群的微粒的速度和位置;

⑤如果没有达到最大的迭代数或得到足够好的适应值，则返回Step2。

3? 算例分析

假设某地区A发生自然灾害，需要3类应急资源，需求量分别为15吨，30吨，50吨，现有5个应急供应点，各供应点及资源如表1。

本文改进粒子群算法所用参数为：n=30，c1=c2=2.0，子群规模为3个粒子，不同子群间的重叠的粒子数为2个，算法最大迭代次数为200，运算次数为10次。

表2中最优调度方案的括号内表示从5个供应点调度的3种不同资源数量，与文献[4]比较，五种算法的调度成本逐步增加，EPSO、IEP、GA、DE、EP、调度成本依次为70.18、70.40、73.55、75.46、80.58（万元），从而本文提出的算法有效降低了调度成本。

4? 结论

本文针对一个受灾地点，多种物资需要调度的应急资源调度问题，构造了时间-成本应急资源调度模型。采用改进的粒子群算法，并对模型进行了求解。通过数值算例结果表明，所提算法能够有效降低调度成本，是解决应急资源调度的一种有效方法。

参考文献：

[1]Fiedich F，Gehbauer F，Rickers U. Optimized resource allocation for emergency response after earthquake disasters[J]. Safety Science， 2000， 35（1-3）： 41-57.

[2]Barbarosoglu G， Arda Y. A two-stage stochastic programming framework for transportation planning in disaster response[J]. Journal of operational research society， 2004， 55： 43-53.

[3]李建斌.高速公路突发事件紧急救援关键技术研究[D].西安：长安大学，2012：101-121.

[4]汪勇，金菲.應急资源调度问题的改进进化算法研究[J].运筹与管理，2012，21（4）：29-33.

[5]汪欲，何建敏.应急系统中多资源出救方案的研究[J].东南大学学报（自然科学版），2002，32（3）：510-513.

[6]戴更新，达庆利.多资源组合应急调度问题的研究[J].系统工程理论与实践，2000，20（9）：52-55.

[7]魏国强，余超.出救时间不确定的连续消耗应急资源调度[J].计算机应用，2012，232（6）：1745-1748.

[8]吴聪，杨建辉.基于改进粒子群算法的物流配送车辆调度优化[J].计算机工程与应用，2015，51（13）：259-262.

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。