突发事件下应急物资调度问题
研究 摘 要 人口、 资源、 环境、 公共卫生等社会矛盾随着社会的发展日益突出， 导致世界范围内的各种公共安全突发事件时有发生， 给社会、 经济等带来了严重的破坏和影响， 造成了生命和财产的巨大损失。 突发事件的危害程度、 危险系数相比以前也明显增高。 针对突发事件， 政府部门建立了相应的应急管理机构和应急反应体系， 调动大量的物资和人力进行救助。 因此往往会发生跨区域大规模的组织物流行为。 本文以国内外突发事件的
研究现状为基础， 介绍突发事件下应急物流的特征、 结构以及物资调度中存在的问题， 总结近年来
研究所取得的成果， 包括模型和算法。 在以上的基础上
研究应急物资在
突发事件中的调度问题， 重点
研究应急物资配置和调度方法， 解决在应急限制期内最可能的满足所有需求点的物资需求问题。 关键词： 突发事件； 应急物流； 物资调度
Abstract Population， resources， environment， public health and other social conflicts with the social development have become increasingly prominent， resulting in a variety of public safety emergencies worldwide have occurred to the social， economic and other serious damage and impact， resulting in the huge losses of life and property. Emergencies degree of harm， risk coefficient was significantly higher compared to the previous. For emergencies， the government departments to establish appropriate emergency management agencies and emergency response system， mobilizing substantial material and human aid. Therefore often will happen the large-scale the organization of logistics of the cross-regional behavior. In this paper， the research based on status of emergencies at home and abroad to introduce the characteristics of emergency logistics in emergencies， structure and materials scheduling problems， sum up the results of studies in recent years， including models and algorithms.On the basis of the above study of emergency supplies in the event of an emergency scheduling problem， focus on emergency supplies and scheduling method to solve the period of the emergency restrictions most likely to meet the material needs of all demand points. Key words： Emergencies； Emergency Logistics； Material scheduling
目录 1 引言 .............................................................................................................................................. 4 1.1 课题背景 ............................................................................................................................. 4 1.2 国内外
研究状况 ................................................................................................................. 4 1.3 课题
研究目的 ..................................................................................................................... 5 1.4 论文主要构成 ..................................................................................................................... 5 2 突发事件下应急物流分析与设计 ............................................................................................... 6 2.1 突发事件下的应急物流 .................................................................................................... 6 2.1.1 突发事件的定义 ..................................................................................................... 6 2.1.2 应急物流的定义 ..................................................................................................... 6 2.1.3 突发事件应急物流的特征 ..................................................................................... 7 2.2 应急物流系统 .................................................................................................................... 7 2.2.1 我国应急物流系统存在的问题 .............................................................................. 7 2.2.2 应急物流系统 ......................................................................................................... 8 2. 2. 3 应急物流系统的特征 ........................................................................................... 9 2.2.4 应急物流系统运作流程 ......................................................................................... 9 2.3 应急物资调度 .................................................................................................................. 10 2.3.1 应急物资调度的重要性 ........................................................................................ 10 2.3.2 应急物资调度的过程模型 .................................................................................... 11 3 基于蚁群模型的应急物资调度问题 ......................................................................................... 12 3.1 问题描述........................................................................................................................... 12 3.1.1 应急物资车辆调度的特征分析 ............................................................................ 12 3.1.2 相关的应急物资车辆调度信息 ............................................................................ 12 3.2 蚁群算法的基本原理 ....................................................................................................... 13 3.3 自适应蚁群算法 .............................................................................................................. 14 3.4 评定道路权重 ................................................................................................................... 15 3. 4. 1 基于层次分析法的道路权重的评定 .................................................................. 15 3. 4. 2 建立递阶层次结构模型 ...................................................................................... 15 3. 4. 3 影响因素权重值解算 ......................................................................................... 16 3.4.4 仿真实验 ............................................................................................................... 18 3. 5 确定型多出救点组合应急物资调度 .............................................................................. 20 3.5.1 单目标问题的求解 ................................................................................................ 21 3.5.2 两阶段目标问题的求解 ........................................................................................ 22 3.5.3 多目标问题的求解 ................................................................................................ 24 3.6 结合蚁群算法的应用实例 ............................................................................................... 24 4 结论 ............................................................................................................................................. 29 参考文献......................................................................................................................................... 30 致谢 ................................................................................................................................................ 31
1 引言 1.1 课题背景 我国是世界上遭受自然灾害最严重的国家之一， 这些突发的事件造成巨大的人员伤亡和经济损失， 需要大量的应急物资， 以资解决或处理伤者救助、 卫生防疫、 灾后重建、 恢复生产、 恢复秩序等， 否则受灾面积、 人员、 损失将会扩大， 这就需要迅速组织所需要的多种资源来应对这些突发事件。 和西方发达国家相比， 我国应急物资调度方面的
研究起步较晚，
研究投入较少， 技术水平还不够成熟。 在我国发生的一些事件已经暴露了我国在应急管理方面的缺乏， 因此
研究应急物资合理调度的问题已十分迫切。
研究资源调度问题， 首先可以给应急管理者提供一个决策的选择方案， 保证
策略的合理性； 再者可以实现对应急资源调度方案的优化。 应急物资调度问题本质上是一个组合优化问题， 问题的
研究成果可以推广到其他的应用领域中。 1.2 国内外
研究状况 YiW 和 zdamarL
研究了自然灾害发生后应急物流 FLP 和 VRP 问题， 并对应急物资的紧急配送和灾区人员撤离的协同性进行了
研究， 建立了一个动态的受伤人员撤退和救援物资供应的物流协同模型。 Fiedrich（2000） 等学者在时间、 资源数量有限的情况下， 将死亡人数最小作为
研究目标， 建立了向多个受灾地点分配和运输资源的优化模型。 Jae（2003）
研究了在路网情况未知条件下如何调度车辆运送的问题。 戴更新等人（2000） 针对多资源应急多点出救问题的特点， 建立多资源应急问题的数学模型。 引入连续可行方案的概念， 利用单资源问题的现有成果， 对该问题的求解。 刘春林等人（2001）
研究以物资需求为约束条件， 多个出救点的紧急物资调度问题。 根据连续应急问题的特点， 给出应急时间最早前提下出救点数目最少，
以及限制期条件下出救点数目最少的应急模型， 从理论上证明了模型求解方法的正确性。 卢安文等人（2003）
研究了紧急情况下的物流配送的必要性， 建立了考虑公路运输的紧急情况下的物流配送模型， 并考虑多种运输方式， 以时间、 费用为目标建立了 0-1 整数规划模型及目标规划模型。 计雷（2005） 提出了应急管理中的救援物资运输问题是最小化运输费用与运输时间的多目 标组合优化问题， 但是该文献并没有涉及到问题模型的建立与实现。 宋明安（2005）
研究以最小化运输费用为目标， 在不同的约束条件下的应急救援物资运输的问题。 张毅等人（2006） 分析应急物资车辆运输线路的选择问题，
运用多属性决策理论建立评价备选线路决策效用函数的数学模型。 从以上的文献回顾中， 我们可以看出国内的学者也主要是假设某个或某几个约束条件， 例如： 成本最小、 时间有限、 运输路径、 多目标等， 从而建立相应的优化模型求解。 1.3 课题
研究目的 由于应急物流问题是一个比较新的
研究领域， 虽然已有学者对应急物资的调度问题进行了一些
研究， 但是还有很多有待
研究的方面。 本文主要
研究以自然灾害为背景的应急物资调度问题。 它以传统的正常经济条件下的物资调度为基础，结合自然灾害背景下应急物资调度的特点， 考虑出救点的级别不同， 以多层次级出救点模型为前提，
研究单物资多受灾点的应急物资调度模型。 1.4 论文主要构成 本文各章节的主要内容如下： 第一章： 介绍
研究课题的背景、 国内外
研究现状、 课题
研究的目的。 描述本文的框架和主要内容。
第二章： 对突发事、 应急物流等一些基本概念进行论述， 比通过与传统物流的比较， 深入分析突发物流的特点。 在此基础上综述应急物流系统的运作流程和物资调度的一些问题。 第三章： 将应急物资配置和调度方法作为
研究的主要目的， 建立模型， 并用实例验证模型的有效性。 第四章： 对全文进行总结， 并提出未来
研究的方向。 2 突发事件下应急物流分析与设计 2.1 突发事件下的应急物流 2.1.1 突发事件的定义 突发事件具有突发性、 紧急性、 不确定性等特征。 因发生的规模、 地点、 事前准备等不同对社会产生不同的后果， 我国将突发事件分为四类： 自然灾害、 公共卫生、 事故灾难、 社会安全事件。 这些事件会对生命、 财产造成一定损害。 突发事件的定义可以分为狭义和广义两种。 狭义的突发事件定义： 在一定的区域内突然发生， 规模较大且造成广泛的社会负面影响， 对生命和财产造成严重威胁的时间和灾害。 广义的突发事件定义： 在计划之外或者在认识范围之外突然发生， 对其利益具有损伤性或潜在的危害性的一切时间。 2.1.2 应急物流的定义 应急物流与普通物流一样， 由流体、 载体、 流向、 流程、 流量等要素构成，具有空间效用、 时间效用和形质效用。 应急物流的。 应急。 二字本身带有一定的军事色彩， 但应急物流和军事物流不同。
军事物流的指令性比较强， 尤其在战争爆发的时候， 始终把军事利益放在首位。 应急物流是指为公共卫生事件、 自然灾害、 特大事故等突发性事件提供所需
应急物资为目的， 以追求时间效益最大化和灾害损失最小化为目标， 借助现代信息技术， 整合应急物资的运输、 包装、 装卸、 搬运、 仓储、 流通加工、 配送及相关信息处理等各种功能而形成的特殊的物流活动。 2.1.3 突发事件应急物流的特征 突发事件下的应急物流通过物流效率实现其物流效益， 而普通物流既强调效率又强调效益。 突发事件的应急物流是一般物流的一个特例， 具有区别一般物流的特点： 突发性和不可预知性、 峰值性、 弱经济性、 需求的随机性、 政府和市场共同参与性、 非常规性等特点。 目前国内突发事件下应急物流具备自己的特点，主要表现为： 政府高度重视， 企业积极参与； 军民携手合作， 军队突击力强； 平时有准备、 预案演练到位等。 2.2 应急物流系统 2.2.1 我国应急物流系统存在的问题 1、 政府应急快速反应机制不健全 国家虽然一次颁布了一系列条理、 法规， 来最大限度地降低突发事件造成的影响和损害， 保证应急行动的顺利实施， 但是我国应急法制建设还存在很多问题；各级政府、 部门几乎都有应急预案， 但其由于职能交叉、 应急空白区较多导致衔接不紧密， 未形成一个完善的应急体系。 还有些基层工作者对某些法规条理的认知度不够深刻， 因而严重影响了应急工作的效率。 2、 缺乏应急管理的思维方式 应急物资调度工作者在应对突发事件的思维意识、 应急管理、 应对机制等方面存在较大差异性和局限性， 常常以个人常态思维方式考虑突发事件， 因此很难适应应急物流系统的迅速反应需求； 而且社会、 各机构间缺乏联动机制。 政府部门、 企业、 社会团体、 个人等往往都会不同程度的介入其中， 这就加大了合作和协调的难易程度。 3、 缺乏所需的基础数据库支持 由于信息获取的不充足和不及时， 应急物资调度者时常不能获得准确的物流
需求、交通情况和现场等信息， 因而严重影响了应急物流的运作质量和运作效率。 4、 灾害现场状况出乎意料和所需的技术、 作装备等严重不足 由于自然灾害发生的不可预测性和时间、 地点的随机性， 导致应急物流准备不充分， 不能满足要求； 同时， 突发事件经常伴随着道路被破坏、 现场情况恶化、缺乏所需的技术支持和工作装备等情况， 物流工作常常被耽搁甚至被完全中断 2.2.2 应急物流系统 应急物流系统是指为了完成突发性的物流需求， 由各个物流元素、 物流环节、物流实体组成的相互联系、 相互协调、 相互作用的有机整体。 应急物流系统的结构包括控制层、 决策层、 数据层和环境层四个层次， 其结构如图 2-1 所示。 制层 策层 据层 境层 应急物资采购和租用运载工具 应急物流方案实施及运输过程监控调方案实施效果评估及应急需求信息反评估突发事件并制定所需应急物资的品种租用所需运载工具 确定应急物流方案 应急 物资 信 息系 统或数据仓运载工具信息系 统或数据仓库 应急物流预 案数据库 行政制度公共政策 法律制度 突发事件触发 应急物资 供应商 运载工具 供应商 控决数环
图 2-1 应急物流系统结构图 2. 2. 3 应急物流系统的特征 1、 应急物流系统的。 时间。 要素特征 应急物流系统具有一般物流系统的六个基本要素， 还具有特有的。 时间。 要素。 由于应急物流的突发性特征， 即应急物流需求发生的时间具有极大的不确定性和应急物流需求时间约束的紧迫性， 肯定了。 时间。 在应急物流系统中是一个至关重要的系统因素， 即应急物流系统有七个主要因素： 流速、 载体、 流程、 流量、 流向、 流体和时间。 2、 应急物流系统的快速反应能力 应急物流的系统具有快速反应能力、 一次性和临时性的特性， 这是由应急物流的突发性和随机性决定的。 应急物流系统的这一特性使得一般的企业内部物流或供应链物流系统的反复性、 稳固性和循环性不同于应急物流系统。 3、 应急物流系统的开放性和可扩展性 应急物流需求同时还应具有随机性和不确定性， 这两种特性决定了应急物流系统在设计上应该具备开放性和可扩展性。 应急物流的需求和供给在突发事件发生前是不确定的， 但在发生之后是确定的， 必须将其纳入应急物流系统中。 2.2.4 应急物流系统运作流程 对应急物流系统的运作流程必须进行全面的考虑， 进行充分的分析， 才能在灾难来临的时候既能保证人民的生命财产， 又能把物流的效益发挥到最大。 分析应急物流系统的特性后， 可将应急物流系统设定以下几个环节： 协调指挥中心、物资供给端、 物流中心、 物资需求端。 各个部门之间的信息双向传递， 实时回馈。其运作流程可如图 2-2 所示：
图 2-2 应急系统运作流程图 2.3 应急物资调度 应急物资主要来源于： 储备物资、 征用物资、 市场采购、 组织突击研制和生产、 组织捐赠这 5 个方面。 应急物资调度是指物资协调指挥中心在突发事件爆发时， 将这些救援物资从仓库或者中转站快速的用各种交通工具输送到指定事故发生地。 应急物资调度应考虑物资的需求量、 运输工具、 运输方式等方面， 并且随着突发事件的发展进行不断的调整， 实现各个阶段的目标。 2.3.1 应急物资调度的重要性 应急物资协调指挥中心处于应急管理的核心位置， 是应急管理的重要组成部分。 应急物资协调指挥中心对应急物资的调度发挥着至关重要的作用。 应急物资调度的目标就是保证应急物资的合理有效分配到受灾地区， 进一步为应急管理的有效开展提供强有力的物资保障， 最大程度的减轻突发事件所带来的生命财产损失。 应急物资协调指挥中心 物资供应端 物资需求端 物资 中心 采购---运输-------分拣、 加工、 包裹------配送---发放 信息流 物流
2.3.2 应急物资调度的过程模型 应急物资协调中心在调度应急物资的过程中应全面权衡， 处理多方面问题。其中包括应急物资需求预测、 应急物资筹备、 应急物资储备、 应急物资运输、 应急物资供应、 应急物资调度评估等。 其流程如图 2-3 所示： 2-3 应急物资调度流程图 突发事件 应急物资协调指挥中心 应急物资需求预测 应急物资筹备 应急物资储备 应急物资运输 应急物资供给 应急物资调度评价
3 基于蚁群模型的应急物资调度问题 3.1 问题描述 3.1.1 应急物资车辆调度的特征分析 应急救援车辆调度要求及时运输救援物资和救援人员到达灾区。 同日常的车辆运输相比， 应急救援车辆的调度具有以下特点： (l) 紧急性。 由于突发事件发生突然， 变化剧烈， 客观上要求车辆调度决策快速、有效， 以保证救援运输任务的完成。 (2) 不确定性和时变性。 突发事件发生的时间和地点不可预知， 而且很难预测其变化情况； 无法在应急反应初期准确计算各类救援物资和救援人员的需求量和供给量； 由于临时交通情况的影响， 通行时间也具有不确定性；
突发事件中人的心理和行为特征也是不确定的； 应急交通管理措施对车辆调度的影响也具有不确定性。 正是由于这些太多的不确定性， 故本
研究课题在设计确定型多出救点组合应急物资调度的方案时， 利用了模糊数学的区间数来表示这种不确定性。 (3) 弱经济性。 突发事件对社会系统的基本价值和行为准则架构产生严重威胁。在应急反应中， 应首先尽可能控制事态蔓延、 减少人员伤亡， 尽快恢复社会秩序等非经济目标往往是救援车辆调度的最重要目标； 而成本、 效益等经济目标不再是唯一目标。 (4) 资源有限。 突发事件发生后， 对救援物资和救援人员的需求剧增， 在短时间内通常没有足够的资源完全满足这些需求。 3.1.2 相关的应急物资车辆调度信息 1. 调查灾区路径信息 在确定应急物资配送中心和应急服务设施点的位置后， 可根据实际情况的路径信息确定应急物资配送中心与应急服务设施点之间的最优路径方案。 为了使应
急物资能尽快到达应急地点并且以尽可能小的代价到达应急地点， 确定调度方案时一般有调运时间最短和调运费用最省两个目标函数。 这两个目标函数中， 应急物资调运的时间长短往往直接关系到救援的成功与否， 所以将调运时间最短作为主要目标函数。 在求得最优路径后， 同时可求得车辆在最优路径上的运行时间，即最短时间。 2. 应急救援车辆调度参数 在进行应急救援车辆调度时， 需根据调度要求设置一些车辆调度参数。 主要的调度参数包括以下几种： 1) 应急救援限期条件。 即满足应急救援的时间紧迫性条件。 如在地震灾害发生后， 有效抢救生命的最佳时间是 72h 之内。 在这有限的时间段内进行高效、 有序的应急救援活动， 才能将灾害造成的损失减少到最低限度。 如果限期时间定得适当， 既可以减少人员伤亡和财产损失， 又可以减少组织应急救援的成本。 2) 应急物资的优先权。 应急物资的优先权对确定调度方案也至关重要， 它直接影响调度方案的设计。 不同应急物资未满足要求时所造成的损失不同， 损失的程度和物资的重要性、 时效性和缺口程度等有关。 不同的应急物资其运输优先权不同。 人的生命是最宝贵的， 伤员的救助在应急救援中必须放在首要位置， 故认为伤员的运输优先权高于救灾物资， 且重伤员的运输优先权高于轻伤员。 另外， 运输车辆的载重量、 可以投入应急物资调度的车辆数量、 各个应急服务设施点对应急物资的需求量等都是需要预先确定的调度参数。 3.2 蚁群算法的基本原理 蚁群优化算法是模拟蚂蚁觅食的原理， 设计出的一种群集智能算法。 蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质， 并在觅食过程中能够感知这种物质的强度， 并指导自己行动方向， 它们总是朝着该物质强度高的方向移动， 因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。 某一条路径越短， 路径上经过的蚂蚁越多， 其信息素遗留的也就越多， 信息素的浓度也就越高， 蚂蚁选择这条路径的几率也就越高， 由此构成的正反馈过程，
从而逐渐的逼近最优路径， 找到最优路径。 3.3 自适应蚁群算法 基本蚁群算法存在一些缺点和不足。 我们在对基本蚁群算法的原理进行分析后不难发现： 基本蚁群算法寻优机制包含两个基本阶段： 适应阶段和协作阶段。在适应阶段， 各候选解根据积累的信息不断调整自身结构， 路径上经过的蚂蚁越多， 信息量越大， 则该路径越容易被选择， 时间越长， 信息量会越小； 在协作阶段， 候选解之间通过信息交流， 以期望产生性能更好的解。 基本蚁群算法主要依据的是信息正反馈原理和某种启发式算法的有机结合， 这种启发式算法在构造解的过程中， 利用随机选择
策略， 这种选择
策略使得进化速度较慢， 正反馈原理旨在强化性能较好的解， 却容易出现停滞现象。 这是造成基本蚁群算法的不足之处的根本原因。 我们首先从选择
策略方面进行改进
研究， 我们采用确定性选择和随机选择相结合的选择
策略， 并且在搜索过程中动态地调整作确定性选择的概率。 当进化到一定代数后， 进化方向已经基本确定， 这时对路径上信息量作动态调整， 缩小最好和最差路径上的信息量的差距， 并且适当加大随机选择的概率， 以利于对解空间的更完全搜索， 从而可以有效地克服基本蚁群算法的两个不足。 这种改进的方法属于自适应方法。 从前面对基本蚁群算法的原理进行分析可以看出， 当处理大规模问题运算时， 蚁群算法中信息素挥发因子 P 的大小直接影响蚁群算法的全局搜索能力及其收敛速度。 针对这个缺点， 这里探讨了一种自适应调整信息素挥发因子的蚁群算法改进
策略， 该改进算法可以通过自适应的改变信息素挥发因子 P 的值来提高算法的全局搜索能力， 从而可以避免陷入局部最优解。 为了提高基本蚁群算法的全局搜索能力， 提高其搜索速度， 将基本蚁群算法作如下改进： (1) 保留最优解。 在每次循环结束后， 求出最优解， 并将其保留。 (2) 自适应地改变 P 值。 当路径规模较大时， 由于挥发系数 P 的存在， 使那些从未被搜索到的路径上的信息量减少到接近 0， 降低了算法的全局搜索能力， P 过
大也会降低全局搜索能力， 减小 P 又会使算法的收敛速率降低； 因此可以采用自适应地改变 P 的值。 方法如下： 设置 P 的初值为0( )P t1�8�8 ， 当求得的最优解在 N次循环内没有明显改进时，P 减为： �8�0min0.95 (1)( )P tpP t�8�2�8�6�8�8min若0. 95P(t-1) P否则 （3-1） 其中minP为 P 的最小值， 可以防止 P 过小而降低算法的收敛速度。 同时， 为了提高蚁群算法的全局搜索能力， 提高其搜索速度， 还在每次循环结束时求出最优解，并将其保留。 3.4 评定道路权重 在基本蚁群算法的数学模型里， 蚂蚁 k 从所在节点搜索下一未访问节点的过程中， 是根据其邻接表中各条路径上的信息量�8�7 �8�8ijt�8�3及路径的启发信息�8�7 �8�8ijt�8�1来计算状态转移概率的， 对路径的假设是一种理想化的状态， 并没有考虑道路的实际状况， 如道路等级、 交通流量、 天气状况等。 而应急救援路径选择需要综合考虑道路的实际属性， 包括运输的时效性、 安全性、 经济性等因素。 3. 4. 1 基于层次分析法的道路权重的评定 层次分析法（AHP） 是一种确定权向量行之有效的方法。 这一方法基于对问题的全面考虑， 将定性与定量分析相结合， 将决策者的经验予以量化， 是一种系统化的、 层次化的分析方法。 决策支持系统软件。 专家选择系统。 就是主要以AHP 为主要原理编写的。 3. 4. 2 建立递阶层次结构模型 在对路径进行选择时， 人们往往更倾向于走宽敞、 顺畅的大道， 有的路径虽然较短， 但有可能会崎岖不平或道路狭窄， 或经常发生交通阻塞等问题， 因而可能需要较长时间通过； 全面地考虑这些因素， 就形成了一个如何规划一条尽量满足各种要求、 较为合理路径的问题。
显然， 人们对合理路径选择主要考虑以下几个方面的内容： (1) 最短距离寻优；(2) 道路等级寻优； (3) 交通流量寻优； （4) 天气状况寻优。 道路属性数据加权的关键在于指标因子的选择。 影响道路权重的因素有很多。 AHP 法首先要对问题所涉及到的所有因素进行分类， 找出相互关系， 构造一个多层次的分析结构模型。 全部因素分为目标类、 准则类、 方案类， 再求出各个评价准则对最终目标的权重， 再分析各个待选方案对各个评价准则的权重， 最后计算出各个待选方案对最终目标的权重。 本文将层次结构分为 2 层(如图 3-1 所示) ， 目标层 z 和准则层 A。 目标层的路径权重为 w； 准则层各个指标对于目标层的权重分别为1234w ,w ,w ,w 。 图 3-1 路径权重层次结构模型图 3. 4. 3 影响因素权重值解算 首先利用层次分析法对准则层各指标对于目标层的权重1234w ,w ,w ,w 进行解算。 第一步： 构造判断矩阵。 判断矩阵的元素是准则层元素两两比较的结果。 依据文献 1 的数据及决策者的经验判断， 构造判断矩阵 A 如表 3-1。 表 3-1 判断矩阵 A Z A1 A2 A3 A4 A1 1 5 5 3 A2 1/5 1 1 1 A3 1/5 1 1 1 A4 1/5 1 1 1 第二步： 计算准则层权重。 这里用特征值法求解准则层权重， 方法如下： 目标层 Z：ijw 路径距离1 w 道路等级w 2交通流量3 w 天气状况w 4
maxAW=W�8�5 （3-2） 式中，max�8�5是 A 的最大特征值， W 是对应的特征向量， 经归一化后就可作为准则层权重向量。 基于matlab编程计算得判断矩阵的最大特征值为 4. 0328； 对应的特征向量为W=(0.5848 0.1320 0.1320 0.1513) 。 第三步： 一致性检验。 构造判断矩阵时， 要对矩阵的一致性进行检验， 方法如下： CRCIRI�8�8 （3-3） 式中， CR为一致性比例， 当 CR<0.1时， 认为判断矩阵的一致性是可接受的， 否则应予修正； CI 为一致性指标， 且max(�8�5)(1)nCIn�8�2�8�8�8�2；RI 为平均随机一致性指标， 由判断矩阵的阶数决定， n=4 时， RI 取值 0. 89。 基于 matlab编程计算得 CR=0.01228 ， 认为判断矩阵的一致性是可接受的。 2341()()ijssWwrwfwwvv w�8�7�8�8�8�0�8�7 �8�0�8�7�8�0�8�7 （3-4） 式中，1234w ,w ,w ,w 为准则层各因素对于目标层的权重系数； S 为路径距离；v 为道路设计平均时速， 依据设计资料获得； r 为道路等级， 依据公路使用任务、功能和适应的交通量划分的 5 个等级由高到低分别赋值(0. 2、 0. 4、 0. 6、 0. 8、1. 0) ； f 为交通流量， 与设计交通流量作比较， 比值由低到高赋(0-l) 区间内的实数； w 为天气状况， 车辆行驶的适宜度由高到低赋(0-l) 区间内实数。 由以上的层次分析法算出各条路径上的权重值后， 即可计算引入路径权重后的状态转移概率， 其计算公式如下： �8�0[�8�3( )] [t( )]t[( )]t,[�8�3( )]t[�8�1( )]t[( )]0,( )tijij�8�4ij�8�5kisisis allowedk�8�3�8�6kwj allowed�8�3w tkijj allowed�8�4p�8�5�8�0�8�0�8�1�8�8若若 （3-5） 式中ijw (t) 为路段<i,j>在 t 时刻的权重量， �8�0 为权重指数， 根据具体情况和要求确定。
3.4.4 仿真实验 为了检验本章在引进路径权重之后的自适应蚁群算法的性能， 仿真算例选取如表 3-2 的 10 个节点进行最优路径选择分析。 0 号节点为救援仓库， 卡车载重量为 5 吨， 设定等待时间不超过 205， 若道路ij(V,V ) 之间不连通， 则将ij d 置为1000。 试验中蚁群算法各参数用实验方法确定其最优组合， 其设置情况见表 3-3，PC 机上用 matlab语言编程实现该引进路径权重的算法， 并将结果与不引入路径权重的蚁群算法得到的结果进行比较分析。 表 3-2 点坐标及配送量 节点编号 0 1 2 3 4 5 6 7 8 9 横坐标 x 0 0 -3 3 -4 3 -3 2 1 -1 纵坐标 y 0 3 -3 -1 -1 4 0 1 3 -1 配送量（t） 0 1.8 0.8 1.5 2.5 0.2 2.4 0.5 0.6 0.9 表 3-3 法的参数设置情况 m Alpha Beta Gama Rho NC_max Q W 60 1 1 15 0.15 5 15 5 不引入路径权重时, 得应急救援最优路径为: 0�8�19�8�12�8�14�8�10 0�8�13�8�18�8�16�8�15�8�11 �8�10 0�8�17�8�10 最短运输总距离: 31. 3985。 最短路径优化结果和各次迭代 m 只蚂蚁的平均距离和最短距离见图 3-2。 图 3-2 未引入路径权重的优化结果图
当引入路径权重， 若道路ij(V,V ) 之间不连通， 则设置路径权重值为。， 且路径权重矩阵分布如表 3-4 时， 修改原有matlab程序， 运行得最优路径为: 0→8→1→5→6→3→0 0→9→2→4→0 0→7→0 最优运输总距离: 33. 0647。 表 3-4 路径权重矩阵表 ijw 0 1 2 3 4 5 6 7 8 9 0 0 14 9 15 20 10 5 13 16 12 1 14 0 8 12 9 7 15 4 11 15 2 9 8 0 7 19 14 5 17 12 16 3 15 12 7 0 9 15 12 10 7 14 4 20 9 19 9 0 8 11 14 17 8 5 10 7 14 15 8 0 9 13 10 6 6 5 15 5 11 9 0 7 0 15 21 7 13 4 17 10 14 13 7 0 15 10 8 16 11 12 7 17 10 18 15 0 8 9 12 15 16 14 8 6 21 10 8 0 最优路径优化结果和各次迭代 m 只蚂蚁的平均距离和最短距离见图 3-3。 图 3-3 引入路径权重后的优化结果
引入路径权重矩阵后， 虽然最短运输总距离有所增加， 但是它考虑了一些实际情况如道路等级、 交通流量、 天气状况后， 完成物资配送任务所需时间更短，这在应急救援最优路径选择中具有更重要的意义。 该小节内容将层次分析法融入自适应蚁群算法， 并应用于应急救援物资配送时的路径寻优， 通过matlab仿真实验， 不仅说明了该套方案的可行性， 而且更具有针对性和实用性， 它从实质上提高了应急救援工作效率。 为了方便叙述和简化问题， 很多基本原理只给出计算方法， 此外， 本文在层次分析法建模时只考虑了4 个准则层的影响因素， 这也是比较片面的。 设计功能更细分、 参数组合更合理的仿真实例并将该套方案融入应急救援辅助决策支持系统是后面的
研究内容。 3. 5 确定型多出救点组合应急物资调度 我们从确定型多出救点组合模型(仅考虑单资源问题) 入手， 设l2A ,A ,.....,A为 n 个应急服务设施点(可出救点) ， A 为应急地点， x 为应急物资需求量，nx (x >0),i=1,2,,n,�8�2�8�2�8�2�8�6出一确定参与应急的出救点及各自提供应急资源数量的方案， 在保证应急资源需iA 的资源可供应量为iiii=1xx�8�6， 从iA 到 A 需要的时间为it ， 要求给求的条件下， 应急开始时间最早。 设任一方案必描述为： 112233nntttttttt={(A ,x' ),(A ,x' ),(A ,x' ),,(A ,x' )}�8�3m�8�6�8�2�8�2�8�2 （3-6） 其中，kkkiii10','kxxx�8�8�8�0�8�0， 且l2mi ,i ,.....,i ， 为1,2,,n�8�2�8�2�8�2子列的一个全排列。 我们用( )T �8�3 表示方案�8�3 对应的开始时间， 那么最早应急时间可以表示为：
min ( )T�8�3 �8�6�8�3�8�3 （3-7） �8�6 表示所有方案构成的集合。 不失一般性， 不妨假设12nttt�8�0�8�0�8�2�8�2�8�2 �8�0， 则有最早紧急时间方案的表达形式�8�3�8�9， 如果有： 1kk11ppk�8�6k�8�6xxx�8�2�8�8�8�8�8�0�8�0 （3-8） 那么： p-1�8�61122pkk=1={(A ,x ),(A ,x ),,(A ,x )}�8�3�8�9�8�2�8�2�8�2 （3-9） 该方案的特点是： 依次选取离事故地点 A 最近的出救点iA 参与应急， 如果它的全部物资依旧小于需求量， 再让次近出救点i+lA 参与应急服务。 下面
研究一次性消耗系统方案的求取。 所谓一次性消耗系统， 它是与连续性消耗系统相对而言的。 我们把物资全部到达才能进行应急活动的系统成为一次性消耗系统； 而连续性条件就是要保证在任何时刻已到达物资量满足应急所需的物资消耗， 即不能出现因物资供应不足引起应急活动停止。 这类问题广泛适合于诸如连续性应急生产系统、 电力供应系统、 供暖供气系统、 消防系统以及其它复杂的社会经济系统等。同样是对于前面的模型， 我们用 ( )T �8�3 表示方案�8�3 对应的最早应急时间， 对于一次性消耗系统， 有： j1,2,...max�8�8( )�8�3jmTt�8�8 (3-10) 下面从单目标问题， 两阶段目标问题， 多目标问题逐层深入的对一次性消耗系统进行
研究。 3.5.1 单目标问题的求解 这里的单目标是指最早应急时间， 即要求开始应急救援的时间越早越好。 根据前面不失一般性的假设： 12nttt�8�0�8�0�8�2�8�2�8�2 �8�0， 根据前面�8�3�8�9的定义， 在pt 之前能够到达的全部物资量肯定小于 x， 故最一早应急时间一定不小于pt 。 所以， 如果�8�3�8�9为该单目标问题的最优方案的话， 则有：
j1,2,...max�8�8(�8�3�8�9)pjpTtt�8�8�8�8 (3-11) 对于其它任何可行方案�8�3 ， 必有 ( )pTt�8�3 �8�6。 例如， 对于这样一个的单目标问题， 已知应急地点需要的应急物资数 x=50。 现有 10 个可指派的出救点： 1210,,,A AA�8�2�8�2�8�2， 它们分别的最早应急时间和可供出调的应急物资数如下表 3-5 所示。 我们需要确定最佳的物资调度方案。 表 3-5 单目标问题的仿真数据 1A 2 A 3A 4 A 5A 6 A 7 A 8A 9 A 10A iT 1 2 2 3 4 6 6 8 10 15 i X 5 10 8 9 7 12 14 9 15 10 根据但目标问题的思想， 即按最早应急时间的要求， 可以很容易得出最佳物资调度方案�8�3�8�9如下： 123456{(,5),(,10),(,8),(,9),(,7),(,11)}AAAAAA�8�3�8�9�8�8 (3-12) 最短应急时间 ()T �8�3�8�9为 6(�8�3�8�9�8�8)6Tt�8�8 (3-13) 3.5.2 两阶段目 标问题的求解 以“最早应急时间” 的方案可能不止一个， 但是无论从费用还是系统稳定性的角度考虑，
研究“最早应急时间前提下的出救点数目最少目标” 的两阶段问题更具有实际意义。 因为出救点的多少直接关系到整个应急系统的稳定性和可靠性， 而且从费用的角度来看， 出救点的多少又直接关系到应急系统的总费用。 所以要求出救点尽可能少具有一定的实际意义。 同理， 假设方案厂为最早应急时间条件下的最优方案， 并且 ()pTt�8�3�8�9�8�8， 若用( )N �8�3 表示方案�8�3 对应的出救点的数目，�8�6表示所有可行的方案集。 那么两阶段问题的模型可以表述如下：
( )�8�3min( )�8�3�8�8. .pTtNs t�8�3 �8�6�8�3�8�3�8�4�8�5 (3-14) 因为各个出救点到应急地点的运输时间不大于pt ， 的可出救点数目可能超过p 个， 不妨设为 q 个， 则根据前面的假设， 有1ppqttt�8�0�8�8�8�8�8�2�8�2�8�2 �8�8。 显然， 两阶段问题的最优方案对应的出救点一定是l2qA ,A ,.....,A 的一个子列。 又因为出救点l2qA ,A ,.....,A 的可出救资源量分别为l2qx ,x ,.....,x ， 假设有12qiiixxx�8�6�8�6�8�2�8�2�8�2， 其中l2qi ,i ,.....,i ， q 的一个排列， 则我们可以用下面的模型表示两阶段目标问题的最优方案。 112233kk-1�8�6tttttttjj=1={(A ,x ),(A ,x ),(A ,x ),,(A ,x )}�8�3�8�2�8�2�8�2 ji1,2,...maxj�8�8pktt�8�0 12kiiixxx�8�6�8�6�8�2�8�2�8�2 (3-15) jj1ii11k�8�6kjjxxx�8�2�8�8�8�8�8�0�8�0�8�6 同样对于前面的那个针对单目标问题的例子， 如果用求解两阶段目标问题的思路来解， 可知最早应急时间不大于6t =6的可出救点数目为 7 个。 最佳出救方案为： 76243{ (, 1 4 ) , (, 1 2 ) , (A, 1 0 ) , (A, 9 ) , ( (3-16) , 5 ) }AAA�8�3 �8�8并且最早应急时间为 6， 出救点数目为 5， 比之前用单目标思想求解的方案的出救点数少一个， 提高了应急系统的可靠性和稳定性， 而且节省了费用。
3.5.3 多目标问题的求解 上述两种问题的求解比较简单， 但当决策者特别注重应急系统稳定性或费用时， “出救点数目最少” 应该作为另外一个优化目标， 这样就产生了基于“最早应急时间” 和“出救点数目最少” 的多目标模型。 这一问题的求解将考虑时间和出救点数目的折中， 充分顾及人的主观性。 这类问题的求解模型表述如下： ( )�8�3( )�8�3min. .�8�3TNs tX�8�3�8�4�8�5�8�3 (3-17) 其中，( )T �8�3 表示方案尹的最早应急时间，( )N �8�3 表示方案沪的出救点数，X 表示所有可行方案的集合。 3.6 结合蚁群算法的应用实例 现以 1998 年洪涝灾害受灾严重的公安县地区为例进行应急物资调度路径优化的说明。下图 3-4 是公安县地区交通示意图， 应急救援中心设立在公安县城区，应急物资从这里开始分别调往各个受灾点救助站， 包括麻豪口镇、 藕池镇、 毛家港镇、 夹竹园镇、 闸口镇、 章田寺乡、 南平镇、 章庄铺镇、 孟家溪镇、 甘家厂乡。我们限定用载重量为 5 吨的货车运输， 且各个受灾点的应急物资需求量如下表3-6 所示。
图 3-4 公安县地区交通示意图 表 3-6 各受灾点应急物资需求 救助站 公安县 麻豪口镇 藕池镇 毛家港镇 夹竹园镇 闸口镇 章田寺乡 南平镇 章庄铺镇 孟家溪镇 甘家厂乡 配送量 （t） 0 1.2 1.6 1.0 1.4 1.3 0.9 1.8 1.3 1.5 1.2 为了尽量节省应急救援物资运输的开销， 考虑到各受灾区应急物资需求量均小于货车载重量， 所以在保证最短应急时间要求的条件下， 每个受灾区救助站需求的救灾物资尽量只用一辆货车运输。 从公安县地区的交通示意图上可以测量出应急救援中心以及各个救助站的地理位置坐标以及它们之间的距离矩阵分别如下表 3-7、 3-8 所示。 表 3-7 应急救援中心以及各个救助站的地理位置坐标 救助站 公安县 麻豪口镇 藕池镇 毛家港镇 夹竹园镇 闸口镇 章田寺乡 南平镇 章庄铺镇 孟家溪镇 甘家厂乡 横坐标 （x） 275 337 347 141 180 256 259 151 34 161 148 纵坐标 （y） 331 246 15 318 256 187 117 180 159 121 11 表 3-8 应急救援中心以及各个救助站之间的距离矩阵 救助站 公安县 麻豪口镇 藕池镇 毛家港镇 夹竹园镇 闸口镇 章田寺乡 南平镇 章庄铺镇 孟家溪镇 甘家厂乡 公安县 0 14. 1 Inf 15. 4 16. 2 18. 6 Inf Inf Inf Inf Inf 麻豪口镇 14. 1 0 35. 1 Inf Inf 24. 2 36. 2 Inf Inf Inf Inf 藕池镇 毛家港镇 15.4 夹竹园镇 16.2 闸口镇 章田寺乡 南平镇 章庄铺镇 孟家溪镇 甘家厂乡 Inf 35. 1 Inf 0 Inf Inf 0 Inf 12.9 Inf Inf 15. 5 Inf Inf Inf Inf Inf Inf Inf 36. 4 Inf Inf Inf 12.9 0 12.7 Inf 12.1 Inf Inf Inf 18.6 24.2 Inf Inf 12.7 0 8.9 13.2 Inf Inf Inf Inf 36.2 15.5 Inf Inf 8.9 0 Inf Inf Inf 43.8 Inf Inf Inf Inf 12.1 13.2 Inf 0 16.8 8.1 Inf Inf Inf Inf Inf Inf Inf Inf 16.8 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 8.1 Inf 0 12.2 Inf Inf 36.4 Inf Inf Inf 43.8 Inf Inf 12.2 0 为了更直观的描述应急救援中心与各救助站的相对位置关系以及便于接下来的路径优化
研究， 根据前面的公安县地区的公路交通示意图及其道路相关数据， 得该地区的网络示意图如下图 3-5。
图 3-5 应急救援中心与各救助站关系的网络示意图 从公安县地区的交通示意图上可以分辨出各段道路的等级， 包括高速公路、国道、 省道、 村级公路， 另外结合道路的曲直、 坡度以及车流量等实际情况，
运用前面层次分析法的理论， 得出应急救援中心以及各个救助站之间的权重矩阵如下表 3-9 所示。 表 3-9 应急救援中心以及各个救助站之间的权重矩阵 救助站 公安县 麻豪口 藕池镇 毛家港 夹竹园 闸口镇 章田寺 南平镇 章庄铺 孟家溪 甘家厂 公安县 0 1 Inf 1. 2 1 1. 3 Inf Inf Inf Inf Inf 麻豪口 1 0 1 Inf Inf 1. 2 1. 1 Inf Inf Inf Inf 藕池镇 毛家港 夹竹园 闸口镇 章田寺 南平镇 章庄铺 孟家溪 甘家厂 Inf 1.2 1 Inf 0 Inf Inf 0 Inf 1.2 Inf Inf 1. 4 Inf Inf Inf Inf Inf Inf Inf 1. 2 Inf 1 Inf Inf 1.2 0 1.2 Inf 1.1 Inf Inf Inf 1.3 1.2 Inf Inf 1.2 0 1.5 1.4 Inf Inf Inf Inf 1.1 1.4 Inf Inf 1.5 0 Inf Inf Inf 1.4 Inf Inf Inf Inf 1 1.2 Inf 0 1 1 Inf Inf Inf Inf Inf Inf Inf Inf 1 0 Inf Inf Inf Inf Inf Inf Inf Inf Inf 1 Inf 0 1 Inf Inf 1.2 Inf Inf Inf 1.4 Inf Inf 1 0 为了检验本章在引进路径权重之后的自适应蚁群算法的性能， 该仿真算例分为利用不引入路径路径权重的蚁群算法和利用引入路径权重的蚁群算法进行仿真实验， 并将得到的结果进行比较分析。 设定算法运算等待...
