基于遗传算法的三层大规模应急救援物资配置策略

何　勇，温洁嫦，黄美华

(广东工业大学 应用数学学院，广东 广州 510520)

基于遗传算法的三层大规模应急救援物资配置策略

何勇，温洁嫦，黄美华

(广东工业大学 应用数学学院，广东 广州 510520)

摘要:在考虑受灾地区对应救援物资需求量大的基础上，研究了包括备选省级应急救援物资供应地、备选市县级应急救援物资中转地、救援物资急需地三层结构的车辆安排、路径选择、物资配送的应急救援物资配置问题；以应急救援物资配置的总成本最小、总的运输时间最短、供应地和中转地启用个数最少为目标，建立数学优化模型.使用遗传算法求解获得近似最优的三层应急救援物资配置方案.

关键词:应急救援；物资配送；车辆安排；路径优化；遗传算法

近年来，国内外各类大规模自然灾害频繁发生，因其具有严重次生灾害等特点,给受灾地区带来了极大的人员伤亡以及严重的经济损失，同时在灾后救援过程中的不计成本、盲目救援造成了严重浪费.大规模自然灾害发生后，如何有效地在救援物资供应地安排车辆进行装载，如何选择车辆路径快速运输、分配应急救援物资，成了大规模应急救援物资配置的关键问题，是快速挽救生命、减少灾民损失、降低经济损耗的基本途径.

针对如何优化应急物资配送这一问题，国内外学者进行了大量有意义的研究.Sheu[l]探讨总结了当前应急物资配置面临的挑战，并针对救援关键时期研究了面向大规模灾难的应急救援物资的配送方法；Chang和Tseng等[2]针对洪灾发生后，受灾地区应急物资需求量不确定的问题，提出了适应不同灾情信息的应急救援物资配送的模型；郑斌和马祖军等[3]建立了一个应急救援物资需求量不精确的多目标LRP优化策略；徐玖平等[4]对汶川特大地震灾后应急救援物资配置问题进行了重建物资分配、运输、配送中转地选择等一系列的实证研究；陈刚和张锦等[5]考虑了以应急物资保障过程为单目标的应急物资运输—配送模型；詹沙磊和刘南[6]研究了多个物资供应点、多个受灾点的应急救援车辆选址、路径优化、物资配送的多目标随机规划模型；廖成等[7]构建了大规模的应急救援模型，并考虑了更有效的求解方法.

综上所述，国内外学者对受灾情况多变的应急救援物资配置问题，已经进行了各种意义深远的建模研究，并对相应模型提出了松弛的拉格朗日算法[8]、启发式算法[9-10]、遗传优化智能算法[11-12]等多种适应不同环境的算法.但是由于突发的大规模事件这一类问题往往会造成灾后应急救援物资配送的情况复杂多变，很难研发出应急救援物资配置通用的数学优化模型与算法，且仍然有许多急需解决的问题.为此，本文基于应急物资急需量大的情况下，考虑把受灾点物资包装成标准单元物资，研究三层大规模应急救援物资配送策略，并使用遗传算法对模型求解获得近似最优的方案.

1数学模型

1.1问题背景描述

救援应急物资配送在受灾地区救援中最为关键，主要考虑问题是如何对受灾地区急需的物资包装分配以及如何安排装载车辆、选择运输路径对受灾地区进行救灾物资输送.因突发灾害复杂特殊、变化万千，对这一类情况特殊的救援应急物资配送问题，很难探讨出普遍适用的数学优化模型与算法.结合实际问题，本文考虑的网络简化结构如图1所示.

图1　物资配送网络的简化结构

1.2模型建立

(1)

(2)

(3)

其中,目标函数(1)为应急救援物资配置的总成本，目标函数(2)为应急救援物资总的运输时间，目标函数(3)为启用的供应地和中转地个数.

