基于遗传算法的应急物资供应点定位—分配问题研究综述

焦琴琴

摘 要：本文总结、分析了近年来国内研究中基于遗传算法求解的应急物资供应点定位-分配相关问题的文献，主要包括应急定位问题、应急物资分配问题、应急定位-分配集成问题的研究综述，最后总结得出研究现状和未来研究的发展趋势。

关键词：遗传算法；应急物流；定位-分配问题

一、 引言

震后应急物流是保障生命安全、减少财产损失的重要环节。以往的震后应急管理实践过程中出现了很多诸如应急物资供应点的定位不合理、应急物资分配不公平等一系列降低应急物流运作效率的问题，这就对我国的应急物流组织体系的构建和完善提出了迫切要求，因此，研究震后应急物资供应点的定位-分配问题，具有十分重大的现实意义。而针对应急物资供应点定位-分配问题的研究一般都属于NP-hard问题，往往是基于遗传算法进行求解的，下面分别对基于遗传算法的应急物资供应点定位-分配问题包含的三个方面进行研究综述。

二、 基于遗传算法的应急物资供应点定位-分配问题研究

（一）基于遗传算法的应急定位问题。刘红娟等（2010）[1]考虑设施点间距离、流量与安全性等道路特性，将其转换为道路的综合权值，建立了应急物流多设施选址模型，并采用遗传算法求解，最后用实例对模型进行了验证分析。李周清等（2011）[2]考虑震后物资调度的中转设施定位，以时间和成本最优为目标，建立了中转网点的定位模型，并用遗传算法求解。于鹏等（2012）[3]考虑设备应急抢修的时限要求和整个应急抢修系统的服务质量要求，采用0-1整数规划模型描述应急抢修点选址定位问题，针对该问题设计了一种混合遗传算法，并通过算例计算结果表明，该算法求得的结果要优于基于罚函数和采用简单修复算法的遗传算法。张刚红（2013）[4]考虑大规模应急设施的选址定位成为应急管理系统的关键，构建应急设施选址问题的集合覆盖模型，提出一种改进的并行遗传算法，并在Hadoop平台上编程实现。付德强等（2014）[5]研究了应急物资储备库的多目标选址决策模型，并设计了相应的多目标非支配排序遗传算法。

（二）基于遗传算法的应急物资分配问题。重大地震灾害发生以后，对应急物资进行科学合理的分配是震后应急物资保障系统的关键。

于振涛（2011）[6]研究应急物流系统中多级设施和多式联运救灾情况下的应急物资分配与调运问题，建立一个具有主从递阶关系结构的双层优化模型，并根据所建立的模型提出了一种改进的遗传算法。王增（2011）[7]考虑连续软时间窗限制，构建人员物资损失最小化和多点“物资消耗终点时间方差最小化”的双目标物资分配模型，采用遗传算法进行模型求解。赵明等（2012）[8]研究多供应点、多需求点的应急物资分配特性，构建以开始时间最早和出救点数目最少为目标的多目标优化模型，设计了遗传算法对最优调度方案进行求解。王旭坪（2013）[9]针对大规模突发事件下应急物资动态调度问题，构建以最小化灾民损失和车辆调度费用为目标的混合整数规划模型，设计了遗传算法进行求解。李沁鲜（2013）[10]运用遗传算法对所建立的应急救助物资配送车辆路径优化模型进行了求解和实例验证。

（三）基于遗传算法的应急定位-分配问题。定位-分配问题（Location-Allocation Problems，简称LAP）是根据需求点的地理分布、物资需求量，确定出某一地理范围内供应点的位置、数量和与需求点的指派方案。