目标转化：为了达到更好的救援效果，结合应急救援物资配置的实际问题，在现实应急救援物资配置中，决策者一般更加注重目标函数(2).采用基于加权排序的方法，根据应急救援物资配置的总成本、总的运输时间、启用的供应地和中转地个数这三者的重要性，取权重为λ1=0.3，λ2=0.5，λ3=0.2.将以上3个目标聚集成一个单目标.

转化后目标函数：

f=λ1f1+λ2f2+λ3f3.

(4)

约束条件：

众所周知，物质交换原理由法国著名侦查学家埃德蒙·洛卡德提出，该理论主要说明了任何犯罪行为只要有客体之间的接触都会发生物质相互转移。将这一学说的原理与信息化调查相结合，就形成了信息转移原理。该理论强调犯罪过程中信息转移现象与犯罪行为是共同体，是客观存在的，监察调查人员在寻找线索证据的时候不能忽视任何蛛丝马迹。

(5)

uji≤xj,rkj≤yk∀j∈M,i∈L,k∈N；

(6)

(7)

αiθ≤XjiΩ，∀j∈M；

(8)

(9)

其中：L={i|i=1,2,…,l}为救援应急物资急需地集合；M={j|j=1,2,…,m}为备选市县级应急救援物资中转地集合；N={k|k=1,2,…,n}为备选省级应急救援物资供应地集合；αi(i=1,2,…,l)表示第i个应急救援物资急需地的物资数量；cji表示第j(j=1,2,…,m)个备选市县级应急救援物资中转地到第i(i=1,2,…,l)个应急救援物资急需地的距离；dkj表示由第k(k=1,2,…,n)个备选省级应急救援物资供应地到第j(j=1,2,…,m)个备选市县级应急救援物资中转地的距离.

xj,yk,uji,rkj(其中i=1,2,…,l;j=1,2,…,m;k=1,2,…,n)为0-1决策变量；如果启用第j个市县级救援物资中转地时xj=1，否则xj=0；如果启用第k个省级应急救援物资供应地时yk=1，否则yk=0；如果第i个应急救援物资急需地由第j个市县级应急救援物资中转地运输物资时uji=1，否则uji=0；如果第j个市县级应急救援物资中转地由第k个省级应急救援物资供应地供应物资时rkj=1，否则rkj=0.

Xji,Ykj,Zk(其中i=1,2,…,l;j=1,2,…,m;k=1,2,…,n)为整数决策变量.Xji表示负责第j个市县级应急救援物资中转地到第i个应急救援物资急需地的车辆数量；Ykj表示负责第k个省级应急救援物资供应地到第j个市县级应急救援物资中转地的车辆数量；Zk表示安排在第k个省级应急救援物资供应地的车辆数量.

2算法设计

遗传算法是一种仿效自然界“物竞天择、适者生存”的进化算法.根据问题，将目标设计成一个适应度函数，把问题所有可能取的解编码为染色体，一系列的染色体构成一个种群.利用迭代的方式让各个染色体经过若干代的选择、交叉、变异等运算来交换种群染色体的信息，并根据适应度评估染色体，优胜劣汰，使其逐渐趋向问题的近似最优解.本文参考文献[13-17]，结合应急救援物资配置模型，提出算法流程如下.

2.1算法参数设置与编码

(1) 设置最大的迭代代数Gen_max，种群规模K、交叉率pc和变异率pm.

(2) 对种群个体使用二进制遗传编码.每个染色体都由两个子串组成，长度为m+n；其中第1个子串的长度为对应的备选市县级应急救援物资中转地的个数m，基因位为0-1，1表示对应备选的中转地被启用，0表示对应的中转地不被启用；第2个子串的长度为对应的备选省级应急救援物资供应地的个数n；基因位为0-1，1表示对应备选的供应地被启用，0表示对应的供应地不被启用.给出算法流程如下.

2.2算法具体步骤

(1) 初始群体的生成.本文采用英国Sheffield遗传算法工具箱的crtbase函数创建任意种群规模为K=100，个体长度为m+n的二进制离散随机种群，将其定义为一个矩阵，至此得到初始种群P(0).

(2) 适应度评估，根据适应度函数大小区分优劣，评估每个染色体的适应度，优胜劣汰.本文直接考虑模型转化后的单目标函数式，取Fitness(i)=1/f(i)为适应度函数，其中f(i)为第i条染色体的目标函数值.

(3) 采用轮盘赌法进行选择操作，从P(n)(其中n为迭代代数)中选择K个染色体进入下一代P(n+1).

(4) 采用单断点交叉进行交叉操作，根据交叉概率pc=0.7判断各个染色体是否进行交叉，以促进遗传算法对解空间的搜索.

(5) 采用离散变异法进行变异操作，对(4)交叉后的染色体根据变异概率pm=0.02判断该基因是否进行变异，产生新一代P(n+1).

(6) 算法结束，如果代数n>Gen_max，输出最优解；如果代数n≤Gen_max，重复(2).

3算例仿真

随机抽取7个备选省级应急救援物资供应地，10个备选市县级应急救援物资中转地，30个应急救援物资急需地以及所需的应急救援物资数量.其中平均救援物资的单位质量：θ=3 kg/件，每辆车单位距离的运输时间：ε=0.015 h/km，单位距离运输单位物资质量的费用：δ=0.25元/(kg.km)，启用每个供应地、中转地的增设费用：ω=0.12百万元/个，每辆车的最大装载重：Ω=35 000 kg/辆.

采用matlab软件，根据以上设计的遗传算法编写相应的程序，求解近似最优的算例结果为应急救援物资配置的总成本为6 691.8百万元，总的运输时间为20 635 h，启用的供应地和中转地数量为12个.其中车辆安排、路径选择、物资配送的近似最优结果见表1、表2和图2.

表1　启用的省级救援物资供应地以及物资配置策略

表2　启用的市县级应急救援中转地以及物资配置策略

图2　算例目标函数近似最优的三层应急救援物资配置方案

Fig.2The three-layer emergency material allocation strategy of approximate optimal objective function of example

4结论

本文是在受灾地区对应急救援物资急需量较大的基础上，基于全国范围这一大区域，以应急救援物资总的运输时间最短、配置的总成本最小、供应地和中转地启用个数最少为目标，考虑了包括备选省级应急救援物资供应地、备选市县级应急救援物资中转地、救援物资急需地三层结构的应急救援物资配置模型，研究了应急救援车辆安排、路径选择、救援物资配送的应急救援物资配置问题.最后结合遗传工具箱设计遗传算法求解获得近似最优的三层应急救灾物资配置方案.

参考文献：

[1] SHEU J B.Challenges of emergency logistics management[J].Transportion Research Part E:Logistics and Transportation Review,2007,43(6):655-659.

[2] CHANG M S,TSENG Y L,CHEN J W.A scenario planning approach for the flood emergency logistics preparation problem under uncertainty[J].Transportation Research Part E: Logistics and Transportation Review,2007,43(6):737-754.

[3] 郑斌,马祖军,方涛.应急物流系统中的模糊多目标定位路径问题的研究[J].系统工程,2009.27(8):21-25.

ZHENG B,MA Z J,FANG T.Fuzzy muti-objective location routing problem in emergency logistics systems[J].Systems Engineering,2009,27(8):21-25.

[4] 徐玖平,马艳岚,段雪玲.汶川特大地震灾后民营企业重建的优选统筹模式[J].中国管理科学,2008,16(4):1-11.

XU J P,MA Y L,DUAN X L. The optimum seeking and overall planning model of the reconstructions of private enterprises in Wen Chuan post-earthquake[J].Chinese Journal of Management Science,2008,16(4):1-11.

[5] 陈刚,张锦,彭永涛.震后应急物资敏捷保障体系模型及算法[J].自然灾害学报,2013,22(3):47-53.

CHEN G,ZHANG J,PENG Y T.Agile security system model and algorithm for post-earthquake urgent relief provisons[J].Journal of Natural Disasters,2013,22(3):47-53.