李周清等（2010）[11]考虑增强大规模区际救援物资运作效率，建立了以运输成本和中转作业变动费用总和最小化为优化目标的应急物资中转设施点的定位-配给模型，并设计了一种运用矩阵编码的遗传算法。庄艳玲（2011）[12]考虑对于脆弱性高的受灾点提高覆盖水平，对脆弱性高的路线减少其运送物资的数量，在此基础上建立多目标优化模型，利用多目标的模糊处理将多目标模型转化成单目标模型，并设计两个遗传算法进行求解。俞武扬（2011）[13]考虑震后应急物资需要大规模协调配送的特性，构建了两级应急物流网络定位-分配模型，设计了一种基于整数编码的遗传算法并利用嵌入运输问题线性规划子算法进行求解。宫本东（2011）[14]考虑系统时间、成本和需求点受灾程度，构建冲突性多目标应急CLRIP模型以解决非常规突发事件环境下物流系统设施选址、路线选择和资源分配问题，并设计了多目标遗传模拟退火算法（GASA）对该模型进行求解。艾云飞等（2015）[15]将应急物资储备库选址定位问题和应急需求分配问题集成考虑，基于集合覆盖理论和引力模型，建立水上应急物资储备库选址-分配优化模型，并针对模型设计遗传算法。

三、综合评述

综上可以看出，我国对于应急救援物流的研究起步较晚，现有研究成果较少，但对于基于遗传算法求解的应急物资供应点的定位-分配问题的研究已经相对成熟。现有研究主要总结为下面几个方面：首先，以往的应急物资分配问题没有考虑到运输时间带来的时间延迟，总是将时间延迟和应急物资不同时段所带来的一个应急物资分配的多阶段问题忽略为单一阶段的救援问题；其次，现有研究主要是针对单一需求物资的分配问题，对于多种物资组合的物资分配问题研究是很有限的；再次，以往的震后应急定位-分配问题一般将目标设置为最小化期望成本、最大化期望收益、最大化期望满意度、最小化期望响应时间等，以期在突发事件前做好预案，使突发事件发生后能在最短时间内达到较好应急救援效果。

因此，现有研究还没有考虑到将受灾点对应急物资需求效用最大和以任意两受灾点需求效用未满足率差最小来表示的物资分配公平性最大作为优化目标。而对于多供应点、多受灾点、多应急物资种类、多目标、多周期动态的应急物资供应点定位-分配问题还有待进一步地深入研究。（作者单位：重庆工商大学商务策划学院）

基金项目：重庆工商大学研究生“创新型科研项目”，项目编号：yjscxx2015-41-18，项目名称：震后应急物资供应点的多目标动态定位-分配问题研究。

参考文献：

[1] 刘洪娟，罗挺，等.基于遗传算法的应急物流多设施选址模型研究[J].后勤工程学院学报，2010，03：46-50.

[2] 李周清，马祖军.基于改进GA的救援物资中转网点定位[J].计算机工程，2011，37（5）：4-6.

[3] 余鹏，隽志才.混合遗传算法求解应急抢修点选址问题[J].计算机应用研究，2012，30（2）：360-363.

[4] 张刚红.Hadoop下并行遗传算法研究及在应急设施选址中的应用[J].互联网天地，2013，5（8）：11-14.

[5] 付德强，王旭，张伟.基于 NSGA-Ⅱ的应急储备库多目标选址决策模型及算法研究[J].运筹与管理，2014，23（4）：64-69.

[6] 于振涛.震后应急物资分配与调运模型及算法研究[D].西南交通大学，2011.

[7] 王增.基于连续软时间窗限制的应急物资分配模型[D].华中科技大学，2011.

[8] 赵明，宋晓宇.利用遗传算法求解应急物资调度优化问题[J].沈阳建筑大学学报，2012，28（5）：944-948.

[9] 王旭坪，马超，阮俊虎.运力受限的应急物资动态调度模型及算法[J].系统工程理论与实践，2013，6：1492-1500.

[10] 李沁鲜.基于需求分析的灾害应急物资配送问题研究[D].兰州交通大学，2013.

[11] 李周清，马祖军.区际救援物资中转运输网点的定位-配给问题研究[J].计算机应用研究，2010，27（8）：2872-2874.

[12] 庄艳玲.考虑拓扑脆弱性的应急储备点选址与物资分配模型研究[D].东北大学，2011.

[13] 俞武扬.大规模应急物资中转运输问题研究[J].计算机工程与应用，2011，47（17）：1-3.

[14] 宫本东.面向非常规突发事件的集成定位-路径-分配模型与算法研究[D].东北大学，2011.

[15] 艾云飞，吕靖，张丽丽.水上应急物资储备库选址-分配优化模型[J].大连海事大学学报，2015，2：62-66.