[6] 詹沙磊,刘南.基于灾情信息更新的应急物资配送多目标随机规划模型[J].系统工程理论与实践,2013,33(1):159-166.

ZHAN S L,LIU N.Multi-objective stochastic programming model for relief allocation based on disaster scenario information updates[J].Systems Enginerring Theory & Practice,2013,33(1):159-166.

[7] 廖成,许维胜,吴启迪.大规模应急救援物资运输模型的构建与求解[J].系统工程,2006,24(11):6-12.

MIAO C,XU W S,WU Q D.A transportation modal and solution of large-scale emergency relief commodeties[J].Systems Engineering,2006,24(11): 6-12.

[8] ÖZDAMAR L,EKINCI E,KüξüKY-AZICI B. Emergency logistics planing in natural disasters[J].Annals of Operation Research,2004,129(1):217-245.

[9] HAGHARNT A,YAN S,SHIN Y L.Optimal scheduling of emergency roadway repair and subsequent relief distribution[J].Computers & Operations Research,2009,36(6):2049-2065.

[10] 杨勃,杜冰,李小林.多受灾点救灾物资分配调度问题启发式算法[J].系统工程,2012,30(1)97-103.

YANG B,DU B,LI X L. Euristics for distribution and scheduling of relief supplies among multiple disaster sites[J].Systems Engineering, 2012,30(1):97-103.

[11] MITSUO G,ADMI S.Hybrid genetic algorithm for multi-time period production/distribution planning[J].Computers & Industrial Engineering, 2005(48):799-809.

[12] 毕娜.0基于多目标遗传算法的配送路径问题研究[D].杭州:浙江工业大学机械工程学院,2007.

[13] 王绍仁,马祖军.震后随机动态LRP多目标优化模型及算法[J].计算机应用研究,2010,27(9):3283-3286.

WANG S R,MA Z J.Stochastic dynamic multi objective optimization location-routing model and algorithm in post-earthquake[J].Application Research of Computers,2010,27(9): 3283-3286.

[14] 郎茂祥.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报,2002,15(3):76-79.

LANG M X.Study of the optimizing of physical distribution routing problem based on genetic algorithm[J].China Journal of Highway and Transport,2002,15(3):76-79.

[15] 史峰,王辉,郁磊.MATLAB智能算法30个案例分析[M].北京:北京航空航天大学出版社,2011.

[16] DAVIS L.Handbook of Genetic Algorithm[M]. NewYork:Nostrand Reinhold,1991.

[17] 张军,詹志军.计算智能[M].北京:清华大学出版社,2009.

The Three Layers of Large-scale Emergency Material Allocation Strategy Based on the

GAHe Yong, Wen Jie-chang, Huang Mei-hua

(School of Applied Mathematics, Guangdong University of Technology, Guangzhou 510520, China)

Abstract:Based on the concern that the affected areas are in an urgent need of a large quantity of emergency relief materials, a study is conducted on the problems of vehicle arrangement, path selection, distribution in emergency material allocation in three layers including alternative provincial supplying spot, alternative municipal and county-level transitional place and the area in urgent need. An optimized mathematical model is figured out with the goals of minimum total cost, the shortest transport time and minimum supplying spots and transitional places in emergency material allocation. Finally, using GA, an optimized three-layer large-scale emergency material allocation scheme is proposed.

Key words:emergency relief; material distribution; vehicle arrangement; path optimization; genetic algorithms(GA)

收稿日期:2015-01-15

基金项目:广东省特色创新项目(2014KTSCX055)

作者简介:何勇(1990-),男，硕士研究生，主要研究方向为最优化方法与应用. 通信作者: 温洁嫦(1964-),女，教授，硕士生导师，主要研究方向为最优化方法与应用、智能计算.E-mail:wjcpig@126.com

doi:10.3969/j.issn.1007-7162.2016.02.007

中图分类号:F252; TP301

文献标志码:A

文章编号:1007-7162(2016)02-0037-05