应急救援物资车辆运输路线多目标优化

第36卷第10期 北京科技大学学报 Vol.36 No.10 2014年10月 Journal of University of Science and Technology Beijing 0ct.2014 应急救援物资车辆运输路线多目标优化 盖文妹)，蒋仲安)四，邓云峰)，李竞》，杜焱》 1)北京科技大学土木与环境工程学院，北京1000832)国家行政学院，北京1000893)中国安全科学生产研究院，北京100012 ☒通信作者，E-mail:jzal963@263.net 摘要运用运筹学中图论及多目标优化的理论和方法建立应急救援物资车辆最佳运输路线的选择模型，并基于启发式算 法求解该模型.从静态网络应急物资车辆运输路线的双目标优化问题入手，设计适合本文模型的算法，并将之推广至含有三 个及三个以上优化目标的路线选择问题.引入时间扩展图的概念，将动态网络中的最佳运输路线问题转化为静态网络中的路 径选择问题.算法实质是通过构造辅助决策函数实现Djst算法的调用，并在辅助函数构成的搜索空间上寻找最优解，是一 种快速的、近似的算法.利用随机路网和真实路网测试本文算法，测试结果与本文的理论分析一致，证明本文算法在应急救援 物资车辆运输路线的多目标优化问题中可行且有较好的应用效果. 关键词应急救援：多目标优化：车辆路线：数学模型：最短路算法 分类号X913.1 Multi-objective route optimization of transporting emergency goods and materi- als for rescue GAI Wen-me.2,JIANG Zhong-n)a,DENG Yun-feng》,LI Jing》,DU Yan” 1)School of Civil and Environmental Engineering.University of Science and Technology Beijing,Beijing 100083,China 2)Chinese Academy of Government,Beijing 100089,China 3)China Academy of Safety Science and Technology,Beijing 100012,China Corresponding author,E-mail:jzal963@263.net ABSTRACT A mathematical model of the optimum route for transporting goods and materials during a disaster period was built by using the graph theory and multi-objective optimization method.For the simple case of a dual-objective optimization,an approximate and fast algorithm was proposed based on the heuristic algorithm and then we extended the promotion to other transportation route optimization problems,which contain 3 and more than 3 optimization goals.The dynamic network routing problem was transferred into a static network routing problem by introducing the time-expanded graph in dynamic network flow analysis,which can provide an appro- priate method for selecting the optimum route of transporting emergency goods and materials.The purposes of the algorithm are to call Dijstra algorithm to calculate the model by constructing several decision support functions and to find the optimal solution in the search space constituted by the auxiliary functions,so the algorithm is a fast and approximate algorithm.The algorithm was tested in a random road network and a real road network,and the results are consistent with theoretical analysis in the text.The test results show that the algorithm has a better effect in solving the multi-objective route optimization problem of transporting emergency goods and materials and its solution efficiency is higher. KEY WORDS emergency rescue:multi-objective optimization:vehicle routing;mathematical models;shortest path algorithm 在我国，自然灾害、事故灾难、公共卫生、社会安全等突发事件时有发生，如“5·12”汶川特大地震、 收稿日期：20130925 基金项目：国家自然科学基金资助项目(71173198)：国家科技支撑计划课题资助项目(2012BAK03B05,2012BAK20B02) DOI:10.13374/j.issn1001-053x.2014.10.016:http://journals.ustb.edu.cn

第 36 卷 第 10 期 2014 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 10 Oct． 2014 应急救援物资车辆运输路线多目标优化 盖文妹1，2) ，蒋仲安1) ，邓云峰2) ，李 竞3) ，杜 焱1) 1) 北京科技大学土木与环境工程学院，北京 100083 2) 国家行政学院，北京 100089 3) 中国安全科学生产研究院，北京 100012  通信作者，E-mail: jza1963@ 263． net 摘 要 运用运筹学中图论及多目标优化的理论和方法建立应急救援物资车辆最佳运输路线的选择模型，并基于启发式算 法求解该模型． 从静态网络应急物资车辆运输路线的双目标优化问题入手，设计适合本文模型的算法，并将之推广至含有三 个及三个以上优化目标的路线选择问题． 引入时间扩展图的概念，将动态网络中的最佳运输路线问题转化为静态网络中的路 径选择问题． 算法实质是通过构造辅助决策函数实现 Dijstra 算法的调用，并在辅助函数构成的搜索空间上寻找最优解，是一 种快速的、近似的算法． 利用随机路网和真实路网测试本文算法，测试结果与本文的理论分析一致，证明本文算法在应急救援 物资车辆运输路线的多目标优化问题中可行且有较好的应用效果． 关键词 应急救援; 多目标优化; 车辆路线; 数学模型; 最短路算法 分类号 X 913. 1 Multi-objective route optimization of transporting emergency goods and materi￾als for rescue GAI Wen-mei1，2) ，JIANG Zhong-an1)  ，DENG Yun-feng2) ，LI Jing3) ，DU Yan1) 1) School of Civil and Environmental Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Chinese Academy of Government，Beijing 100089，China 3) China Academy of Safety Science and Technology，Beijing 100012，China  Corresponding author，E-mail: jza1963@ 263． net ABSTＲACT A mathematical model of the optimum route for transporting goods and materials during a disaster period was built by using the graph theory and multi-objective optimization method． For the simple case of a dual-objective optimization，an approximate and fast algorithm was proposed based on the heuristic algorithm and then we extended the promotion to other transportation route optimization problems，which contain 3 and more than 3 optimization goals． The dynamic network routing problem was transferred into a static network routing problem by introducing the time-expanded graph in dynamic network flow analysis，which can provide an appro￾priate method for selecting the optimum route of transporting emergency goods and materials． The purposes of the algorithm are to call Dijstra algorithm to calculate the model by constructing several decision support functions and to find the optimal solution in the search space constituted by the auxiliary functions，so the algorithm is a fast and approximate algorithm． The algorithm was tested in a random road network and a real road network，and the results are consistent with theoretical analysis in the text． The test results show that the algorithm has a better effect in solving the multi-objective route optimization problem of transporting emergency goods and materials and its solution efficiency is higher． KEY WOＲDS emergency rescue; multi-objective optimization; vehicle routing; mathematical models; shortest path algorithm 收稿日期: 2013--09--25 基金项目: 国家自然科学基金资助项目( 71173198) ; 国家科技支撑计划课题资助项目( 2012BAK03B05，2012BAK20B02) DOI: 10． 13374 /j． issn1001--053x． 2014． 10． 016; http: / /journals． ustb． edu． cn 在我国，自然灾害、事故灾难、公共卫生、社会安 全等突发事件时有发生，如“5·12”汶川特大地震

第10期 盖文妹等：应急救援物资车辆运输路线多目标优化 ·1385· “12·23”重庆天然气井喷事故以及“415”重庆天原 由于运输行程中不同路段的道路环境、地形条件差 化工总厂氯气泄漏事故习.为积极应对上述各种 异及灾害事态严重程度不同，各路段的风险不同，为 紧急态势，国家有关部门制定了相应的紧急救援预 保证物资运送人员的安全，应尽量选择风险较小的 案，其中应急救援物资运输是救援工作的重要内容， 路段行驶：此外，合理的运输调度方案有利于减少运 而应急救援物资车辆的调度问题是确保这一工作顺 输周转量，从而降低运输费用，但是在紧急态势下， 利进行的关键回.近年来现代地理信息服务、远程 由于运量大和运输时间集中等原因，常常会发生运 监测、传感器技术等信息技术的发展为建立动态实 力紧张的状况，追求运输调度的经济性目标，能够有 时的应急救援物资车辆最佳运输路线选择系统提供 效缓解运力不足的矛盾B.10-.因此，紧急态势下 了必要的技术支持O.在GS上以图形形式直观显 的应急决策者在选择救援物资车辆运输路线时，可 示应急救援物资车辆最佳运输路线的前提是建立合 能要求从救援物资支持保障中心到受灾地点运输路 理的运输路线优化模型，并设计出适合模型的算法. 线的时效性、安全性和经济性目标等多个目标的最 目前求解避灾路线与救灾路线等灾变条件下路 优化：从受灾地点返回支持保障中心时可能只要求 线选择的单目标优化研究己有所论述，多利用最短 运输路线的安全性和经济性实现最优化即可，虽然 路模型求解，但利用最短路模型求解灾变条件下救 也是起点到终点再返回起点的一条回路，但是救援 援物资运输调度多目标优化问题的研究还为数不 物资车辆由起点到终点的路线和由终点返回起点的 多B-).Current和Marsh网对于多目标最短路问题 路线优化目标内容和数量并不统一，显然无法借助 的研究现状进行分类和概括后指出，一般地，对于多 旅行商模型求解，需要根据灾变时期路线选择的特 目标的最短路算法，通常的处理方法是对不同的目 点建立合理的模型 标进行线性加权或是将某些目标转化为约束条件， 1.2模型建立 但是对于线性加权法而言，其权重的确定是一件很 地面错综复杂的道路易于用图形的形式直观地 困难的事情：而对于有约束的最短路问题，已经被证 描述与表达，数学上把这种与图相关的结构称为网 明是NP(non-deterministic polynomial)完全问题，有 络，路段抽象为图的边，路段之间的交点抽象成图的 时因为其算法复杂性太高使得无法进行求解.本文 点的集合，组成网络图的顶点，与路段相关的优化决 运用运筹学中图论和多目标优化的理论和方法建立 策指标作为有向边的权重.紧急态势下救援物资车 了应急救援物资车辆运输路线多目标优化模型，并 辆运输路线的选择虽然需要考虑多个优化目标，但 从应急决策的角度降低计算最优解的复杂度，设计 在任何情况下，保障人员的安全都是首要的目标，相 出适合求解该模型的算法 对而言，路线的时效性、经济性等要求均可看作次要 优化目标.为便于描述，令G=(V,E)表示一张道路 应急救援物资车辆最佳运输路线数学 网络图，V={}为G的节点集，E={(:,)|(:, 模型 )≠(，），)为G的有向边集，其中1V1= 1.1问题描述 n,IE1=m;为(：U)赋予多个不同的权重，和a, 灾变条件下的救援物资运输调度与正常环境下 T为车辆在路段(，y)上安全通过的概率，0<r< 的企业运输调度，优化目标之间差异明显.对于正 1,a为车辆在路段(：，，)上行驶的时间、成本等除 常情况下的企业运输调度而言，优化目标主要从经 安全性指标以外的其他决策指标，a证≥0，其中k= 济性角度考虑，通常简化为从起点出发，通过所有给 1,2,·,X,X为次要优化目标的数量.根据前述分 定的需求点之后，最后再回到原点运输成本的最小 析的应急救援物资车辆最佳运输路线选择的特点， 化，只在少数情况下才考虑时间约束，可转化为运筹 可将救援物资车辆最佳运输路线的选择分为“往” 学中的旅行商问题(traveling salesman problem, (支持保障中心→物资需求点)和“回”（物资需求 TSP),求解旅行商问题的算法已有较为深入的研 点→支持保障中心)两个过程来求解，每个过程均 究，分为完全算法和近似算法两类回.在灾变时期， 属于一个，→路线选择的多目标优化问题，其中 为保证安全高效的救灾，救援物资车辆运输路径的 ,和)分别表示选定的起点和终点.当"，表示物资 选择往往需要同时考虑多个优化目标，比如时间、成 支持保障中心时，表示受灾地点：当，表示受灾地 本和风险.首先，时间是任何紧急态势下不可忽视 点时，表示物资支持保障中心.由于最佳运输路 的决策属性，尤其是灾变条件下，争取时间能够抢得 线的各个优化目标之间通常存在冲突，某个目标下 主动，最大限度地挽救生命和减少财产损失；其次， 的最优解对于另一个目标可能并非最优，因而需要

第 10 期 盖文妹等: 应急救援物资车辆运输路线多目标优化 “12·23”重庆天然气井喷事故以及“4·15”重庆天原 化工总厂氯气泄漏事故［1--2］． 为积极应对上述各种 紧急态势，国家有关部门制定了相应的紧急救援预 案，其中应急救援物资运输是救援工作的重要内容， 而应急救援物资车辆的调度问题是确保这一工作顺 利进行的关键［3］． 近年来现代地理信息服务、远程 监测、传感器技术等信息技术的发展为建立动态实 时的应急救援物资车辆最佳运输路线选择系统提供 了必要的技术支持［4］． 在 GIS 上以图形形式直观显 示应急救援物资车辆最佳运输路线的前提是建立合 理的运输路线优化模型，并设计出适合模型的算法． 目前求解避灾路线与救灾路线等灾变条件下路 线选择的单目标优化研究已有所论述，多利用最短 路模型求解，但利用最短路模型求解灾变条件下救 援物资运输调度多目标优化问题的研究还为数不 多［5--7］． Current 和 Marsh［8］对于多目标最短路问题 的研究现状进行分类和概括后指出，一般地，对于多 目标的最短路算法，通常的处理方法是对不同的目 标进行线性加权或是将某些目标转化为约束条件， 但是对于线性加权法而言，其权重的确定是一件很 困难的事情; 而对于有约束的最短路问题，已经被证 明是 NP( non-deterministic polynomial) 完全问题，有 时因为其算法复杂性太高使得无法进行求解． 本文 运用运筹学中图论和多目标优化的理论和方法建立 了应急救援物资车辆运输路线多目标优化模型，并 从应急决策的角度降低计算最优解的复杂度，设计 出适合求解该模型的算法． 1 应急救援物资车辆最佳运输路线数学 模型 1. 1 问题描述 灾变条件下的救援物资运输调度与正常环境下 的企业运输调度，优化目标之间差异明显． 对于正 常情况下的企业运输调度而言，优化目标主要从经 济性角度考虑，通常简化为从起点出发，通过所有给 定的需求点之后，最后再回到原点运输成本的最小 化，只在少数情况下才考虑时间约束，可转化为运筹 学中的旅行商问题 ( traveling salesman problem， TSP) ，求解旅行商问题的算法已有较为深入的研 究，分为完全算法和近似算法两类［9］． 在灾变时期， 为保证安全高效的救灾，救援物资车辆运输路径的 选择往往需要同时考虑多个优化目标，比如时间、成 本和风险． 首先，时间是任何紧急态势下不可忽视 的决策属性，尤其是灾变条件下，争取时间能够抢得 主动，最大限度地挽救生命和减少财产损失; 其次， 由于运输行程中不同路段的道路环境、地形条件差 异及灾害事态严重程度不同，各路段的风险不同，为 保证物资运送人员的安全，应尽量选择风险较小的 路段行驶; 此外，合理的运输调度方案有利于减少运 输周转量，从而降低运输费用，但是在紧急态势下， 由于运量大和运输时间集中等原因，常常会发生运 力紧张的状况，追求运输调度的经济性目标，能够有 效缓解运力不足的矛盾［3，10--12］． 因此，紧急态势下 的应急决策者在选择救援物资车辆运输路线时，可 能要求从救援物资支持保障中心到受灾地点运输路 线的时效性、安全性和经济性目标等多个目标的最 优化; 从受灾地点返回支持保障中心时可能只要求 运输路线的安全性和经济性实现最优化即可，虽然 也是起点到终点再返回起点的一条回路，但是救援 物资车辆由起点到终点的路线和由终点返回起点的 路线优化目标内容和数量并不统一，显然无法借助 旅行商模型求解，需要根据灾变时期路线选择的特 点建立合理的模型． 1. 2 模型建立 地面错综复杂的道路易于用图形的形式直观地 描述与表达，数学上把这种与图相关的结构称为网 络，路段抽象为图的边，路段之间的交点抽象成图的 点的集合，组成网络图的顶点，与路段相关的优化决 策指标作为有向边的权重． 紧急态势下救援物资车 辆运输路线的选择虽然需要考虑多个优化目标，但 在任何情况下，保障人员的安全都是首要的目标，相 对而言，路线的时效性、经济性等要求均可看作次要 优化目标． 为便于描述，令 G = ( V，E) 表示一张道路 网络图，V = { vi} 为 G 的节点集，E = { ( vi，vj) | ( vi， vj ) ≠( vj ，vi ) ，vi，vj"V} 为 G 的有向边集，其中 | V | = n，| E | = m; 为( vi，vj) 赋予多个不同的权重 rij和 aijk， rij为车辆在路段( vi，vj ) 上安全通过的概率，0 ＜ rij ＜ 1，aijk为车辆在路段( vi，vj ) 上行驶的时间、成本等除 安全性指标以外的其他决策指标，aijk≥0，其中 k = 1，2，…，X，X 为次要优化目标的数量． 根据前述分 析的应急救援物资车辆最佳运输路线选择的特点， 可将救援物资车辆最佳运输路线的选择分为“往” ( 支持保障中心→物资需求点) 和“回”( 物资需求 点→支持保障中心) 两个过程来求解，每个过程均 属于一个 v1→vn路线选择的多目标优化问题，其中 v1和 vn分别表示选定的起点和终点． 当 v1表示物资 支持保障中心时，vn表示受灾地点; 当 v1表示受灾地 点时，vn表示物资支持保障中心． 由于最佳运输路 线的各个优化目标之间通常存在冲突，某个目标下 的最优解对于另一个目标可能并非最优，因而需要 · 5831 ·

·1386· 北京科技大学学报 第36卷 对某些优化目标进行折衷.对于应急物资调度的决 对Vk=1,2,…,X,设P表示(BOOP)的最优解，可 策者而言，在无法获得理想最佳运输路线的条件下， 以证明辅助决策函数有如下性质成立. 可以对次要优化目标进行控制使其在可接受范围 性质1若P满足式(3)，则P,是图G关于构 内，而尽量使首要优化目标达到最优.因此，本文研 造权重W继的最短路. 究的应急救援物资车辆运输路线多目标优化问题 证明：若P,满足式(3)，则 (multi--objective optimization problem,MOOP)可以描 述为： e-m]= (p)ePa (1) ma_（分e--ma). (r A(P)=,∑ae≤l,k=1,2,,X (2) 所以 可ep 式中：P为，，的一条路；R(P)称为路P的安全 ∑0lrg-(1-0）24a]= 概率，属于首要优化目标函数；A(P)是路P的第k max∑0lmg-(1-）·m2ua], 个次要优化目标函数，如行驶时间和运输成本；，表 示A(P)的最大允许值.(MOOP)即求，→U,的一 ∑0(-lnrg)+(1-)724ae]= 条路P,同时满足式(1)和式(2)，并称P为模型 (rpE ePa min∑[0(-lrg）+(1-0)·72kap], 的最优解.(MOOP)实际上属于多目标最短路问 可eP 题，Dijkstra算法等传统最短路算法无法直接求解 该模型.为解决此问题，本文将在第2部分讨论适 。0联=min,∑，0g 合求解该模型的算法，并详细分析算法的时间复杂 (ep ePo (,可eP 度及优势所在. 性质2辅助函数y=fk(θ)递增时y=fk() 递减，且分别在0=0和0=1时取得最小值. 2应急救援物资车辆最佳运输路线算法 证明：任取0≤a 本文基于启发式算法思想，借助加权平均法构造 ∑.B(-lrg)+(1-B)·n24at]. (r cPB 辅助决策函数，并据此设计(BOOP)的算法 所以 (1)几何平均构造辅助决策函数.利用几何平 均方法的构造如下辅助决策函数： l多（-my多（-w]+ f(a,B)=max 几。ga+e胸la+9]. -[. me）g.{aua]≤0 (3) 式中，2x为量纲一化系数，2k=[min4（P)]-1: ®l多.（-)多，（-i时+ (可eg a,B≥0且a+B≠0，k∈{1,2，…，X}.令0=a/ (α+B),式(3)所示函数可以转化为加权系数日的 u-p[.a多wJ]≥0 函数，记作y=f(0),0∈0,1]，k∈{1,2，…，X}. 又因为 令P,表示对应于0的满足式(3)的1→v.的一条 (1-B),(1-a)∈0,1]， 路，利用P,可构造另外两个辅助决策函数： 所以 y=fik(0)=-lnR(P,）,y=f（0)=n2x44(P。）. ∑.（-lr,)≥∑(-lrg), 其中0∈D,1],k∈{1,2，…，X}.为图G的有向边 (可ePg (,)构造一个新权重 ∑(m24a)≤∑(n2a). (r EPa (i ePg 0t=0（-lnrg）+（1-)·72a, 再根据式(1)和式(2)

北 京 科 技 大 学 学 报 第 36 卷 对某些优化目标进行折衷． 对于应急物资调度的决 策者而言，在无法获得理想最佳运输路线的条件下， 可以对次要优化目标进行控制使其在可接受范围 内，而尽量使首要优化目标达到最优． 因此，本文研 究的应急救援物资车辆运输路线多目标优化问题 ( multi-objective optimization problem，MOOP) 可以描 述为: maxＲ( P) = ( v ∏i ，vj ) ∈P rij， ( 1) Ak ( P) = ( v ∑i ，vj ) ∈P aijk≤lk，k = 1，2，…，X． ( 2) 式中: P 为 v1→vn的一条路; Ｒ( P) 称为路 P 的安全 概率，属于首要优化目标函数; Ak ( P) 是路 P 的第 k 个次要优化目标函数，如行驶时间和运输成本; lk表 示 Ak ( P) 的最大允许值． ( MOOP) 即求 v1→vn的一 条路 P* ，同时满足式( 1) 和式( 2) ，并称 P* 为模型 的最优解． ( MOOP) 实际上属于多目标最短路问 题，Dijkstra 算法等传统最短路算法［6］无法直接求解 该模型． 为解决此问题，本文将在第 2 部分讨论适 合求解该模型的算法，并详细分析算法的时间复杂 度及优势所在． 2 应急救援物资车辆最佳运输路线算法 研究 2. 1 含两个优化目标的最佳运输路线算法 应急救援物资车辆运输路线双目标优化问题 ( bi-objective optimization problem， BOOP ) 是 ( MOOP) 中的一个常见情况，Handler 和 Zang［13］证 明了该问题是 NP-完全的． 为降低计算的复杂度， 本文基于启发式算法思想［14］，借助加权平均法构造 辅助决策函数，并据此设计( BOOP) 的算法． ( 1) 几何平均构造辅助决策函数． 利用几何平 均方法［15］构造如下辅助决策函数: f( α，β) = max ( v ∏i ，vj ) ∈P ［r α/( α + β) ij ·e － βη2kaijk /( α + β) ］． ( 3) 式中，η2k 为量纲一化系数，η2k = ［minAk ( P) ］－ 1 ; α，β≥0 且 α + β≠0 ，k∈{ 1，2，…，X} ． 令 θ = α/ ( α + β) ，式( 3) 所示函数可以转化为加权系数 θ 的 函数，记作 y = fk ( θ) ，θ∈［0，1］，k∈{ 1，2，…，X} ． 令 Pθ表示对应于 θ 的满足式( 3) 的 v1 →vn 的一条 路，利用 Pθ可构造另外两个辅助决策函数: y = f1k ( θ) = － lnＲ( Pθ ) ，y = f2k ( θ) = η2kAk ( Pθ ) ． 其中 θ∈［0，1］，k∈{ 1，2，…，X} ． 为图 G 的有向边 ( vi，vj ) 构造一个新权重 wijk = θ·( － lnrij) + ( 1 － θ)·η2kaijk， 对k = 1，2，…，X，设 P* k 表示( BOOP) 的最优解，可 以证明辅助决策函数有如下性质成立． 性质 1 若 Pθ满足式( 3) ，则 Pθ是图 G 关于构 造权重 wijk的最短路． 证明: 若 Pθ满足式( 3) ，则 ( v ∏i ，vj ) ∈Pθ ［r θ ij·e － ( 1 － θ) η2kaijk］= max ( v ∏i ，vj ) ∈P ( r θ ij·e － ( 1 － θ) η2kaijk ) ． 所以 ( v ∑i ，vj ) ∈Pθ ［θ·lnrij － ( 1 － θ)·η2kaijk］= max ( v ∑i ，vj ) ∈P ［θ·lnrij － ( 1 － θ)·η2kaijk］， ( v ∑i ，vj ) ∈Pθ ［θ·( － lnrij) + ( 1 － θ)·η2kaijk］= min ( v ∑i ，vj ) ∈P ［θ·( － lnrij) + ( 1 － θ)·η2kaijk］， 即 ( v ∑i ，vj ) ∈Pθ wijk = min ( v ∑i ，vj ) ∈P wijk ． 性质 2 辅助函数 y = f2k ( θ) 递增时 y = f1k ( θ) 递减，且分别在 θ = 0 和 θ = 1 时取得最小值． 证明: 任取0≤α ＜ β≤1，设 Pα和 Pβ分别为 θ = α 和 θ = β 时满足公式( 3) 的一条路，根据性质 1 可知 ( v ∑i ，vj ) ∈Pα ［α·( － lnrij) + ( 1 － α)·η2kaijk］≤ ( v ∑i ，vj ) ∈Pβ ［α·( － lnrij) + ( 1 － α)·η2kaijk］， ( v ∑i ，vj ) ∈Pα ［β·( － lnrij) + ( 1 － β)·η2kaijk］≥ ( v ∑i ，vj ) ∈Pβ ［β·( － lnrij) + ( 1 － β)·η2kaijk］． 所以 α [ ( v ∑i ，vj ) ∈Pα ( － lnrij) － ( v ∑i ，vj ) ∈Pβ ( － lnrij ] ) + ( 1 － α [ ) ( v ∑i ，vj ) ∈Pα ( η2kaijk ) － ( v ∑i ，vj ) ∈Pβ ( η2kaijk ] ) ≤ 0; β [ ( v ∑i ，vj ) ∈Pα ( － lnrij) － ( v ∑i ，vj ) ∈Pβ ( － lnrij ] ) + ( 1 － β [ ) ( v ∑i ，vj ) ∈Pa ( η2kaijk ) － ( v ∑i ，vj ) ∈Pβ ( η2kaijk ] ) ≥0． 又因为 ( 1 － β) ，( 1 － α) ∈［0，1］， 所以 ( v ∑i ，vj ) ∈Pα ( － lnrij) ≥ ( v ∑i ，vj ) ∈Pβ ( － lnrij) ， ( v ∑i ，vj ) ∈Pα ( η2kaijk ) ≤ ( v ∑i ，vj ) ∈Pβ ( η2kaijk ) ． 再根据式( 1) 和式( 2) ， · 6831 ·

第10期 盖文妹等：应急救援物资车辆运输路线多目标优化 ·1387· ∑(-lnr)=-lnR(P), R(P)>R(P)且A(P)n24,则R(P)≥ 为P和P,则 R(P)EA2(P)>h,YE(u+K (v-u)/N,v]; f(0）=e-24=max e2uW, ②若f(u+K,(v-u)/N)l至少有一个成立，Hg∈[u,u+K(v- )/N)(u+K2(w-u)/W,v]; -lnΠrg=mim(-lnΠ_r). ④如果f(u+K(v-u)/N)=2l4,则P= (r)ePI (iE)cP 结合式(1)和(2)可知 P.:如果fx(u+K,(u-u）/N)=n2l4,则P=Pg f5s(0）=2sA(Pa）=min(n2k4k(P））= 结论2设置的限制条件不同，P的结果不同： min(n2xA:(P,））=minfzx(0), 若ln24l,P无解； 的采样值即为(BOOP)的最优解. 若f(0）=刀2lk,则P=P。:若f（1)≤72xlk,则 (2)算法可行性及流程分析.根据辅助决策函 P=P:若f4(0)n2,则A4(P）>l恒成立，因此对k=1, 中K1RP,或者至少有一段区间去掉后不会丢失P·因 (P且A4(P)<l4,所以P=P。·若0=1时P满 此，通过反复迭代搜索当前区间u,v],或者恰好在 足式(3)，根据性质2可知f(1)=-lnR(P)=0=0处获得P,或者最终得到一个较小的0的近 min[-lnR(P)],所以R(P,)=maxR（P),若 似区间u,v],并在0=u处获得P的一个近似解， f(1)≤n24l4,则A(P)≤l4,因此对Vk=1,2,…, 记作P.综上，通过N分当前区间并选择两个试 X,P能同时满足式(1)和式(2)，因此P=P.若 探点搜索最优解的算法具备可行性，求解(BOOP) (O)<24<fx(1),根据性质2可知，若存在满 的算法流程见图1.1996年Zhan和Noon使用实际 足式(3)的一条路P,恰能满足fx（0)=2k4k(P,)= 交通网络测试了15种传统最短路算法.测试结果 2,则易知此时不可能有另一条路径P同时满足 表明，计算一点到所有其他点的最短路径最快的算

第 10 期 盖文妹等: 应急救援物资车辆运输路线多目标优化 ( v ∑i ，vj ) ∈P ( － lnrij) = － lnＲ( P) ， ( v ∑i ，vj ) ∈P ( η2kaijk ) = η2k Ak ( P) ， 有 － lnＲ( Pα ) ≥ － lnＲ( Pβ ) ， η2k Ak ( Pα ) ≤η2k Ak ( Pβ ) ， 得 f2k ( α) ≤f2k ( β) ，f1k ( α) ≥f1k ( β) ． 所以 f2k ( θ) 和 f1k ( θ) 分别为［0，1］上的增函数和减 函数． 假设 θ = 0 和 θ = 1 时满足式( 3) 的路径分别 为 P0和 P1，则 fk ( 0) = ( v ∏i ，vj ) ∈P0 e － η2kaijk = max ( v ∏i ，vj ) ∈P e － η2kaijk， fk ( 1) = ( v ∏i ，vj ) ∈P1 rij = max ( v ∏i ，vj ) ∈P rij． 所以 η2k ( v ∑i ，vj ) ∈P0 aijk = min ( η2k ( v ∑i ，vj ) ∈P aijk ) ， － ln ( v ∏i ，vj ) ∈P1 rij = min( － ln ( v ∏i ，vj ) ∈P rij) ． 结合式( 1) 和( 2) 可知 f2k ( 0) = η2kAk ( P0 ) = min( η2kAk ( P) ) = min( η2kAk ( Pθ ) ) = minf2k ( θ) ， f1k ( 1) = － lnＲ( P1 ) = min( － lnＲ( P) ) = min( － lnＲ( Pθ ) ) = minf1k ( θ) ． 命题得证． 性质 3 设 θ = 0 和 θ = 1 时满足公式( 3) 的路 径分别为 P0和 P1，那么: 若 f2k ( 0) ＞ η2k lk，P* k 无解; 若 f2k ( 0) = η2k lk，则 P* k = P0 ; 若 f2k ( 1) ≤η2k lk，则 P* k = P1 ; 若 f2k ( 0) ＜ η2k lk ＜ f2k ( 1) ，并且存在满足 式( 3) 的一条路 Pθ恰能使 f2k ( θ) = η2k lk，则 P* k = Pθ ． 证明: 若 θ = 0 时 P0满足式( 3) ，根据性质 2 可 知 f2k ( 0 ) = η2k Ak ( P0 ) = min ( η2k Ak ( P) ) ． 若 f2k ( 0) ＞ η2k lk，则 Ak ( P) ＞ lk恒成立，因此对k = 1， 2，…，X，不存 v1→vn的一条路能同时满足式( 1) 和 式( 2) ，所以 P* k 无解; 若 f2k ( 0) = η2k lk，根据性质 2 易知不可能有另一条路径 P 同时满足 Ｒ( P) ＞ Ｒ ( P0 ) 且 Ak ( P) ＜ lk，所以 P* k = P0 ． 若 θ = 1 时 P1满 足式( 3) ，根据性质 2 可知 f1k ( 1) = － lnＲ( P1 ) = min［－ lnＲ( P) ］，所 以 Ｒ ( P1 ) = maxＲ ( P ) ，若 f2k ( 1) ≤η2k lk，则 Ak ( P1 ) ≤lk，因此对k = 1，2，…， X，P1能同时满足式( 1) 和式( 2) ，因此 P* k = P1 ． 若 f2k ( 0) ＜ η2k lk ＜ f2k ( 1) ，根据性质 2 可知，若存在满 足式( 3) 的一条路 Pθ恰能满足 f2k ( θ) = η2kAk ( Pθ ) = η2k lk，则易知此时不可能有另一条路径 P 同时满足 Ｒ( P) ＞ Ｒ( Pθ ) 且 Ak ( P) ＜ lk，那么对于k = 1，2， …，X，根据式( 1) 和式( 2) 可知 Pθ = P* k ． 对于( u，v) ( 0，1) ，若将区间( u，v) 均分为 N 份，N 为正整数，对于 K1 ＜ K2∈{ 1，2，…，N － 1} ， 基于辅助决策函数的上述性质，容易证明有如下结 论成立． 结论 1 假设对应于 θ = u + K1 ( v － u) /N、θ = u + K2 ( v － u) /N及 θ = ζ 的满足式( 3) 的路径存在且 分别为 Pα、Pβ和 Pζ，那么: ① 若 f2k ( u + K1 ( v － u) /N) ＞ η2k lk，则 Ｒ( Pζ ) ≥ Ｒ( Pα ) 且 A2k ( Pζ ) ＞ lk，ζ∈( u + K1 ( v － u) /N，v］; ② 若 f2k ( u + K2 ( v － u) /N) ＜ η2k lk，则 Ｒ( Pζ ) ≤ Ｒ( Pβ ) 且 A2k ( Pζ ) ＜ lk，ζ∈( u，u + K2 ( v － u) /N］; ③ 若( f2k ( u + K1 ( v － u) /N) － η2k lk ) ( f2k ( u + K2 ( v － u) /N) － η2k lk ) ＜ 0，则 Ｒ( Pζ ) ≤Ｒ( Pβ ) 与 A2k ( Pζ ) ＞ lk至少有一个成立，ζ∈［u，u + K1 ( v － u) /N ) #( u + K2 ( v － u) /N，v］; ④ 如果 f2k ( u + K1 ( v － u) /N) = η2k lk，则 P* k = Pα ; 如果 f2k ( u + K2 ( v － u) /N) = η2k lk，则 P* k = Pβ ． 结论 2 设置的限制条件不同，P* k 的结果不同: 若 lk ＜ η － 1 2k ·f2k ( 0) ，P* k 无解; 若 lk = η － 1 2k ·f2k ( 0) ，则 P* k = P0 ; 若 lk ≥η － 1 2k ·f2k ( 1) ，则 P* k = P1 ; 若 η － 1 2k · f2k ( 0) ＜ lk ＜ η － 1 2k ·f2k ( 1) ，则可以通过 N 分区间［0， 1］的方法获得满足 A2k ( P) ＜ lk 的一系列 v1 →vn的 路，这些路径即为最优解的采样值，其中满足式( 1) 的采样值即为( BOOP) 的最优解． ( 2) 算法可行性及流程分析． 根据辅助决策函 数性质 1，满足式( 3) 的路径 Pθ可利用 Floyd 算法、 Dijstra 算法及 A-star 算法等传统最短路算法直接求 解． 根据结论 1 可知，若将区间［u，v］细分成 N 份， 只要任 取 两 个 点 θ = u + K1 ( v － u) /N 和 θ = u + K2 ( v － u) /N 作为试探点计算满足式( 3) 的路径，其 中 K1 ＜ K2∈{ 1，2，…，N － 1} ，对于k = 1，2，…，X， 通过比较函数值 f2k ( u + K1 ( v － u) /N) 或f2k ( u + K1 ( v － u) /N) 与 η2k lk 之间的关系，或 者 可 以 求 得 P* k ，或者至少有一段区间去掉后不会丢失 P* k ． 因 此，通过反复迭代搜索当前区间［u，v］，或者恰好在 θ = θ * 处获得 P* k ，或者最终得到一个较小的 θ * 的近 似区间［u，v］，并在 θ = u 处获得 P* k 的一个近似解， 记作 Papp k ． 综上，通过 N 分当前区间并选择两个试 探点搜索最优解的算法具备可行性，求解( BOOP) 的算法流程见图 1． 1996 年 Zhan 和 Noon 使用实际 交通网络测试了 15 种传统最短路算法． 测试结果 表明，计算一点到所有其他点的最短路径最快的算 · 7831 ·

·1388· 北京科技大学学报 第36卷 1>0.Y4-30 K1.K-2 00.调用Dijkstra算法 求满足式3)的路径P。 了0>n,？>(D.P无解 计算，0，j41 立否 否 61,2 D.jP P。 计算0.产+1 不否 u 0.PP 是 0K12 是 ∫(0>1？ 8.PP。 香 temp'.Pm-f。 2 0u+K (-U/N 上否 调用Dijkstra算法求满足 式(3的路径P DP。 计算j月+1 图1应急救援物资车辆运输路线双目标优化搜索算法 Fig.1 Search-ype algorithm of the bi-objective optimum route 法是Dijkstra算法，因此图1所示算法在设计时 2-2+P 采用Dijkstra算法作为底层算法求解满足式(3)的 停：输出n、是 24i+1 ↑否 路径. 否 Y>2.1>0kE 0.+-0.k+-1 p*+p 是 R(P>P 以应急救援物资车辆运输路线的双目标优化搜 2-P) 索算法作为基础，含三个及以上优化目标的最佳运 i0.P +1 D与j.S-PnP,n 输路线问题的求解变得容易.若X≥3，可将 eN调用Dijkstra 否 …nP∩…nP 是 K+-SL.IP]+-S 算法求满足式(3)的 K-X (MOOP)问题分解为X个(BOOP)问题，根据结论 i∈1.2.…，.-2 路径Pj+1 P+PQ+ 2,对于任意一个(B0OP)问题，可通过N分区间D, 1]的方法获得一系列P的采样值，将采样值的集 ≤n i+1 合记作P4,其中k∈{1,2，，X}.令集合S=P1∩ Y是 个否 P-P+IPl 是 i=N P2∩…∩P∩…∩Px,那么集合S中满足式(1)的 路径即为(MOOP)的最优解P,若这样的P不止 图2应急救援物资车辆运输路线多目标优化搜索算法(X≥2) Fig.2 一个，则称P的集合为(MOOP)的最优解集，记作 Search-type algorithm of the multi-objective optimum route (X≥2) 2,算法流程见图2. 2.3应急救援物资车辆最佳运输路线的动态求解 援物资车辆动态最佳运输路线问题的求解.其基本 以上算法适用于静态网络中应急救援物资车辆 思想是：对于每一个较小的时间间隔△，路段的权 运输路线的求解，但在时变网络中，有向边的权重参 重参数可看作常数，假设初始时刻t=0,每一个可能 数可能随时间变化，此时应急救援物资车辆的最佳 的时刻t=i"△1(i=0,1,…,T-1)都对应一张由应 运输路线求解属于动态网络优化问题6.国内外 急物资车辆的当前位置到终点的网络图G(V(t), 学者对动态网络优化问题做了大量研究，其中Fod E(t)),其中V(t)和E(t)分别表示t时刻对应的网 和Fulkerson在离散时间动态网络流的分析中提出 络图的节点集和有向边集，，(t)和vn(t)表示 时间扩展图的概念切，本文将这一概念用于应急救 G(V(),E(t))的起点和终点，并将t=i△t时刻应

北 京 科 技 大 学 学 报 第 36 卷 图 1 应急救援物资车辆运输路线双目标优化搜索算法 Fig． 1 Search-type algorithm of the bi-objective optimum route 法是 Dijkstra 算法［6］，因此图 1 所示算法在设计时 采用 Dijkstra 算法作为底层算法求解满足式( 3) 的 路径． 2. 2 含三个及以上优化目标的最佳运输路线算法 以应急救援物资车辆运输路线的双目标优化搜 索算法作为基础，含三个及以上优化目标的最佳运 输路线 问 题 的 求 解 变 得 容 易． 若 X ≥ 3，可 将 ( MOOP) 问题分解为 X 个( BOOP) 问题，根据结论 2，对于任意一个( BOOP) 问题，可通过 N 分区间［0， 1］的方法获得一系列 P* k 的采样值，将采样值的集 合记作 Pk，其中 k∈{ 1，2，…，X} ． 令集合 S = P1∩ P2∩…∩Pk∩…∩PX，那么集合 S 中满足式( 1) 的 路径即为( MOOP) 的最优解 P* ，若这样的 P* 不止 一个，则称 P* 的集合为( MOOP) 的最优解集，记作 Ω，算法流程见图 2． 2. 3 应急救援物资车辆最佳运输路线的动态求解 以上算法适用于静态网络中应急救援物资车辆 运输路线的求解，但在时变网络中，有向边的权重参 数可能随时间变化，此时应急救援物资车辆的最佳 运输路线求解属于动态网络优化问题［16］． 国内外 学者对动态网络优化问题做了大量研究，其中 Ford 和 Fulkerson 在离散时间动态网络流的分析中提出 时间扩展图的概念［17］，本文将这一概念用于应急救 图 2 应急救援物资车辆运输路线多目标优化搜索算法( X≥2) Fig． 2 Search-type algorithm of the multi-objective optimum route ( X≥2) 援物资车辆动态最佳运输路线问题的求解． 其基本 思想是: 对于每一个较小的时间间隔 Δt，路段的权 重参数可看作常数，假设初始时刻 t = 0，每一个可能 的时刻 t = i·Δt( i = 0，1，…，T － 1) 都对应一张由应 急物资车辆的当前位置到终点 vn的网络图 G( V( t) ， E( t) ) ，其中 V( t) 和 E( t) 分别表示 t 时刻对应的网 络图的节点集和有向边集，v1 ( t) 和 vn ( t) 表示 G( V( t) ，E( t) ) 的起点和终点，并将 t = iΔt 时刻应 · 8831 ·

第10期 盖文妹等：应急救援物资车辆运输路线多目标优化 ·1389· 急救援物资车辆所在位置定义为一个新的节点，用 函数，并在辅助函数构成的搜索区间上寻找最优解， emp（t)表示，则1（0）=1,1（t)=emp（t), 再将之推广到含有三个及三个以上优化目标的最佳 n()=v,T为救援物资车辆从，→，的行驶时间 运输路线求解问题，由于算法具有启发式而不是在 与△1的比值.这样通过对车辆运送应急救灾物资 各个方向上平均搜索，算法探索的区域相对求解理 过程的离散化处理，使动态网络运输路线优化问题 想最优解的算法小，所以有较高的求解效率.(2)引 转化为静态的运输路线优化问题，动态网络中 入动态网络流分析中的时间扩展图的概念并将之应 (MOOP)的最优解为 用于应急救援物资车辆动态最佳运输路线问题的求 P=P。+P1+…+P:+…+Px-1 (4) 解，将该问题转化为静态网络中的路线优化问题，满 式中，P,为图G(V(i“△t),E(i"△t))中u,(i“△t)→ 足了动态网络中应急救援物资车辆运输路线选择的 m（(i+1)·△)的一条路，且P:d,Pa为 多目标优化需求.(3)根据本文所构造辅助函数的 G(V(t),E(t))中应急救灾物资车辆从，(t)→+un 性质2及结论2可知，令0取值为1/N到1，每次增 (t)的最佳路线，可直接利用本文图1或图2所示算 加1/W,当N为足够大的正整数时，可绘制出辅助决 法计算. 策函数与参数日的关系曲线，这样根据本文所建应 2.4算法终止条件、时间复杂度及优势分析 急物资车辆运输路线多目标优化模型及算法，决策 对于一个极小的区间(a,B)C0,1],如图1所 者不仅可以解决问题，还可以根据辅助决策函数曲 示算法中的区间山，v],假设0=Q和0=B时有满 线提出问题：当己知次要优化目标的限定条件，决策 足式(3)的路径P.和P。,可能对于H0∈(a,B)己经 者可以利用第2.1~2.3节所示算法求得符合限制 不存在路径P,符合式(3)，同时满足P。≠P。且P。≠ 条件的应急救援物资车辆运输的最佳往返方案，即 P。,如果算法在这样的区间中不断搜索，无疑影响求 应急救援物资车辆运输路线优化问题的解决；若己 解效率而成为算法的瓶颈。为解决这一问题，可为 知需要优化的目标函数，但限制条件未知，决策者可 图1所示算法循环部分增加一个终止条件-u0：同理，合理设置N的 形成不同的应急救援物资车辆运输路线优化问题， 值有利于提高图2所示算法的求解效率，因为若N 即问题的提出. 过大，可能多个相邻的点0=i/N(i=0,1,…,N)处 本文将在第3部分对所提算法进行模拟测试， P的采样值相同，即算法的搜索范围增大，使求解 以验证基于几何加权方法所构造辅助决策函数的性 速度变慢；而如果N过小，则可能会丢失部分P的 质及本文算法的优势 采样值而使所得结果与理想的最优解之间的误差 3 模拟测试 增大. 对于非负带权图而言，Dijkstra单源最短路径算 本次模拟选择随机路网和真实路网作为测试网 法(single-source shortest paths,SSSP)的时间复杂度 络，旨在测试辅助函数的单调性、算法的求解效率及 为O(m+nlgn),而多源的最短路径算法(all-pair 应用效果.系统的用户层用.net架构的c#语言来 shortest paths,APSP)的时间复杂度为O(mm+ 发，底层用Python的NetworkX库，直接调用封装好 n2lgn)阁.相应地，本文算法通过调用Dijkstra算法 的Dijkskra算法，获取数据的方法可以从xls或mif 寻找多目标最优路径，求解静态单源最优运输路线 文件导入或者动态从数据库中读取.假设有一批救 的时间复杂度为O(D·(m+lgn)),而静态多源最 援物资需要从支持保障中心运往某个物资需求点， 优运输路线的时间复杂度为0O(D·(mn+n2lgn); 将路线的安全概率作为首要优化目标.除此之外， 求解动态单源最优运输路线的时间复杂度为O(T· 还有路线的时效性或经济性指标等k(k=1,2,·, D·(m+nlgn)）,而动态多源最优运输路线的时间复 X)个次要优化目标 杂度为O(TD·(mn+nlgn)).其中D为图1或图 (1)随机路网实验.模拟中路段权重参数随机 2所示算法结束时计数器j的值. 假定设置，在实际情况中这些参数与路段固有属性、 本文所提算法在应急决策中有诸多优势.(1) 路况信息、灾变情况等有关，可根据实地试验或实时 本文将灾变条件下的应急救援物资车辆调度优化问 监测数据获得.随机路网的搭建方法是调用Python 题分为“往”和“回”两个过程来求解，并建立合理的 的NetworkX包，采用grid_2d-graph（Y,Z, 车辆运输路线多目标优化数学模型，从运输路线的 periodic=False,create_.using=None)方法生成一个 双目标优化问题入手，借助几何平均方法构造辅助 节点规模n=Y×Z的随机路网，其中Y表示行数，Z

第 10 期 盖文妹等: 应急救援物资车辆运输路线多目标优化 急救援物资车辆所在位置定义为一个新的节点，用 vtemp ( t) 表 示，则 v1 ( 0 ) = v1，v1 ( t) = vtemp ( t) ， vn ( t) = vn，T 为救援物资车辆从 v1 →vn的行驶时间 与 Δt 的比值． 这样通过对车辆运送应急救灾物资 过程的离散化处理，使动态网络运输路线优化问题 转化为静态的运输路线优化问题，动 态 网 络 中 ( MOOP) 的最优解为 P* = P0 + P1 + … + Pi + … + PT － 1 ． ( 4) 式中，Pi为图 G( V( i·Δt) ，E( i·Δt) ) 中 v1 ( i·Δt) $ vtemp ( ( i + 1) ·Δt) 的一条路，且 Pi %P* t = iΔt，P* t = i·Δt 为 G( V( t) ，E( t) ) 中应急救灾物资车辆从 v1 ( t) →vn ( t) 的最佳路线，可直接利用本文图 1 或图 2 所示算 法计算． 2. 4 算法终止条件、时间复杂度及优势分析 对于一个极小的区间( α，β) ［0，1］，如图 1 所 示算法中的区间［u，v］，假设 θ = α 和 θ = β 时有满 足式( 3) 的路径 Pα和 Pβ，可能对于θ∈( α，β) 已经 不存在路径 Pθ符合式( 3) ，同时满足 Pθ≠Pα且 Pθ≠ Pβ，如果算法在这样的区间中不断搜索，无疑影响求 解效率而成为算法的瓶颈． 为解决这一问题，可为 图 1 所示算法循环部分增加一个终止条件 v － u ＜ δ， 如图 1 中虚线所示，其中 δ ＞ 0; 同理，合理设置 N 的 值有利于提高图 2 所示算法的求解效率，因为若 N 过大，可能多个相邻的点 θ = i /N( i = 0，1，…，N) 处 P* k 的采样值相同，即算法的搜索范围增大，使求解 速度变慢; 而如果 N 过小，则可能会丢失部分 P* k 的 采样值而使所得结果与理想的最优解之间的误差 增大． 对于非负带权图而言，Dijkstra 单源最短路径算 法( single-source shortest paths，SSSP) 的时间复杂度 为 O( m + nlgn) ，而多源的最短路径算法( all-pair shortest paths，APSP ) 的时间复杂度为 O( mn + n2 lgn) ［18］． 相应地，本文算法通过调用 Dijkstra 算法 寻找多目标最优路径，求解静态单源最优运输路线 的时间复杂度为 O( D·( m + nlgn) ) ，而静态多源最 优运输路线的时间复杂度为 O( D·( mn + n2 lgn) ) ; 求解动态单源最优运输路线的时间复杂度为 O( T· D·( m + nlgn) ) ，而动态多源最优运输路线的时间复 杂度为 O( T·D·( mn + n2 lgn) ) ． 其中 D 为图 1 或图 2 所示算法结束时计数器 j 的值． 本文所提算法在应急决策中有诸多优势． ( 1) 本文将灾变条件下的应急救援物资车辆调度优化问 题分为“往”和“回”两个过程来求解，并建立合理的 车辆运输路线多目标优化数学模型，从运输路线的 双目标优化问题入手，借助几何平均方法构造辅助 函数，并在辅助函数构成的搜索区间上寻找最优解， 再将之推广到含有三个及三个以上优化目标的最佳 运输路线求解问题，由于算法具有启发式而不是在 各个方向上平均搜索，算法探索的区域相对求解理 想最优解的算法小，所以有较高的求解效率． ( 2) 引 入动态网络流分析中的时间扩展图的概念并将之应 用于应急救援物资车辆动态最佳运输路线问题的求 解，将该问题转化为静态网络中的路线优化问题，满 足了动态网络中应急救援物资车辆运输路线选择的 多目标优化需求． ( 3) 根据本文所构造辅助函数的 性质 2 及结论 2 可知，令 θ 取值为 1 /N 到 1，每次增 加 1 /N，当 N 为足够大的正整数时，可绘制出辅助决 策函数与参数 θ 的关系曲线，这样根据本文所建应 急物资车辆运输路线多目标优化模型及算法，决策 者不仅可以解决问题，还可以根据辅助决策函数曲 线提出问题: 当已知次要优化目标的限定条件，决策 者可以利用第 2. 1 ～ 2. 3 节所示算法求得符合限制 条件的应急救援物资车辆运输的最佳往返方案，即 应急救援物资车辆运输路线优化问题的解决; 若已 知需要优化的目标函数，但限制条件未知，决策者可 根据辅助决策函数曲线设置合理的限制条件，从而 形成不同的应急救援物资车辆运输路线优化问题， 即问题的提出． 本文将在第 3 部分对所提算法进行模拟测试， 以验证基于几何加权方法所构造辅助决策函数的性 质及本文算法的优势． 3 模拟测试 本次模拟选择随机路网和真实路网作为测试网 络，旨在测试辅助函数的单调性、算法的求解效率及 应用效果． 系统的用户层用． net 架构的 c #语言来 发，底层用 Python 的 NetworkX 库，直接调用封装好 的 Dijkskra 算法，获取数据的方法可以从 xls 或 mif 文件导入或者动态从数据库中读取． 假设有一批救 援物资需要从支持保障中心运往某个物资需求点， 将路线的安全概率作为首要优化目标． 除此之外， 还有路线的时效性或经济性指标等 k( k = 1，2，…， X) 个次要优化目标． ( 1) 随机路网实验． 模拟中路段权重参数随机 假定设置，在实际情况中这些参数与路段固有属性、 路况信息、灾变情况等有关，可根据实地试验或实时 监测数据获得． 随机路网的搭建方法是调用 Python 的 NetworkX 包，采 用 grid _ 2d _ graph ( Y， Z， periodic = False，create_using = None) 方法生成一个 节点规模 n = Y × Z 的随机路网，其中 Y 表示行数，Z · 9831 ·

·1390 北京科技大学学报 第36卷 表示列数，令1=(0,0)，tn=(Y-1,Z-1),图3表 1.8 ·…y=f《( 示(0,0)→(Y-1,Z-1)的一张有向随机路网图. 1.6 首先测试辅助函数的单调性.假设求(0,0)→(Y- 14 1,L 可行域 1,Z-1)的一条应急救援物资车辆最佳行进路线 1.2 ( 7*1 可行域 P,路P的首要优化目标为安全概率最大化，路P的 运输成本、行驶时间等作为第k(k=1,2,…,X)个次 0.8 要优化目标.将自变量0的区间D,1]平均分成N 0.6 份，在随机网络上反复测试发现，当N较大时均能 0.4 获得类似图4的辅助决策函数曲线.从图4可以看 0% 0.2 0.4 0.6 0.8 1.0 出，f(0)和f2()随系数0递减，f(0)和f2(0) 加权系数.0 随系数0递增，与本文辅助函数性质2描述一致 图4基于ython平台的辅助决策函数曲线(X=2,N=100) 其次，在未知次要优化目标限制条件值的情况下， Fig.4 Auxiliary function curves based on Python platform (Y=2, 若想提出新的路线优化问题，只要选定一个值满 N=100) 足2l落入图4所示可行域即可；若己知4的值，只 次数并不随！直线上升.根据本文第2.4节对算法 要根据图4所示曲线判断7244是否落入可行域，若 时间复杂度的分析可知，算法求解效率与Dijstra算 在可行域内可根据图1和图2所示算法求解该问 法调用次数成反比，因此基于图5(a)的分析说明图 题，否则该问题无解，与本文第2.4节关于算法优势 1所示算法结构削弱了参数1的变化对模型求解速 的理论分析一致.此外，从图4中曲线可以看出，若 度的影响，从而验证了第2.4节关于算法终止条件 L己知，由于N设置的比较大(N=100),所以存在 的理论.从图5(b)可以看出，当节点规模n增加 多个相邻的点处P的采样值相同的情况，这在求解 时，算法求解效率有变慢的趋势.这是因为随着节 (MOOP)时会使算法搜索范围较大而影响求解效 点数的增加，起点到终点的路段组合方式增加，最优 率，因此在求解模型时需要合理设置V的值，与本 解的搜索范围随之增大.但反复测试发现，当X=2 文第2.4节关于算法终止条件的理论分析一致：而 时，在10000节点以内的随机路网图上利用本文算 当4未知需要根据图4所示曲线提出问题时，可适 法计算最优路线，调用Dijstra算法10次以内即可获 当增大N的值，以保证有足够多f:(a)和fx（0)的 得最优解，证明本文算法对于含有两个优化目标的 观测值用于确定不同的应急救援物资车辆运输路线 应急救援物资车辆路线选择问题有较高的求解效 优化问题 率.从图5(c)可以看出，优化目标数量越多，算法 (4.0) 3.0 (2.0 的求解速度越慢.但应急物资运输车辆路线决策中 1.0 (4,1 0.0 的优化目标一般不会超过五个，对于400节点的随 3.1) ● 机路网而言，当X≤5时利用本文算法一般调用 4.2) 2.1 /.D 0.1) Dijstra算法30次以内即可获得模型的最优解，说明 /3.2 43 2.2 在节点规模较小的地图上寻找运输路线多目标优化 12 0.2 /33 的最优解时，本文算法求解效率较高。若在较大的 /2.3) (3.4) 1.3) 0.3) 地图上寻找最佳运输路线，且含有三个以上优化目 (249 (1,4) 0.4 标时，保证本文模型求解效率的一个可行的办法是， 图35×5随机路网 针对不同场合设计多个最优路径算法，当距离终点 Fig.3 5 x5 type random road network 较远时用大网格粗略寻找最优前进方向，而当接近 其次，测试算法的求解效率.令参数l=(4- 终点的时候切换到小网格精细寻找最优前进方向. f(0))/(fx(1)-f4(0))(0≤l≤1)，当X=1时， 当X=1时假设决策者以经济性指标作为次要优化 若设置一个较大的V值并根据式(2)检验每一个点 目标，假定车辆从心，→时可承受的运输成本最大 的f()值来搜索最优解，会导致计算最优解的速 值为1100元，测试图1所示算法的求解效率与δ的 度随！的增加而减慢：而图1所示算法在设计时令 关系.分析表1中数据可知，当0.001<8≤0.1时， N=3,并以两个三等分点作为试探点反复缩减搜索 随着δ的减小，所求近似最优路径P聊的安全概率 区间寻找最优解，结合图5(a)可知Dijstra算法调用 增加，说明6过大可能使近似最优解P与理想最

北 京 科 技 大 学 学 报 第 36 卷 表示列数，令 v1 = ( 0，0) ，vn = ( Y － 1，Z － 1) ，图 3 表 示( 0，0) →( Y － 1，Z － 1) 的一张有向随机路网图． 首先测试辅助函数的单调性． 假设求( 0，0) →( Y － 1，Z － 1) 的一条应急救援物资车辆最佳行进路线 P，路 P 的首要优化目标为安全概率最大化，路 P 的 运输成本、行驶时间等作为第 k( k = 1，2，…，X) 个次 要优化目标． 将自变量 θ 的区间［0，1］平均分成 N 份，在随机网络上反复测试发现，当 N 较大时均能 获得类似图 4 的辅助决策函数曲线． 从图 4 可以看 出，f11 ( θ) 和 f12 ( θ) 随系数 θ 递减，f21 ( θ) 和 f22 ( θ) 随系数 θ 递增，与本文辅助函数性质 2 描述一致． 其次，在未知次要优化目标限制条件值 lk的情况下， 若想提出新的路线优化问题，只要选定一个 lk值满 足 η2k lk落入图 4 所示可行域即可; 若已知 lk的值，只 要根据图 4 所示曲线判断 η2k lk是否落入可行域，若 在可行域内可根据图 1 和图 2 所示算法求解该问 题，否则该问题无解，与本文第 2. 4 节关于算法优势 的理论分析一致． 此外，从图 4 中曲线可以看出，若 lk已知，由于 N 设置的比较大( N = 100) ，所以存在 多个相邻的点处 P* k 的采样值相同的情况，这在求解 ( MOOP) 时会使算法搜索范围较大而影响求解效 率，因此在求解模型时需要合理设置 N 的值，与本 文第 2. 4 节关于算法终止条件的理论分析一致; 而 当 lk未知需要根据图 4 所示曲线提出问题时，可适 当增大 N 的值，以保证有足够多 f1k ( θ) 和 f2k ( θ) 的 观测值用于确定不同的应急救援物资车辆运输路线 优化问题． 图 3 5 × 5 随机路网 Fig． 3 5 × 5 type random road network 其次，测试算法的求解效率． 令参数l = ( lk － f2k ( 0) ) /( f2k ( 1) － f2k ( 0) ) ( 0≤l≤1) ，当 X = 1 时， 若设置一个较大的 N 值并根据式( 2) 检验每一个点 的 f2k ( θ) 值来搜索最优解，会导致计算最优解的速 度随 l 的增加而减慢; 而图 1 所示算法在设计时令 N = 3，并以两个三等分点作为试探点反复缩减搜索 区间寻找最优解，结合图 5( a) 可知 Dijstra 算法调用 图 4 基于 Python 平台的辅助决策函数曲线( X = 2，N = 100) Fig． 4 Auxiliary function curves based on Python platform ( X = 2， N = 100) 次数并不随 l 直线上升． 根据本文第 2. 4 节对算法 时间复杂度的分析可知，算法求解效率与 Dijstra 算 法调用次数成反比，因此基于图 5( a) 的分析说明图 1 所示算法结构削弱了参数 l 的变化对模型求解速 度的影响，从而验证了第 2. 4 节关于算法终止条件 的理论． 从图 5 ( b) 可以看出，当节点规模 n 增加 时，算法求解效率有变慢的趋势． 这是因为随着节 点数的增加，起点到终点的路段组合方式增加，最优 解的搜索范围随之增大． 但反复测试发现，当 X = 2 时，在 10000 节点以内的随机路网图上利用本文算 法计算最优路线，调用 Dijstra 算法 10 次以内即可获 得最优解，证明本文算法对于含有两个优化目标的 应急救援物资车辆路线选择问题有较高的求解效 率． 从图 5( c) 可以看出，优化目标数量越多，算法 的求解速度越慢． 但应急物资运输车辆路线决策中 的优化目标一般不会超过五个，对于 400 节点的随 机路网而言，当 X≤5 时利用本文算法一般调用 Dijstra算法 30 次以内即可获得模型的最优解，说明 在节点规模较小的地图上寻找运输路线多目标优化 的最优解时，本文算法求解效率较高． 若在较大的 地图上寻找最佳运输路线，且含有三个以上优化目 标时，保证本文模型求解效率的一个可行的办法是， 针对不同场合设计多个最优路径算法，当距离终点 较远时用大网格粗略寻找最优前进方向，而当接近 终点的时候切换到小网格精细寻找最优前进方向． 当 X = 1 时假设决策者以经济性指标作为次要优化 目标，假定车辆从 v1→vn时可承受的运输成本最大 值为 1100 元，测试图 1 所示算法的求解效率与 δ 的 关系． 分析表 1 中数据可知，当 0. 001 ＜ δ≤0. 1 时， 随着 δ 的减小，所求近似最优路径 Papp k 的安全概率 增加，说明 δ 过大可能使近似最优解 Papp k 与理想最 · 0931 ·

第10期 盖文妹等：应急救援物资车辆运输路线多目标优化 ·1391· 优解P之间误差较大；当δ≤0.001时，δ继续减 明δ过小可能使算法求解速度变慢.因此可以得出 小，所求近似最优路径P的安全概率相同，未出 结论，8并不是越小越好.这与本文第2.4节关于终 现更优的路径但Dijstra算法调用次数仍在增加，说 止条件的理论分析相符. a (b) 0.2 0.4 0.6 0.8 1.0 100x100 60 (e) 50 40 30 20 10 图5算法调用D时jstm算法次数与参数km及X关系.(a)n=20×20,X=1:(b)1=0.75,X=1:(c)n=20×20,1=0.75,N=9,K1=3, K2=6 Fig.5 Relationships between the number of calling Dijstra algorithm and l,n or X:(a)n =20 x 20,X=1;(b)1=0.75,X=1;(c)n=20 x 20,1=0.75,N=9,K1=3,K2=6 表1算法调用Dijstra算法次数与8的关系(n=20×20,X=1,l= 数9-0，若只考虑行驶时间的最优化，可利用Dijstra 0.75) 算法直接求解车辆的最佳往返路线，如表2所示 Table 1 Relationship between the number of calling Dijstra algorithm and8(n=20×20,X=1,1=0.75) 但一味追求时效性而忽略安全性或经济性指标，可 f(e)f5(6) 能使参与救援物资运输的工作人员面临较高的风险 R(PP）A(P)/元D 或运输成本过高而在运力紧张的条件下难以实现. 0.1 0.5534 1.264 0.575 632 6 此外，当车辆从物资需求点返回支持保障中心时，若 0.01 0.2998 1.98 0.741 990 10 后续没有新的运输任务，此时运输路线的时效性指 0.001 0.2169 2.066 0.805 1033 13 标相比安全性和经济性指标的重要性有所下降.因 0.00010.21692.066 0.805 1033 16 此在本次实验中，将应急救援物资车辆往返运输路 0.000010.2169 2.066 0.805 1033 20 线的优化分解为两个过程，并对应设置两种不同的 (2)真实路网实验.重大事故或自然灾害一旦 情景，每种情景下车辆路线优化的目标均为满足限 发生，药品和医疗人员、专业救援设备和救援队、食 制条件下的安全概率最大化：①车辆从支持保障中 品以及水等必须尽快从支持保障中心运往受到影响 心前往物资需求点时，为最佳路线的选择设置时效 的区域，尽快帮助伤者和支持救援行动.因此当物 性和经济性两个方面的限制条件；②车辆从物资需 资运输车辆前往物资需求点时，车辆在物流网络上 求点返回支持保障中心时，只将满足经济性指标作 的行驶时间是路线优化时一个十分重要的参 为唯一的限制条件.在模拟中，地图数据采用

第 10 期 盖文妹等: 应急救援物资车辆运输路线多目标优化 优解 P* k 之间误差较大; 当 δ≤0. 001 时，δ 继续减 小，所求近似最优路径 Papp k 的安全概率相同，未出 现更优的路径但 Dijstra 算法调用次数仍在增加，说 明 δ 过小可能使算法求解速度变慢． 因此可以得出 结论，δ 并不是越小越好． 这与本文第 2. 4 节关于终 止条件的理论分析相符． 图 5 算法调用 Dijstra 算法次数与参数 l、n 及 X 关系． ( a) n = 20 × 20，X = 1; ( b) l = 0. 75，X = 1; ( c) n = 20 × 20，l = 0. 75，N = 9，K1 = 3， K2 = 6 Fig． 5 Ｒelationships between the number of calling Dijstra algorithm and l，n or X: ( a) n = 20 × 20，X = 1; ( b) l = 0. 75，X = 1; ( c) n = 20 × 20，l = 0. 75，N = 9，K1 = 3，K2 = 6 表 1 算法调用 Dijstra 算法次数与 δ 的关系( n = 20 × 20，X = 1，l = 0. 75) Table 1 Ｒelationship between the number of calling Dijstra algorithm and δ ( n = 20 × 20，X = 1，l = 0. 75) δ f11 ( θ) f21 ( θ) Ｒ( Papp k ) Ak ( Papp k ) /元 D 0. 1 0. 5534 1. 264 0. 575 632 6 0. 01 0. 2998 1. 98 0. 741 990 10 0. 001 0. 2169 2. 066 0. 805 1033 13 0. 0001 0. 2169 2. 066 0. 805 1033 16 0. 00001 0. 2169 2. 066 0. 805 1033 20 ( 2) 真实路网实验． 重大事故或自然灾害一旦 发生，药品和医疗人员、专业救援设备和救援队、食 品以及水等必须尽快从支持保障中心运往受到影响 的区域，尽快帮助伤者和支持救援行动． 因此当物 资运输车辆前往物资需求点时，车辆在物流网络上 的行驶时间是路线优化时一个十分重要的参 数［19--20］，若只考虑行驶时间的最优化，可利用Dijstra 算法直接求解车辆的最佳往返路线，如表 2 所示． 但一味追求时效性而忽略安全性或经济性指标，可 能使参与救援物资运输的工作人员面临较高的风险 或运输成本过高而在运力紧张的条件下难以实现． 此外，当车辆从物资需求点返回支持保障中心时，若 后续没有新的运输任务，此时运输路线的时效性指 标相比安全性和经济性指标的重要性有所下降． 因 此在本次实验中，将应急救援物资车辆往返运输路 线的优化分解为两个过程，并对应设置两种不同的 情景，每种情景下车辆路线优化的目标均为满足限 制条件下的安全概率最大化: ①车辆从支持保障中 心前往物资需求点时，为最佳路线的选择设置时效 性和经济性两个方面的限制条件; ②车辆从物资需 求点返回支持保障中心时，只将满足经济性指标作 为唯 一 的 限 制 条 件． 在 模 拟 中，地 图 数 据 采 用 · 1931 ·

·1392 北京科技大学学报 第36卷 Mapinfo中的mif数据格式Pn,路段的长度参数通过 O→D或D→0的最佳运输路线其时效性最好，能 读取地图数据获得，不同路段的平均行驶速度、安全 使运输时间在物资需求点可承受范围内，但是其 概率和运输成本均为假定设置，根据路段长度和行 安全性不佳，车辆沿该路线行驶时风险较高，而且 驶速度可求得车辆在路段上的行驶时间.假定设置 运输成本也超出了可承受运输成本的最大值：而 支持保障中心和受灾地点的位置并分别用节点0 基于本文所提算法，分情况计算得到两条不同的 和节点D表示，参数设置与路线优化结果如表2所 运输路线，其中O+D的最佳运输路线不仅兼顾了 示，图6为利用本文算法计算的最佳车辆往返路 物资运输的时效性和安全性的要求，还最大限度 线，图中箭头表示车辆前进方向：利用本文算法计算 地保障了救援人员的安全，而D→O的最佳运输路 O→D的最佳路线时，选择图2所示算法计算；计算 线，由于没有时间限制条件，在使安全概率最大化 D→O的最佳路线时，选择图1所示算法计算.从图 的同时最大限度的降低了物资运输成本，一定程 6可以看出，由于往返时的优化目标不同，使得O→ 度上可以缓解运力紧张的状况.因此在多属性应 D的最佳路线和D→O的最佳路线并不完全重合. 急物流决策中，相比Dijstra算法，本文算法在优化 对比表2中数据可知：基于传统Dijstra算法计算 结果上更具优势 表2基于本文算法与Dijstra算法的参数设置与路线优化结果 Table 2 Parameters and route selection results of the proposed algorithm and Dijstra algorithm 次要优化 最佳运输路线 算法 车辆行进方向 首要优化目标 限制条件 目标数量X 路线行驶时间/min路线安全概率/%路线运输成本/元 Dijstra算法 OD(或D+O) 行驶时间最短 无 239 51.08 1232 本文算法 D→0 安全概率最大化 运输成本≤900元 357 86.75 899 运输成本≤1100元 本文算法 0D 安全概率最大化 2 274 91.62 1015 运输时间≤300min 量理具 复迭代调用Dijstra算法寻找最优解.经随机路网和 真实路网的模拟测试表明，本文算法在应急救援物 资车辆运输路线的多目标优化问题中有较好的应用 效果，并且求解效率较高 (2)本文从简单的应急救援物资车辆运输路线 双目标优化问题入手，利用辅助决策函数性质设计 应急救援物资车辆运输路线的双目标优化搜索算 法，并将之推广至含有三个及三个以上优化目标的 应急救援物资车辆运输路线选择问题，不仅可以对 车辆的单一方向路线进行多目标优化，还能对车辆 的往返路线进行多目标优化.最后引入动态网络流 图6应急救援物资运输最佳往返路线 Fig.6 Best round-trip route of transporting emergency goods and 分析中的时间扩展图的概念，将本文算法推广至应 materials 急物资运输路线的动态优化问题.应急物资车辆运 输路线的确定对于事故灾害应急预案的编制具有重 综上测试结果可以得出结论，算法的模拟测试 要的意义 结果与本文理论分析一致，证明本文模型及算法在 应急救援物资车辆运输路线多目标优化问题中有较 (3)本文应急救援物资车辆运输路线的多目标 优化数学模型适用于灾变条件下救援物资运输调度 好的应用效果，并且求解效率较高 优化问题，也可以扩展到应急决策中的其他路线选 4结论 择与优化问题. (1)本文运用运筹学中图论及多目标优化的理 参考文献 论和方法建立应急救援物资车辆最佳运输路线数学 [1]Wu QS,Qian X M,Guo Z F.Probability of receptor lethality in 模型，并在辅助决策函数构造的搜索空间上通过反 blowout of sour gas wells.Pet Explor Dev,2009,36(5):641

北 京 科 技 大 学 学 报 第 36 卷 MapInfo中的 mif 数据格式［21］，路段的长度参数通过 读取地图数据获得，不同路段的平均行驶速度、安全 概率和运输成本均为假定设置，根据路段长度和行 驶速度可求得车辆在路段上的行驶时间． 假定设置 支持保障中心和受灾地点的位置并分别用节点 O 和节点 D 表示，参数设置与路线优化结果如表 2 所 示，图 6 为利用本文算法计算的最佳车辆往返路 线，图中箭头表示车辆前进方向: 利用本文算法计算 O→D 的最佳路线时，选择图 2 所示算法计算; 计算 D→O 的最佳路线时，选择图 1 所示算法计算． 从图 6 可以看出，由于往返时的优化目标不同，使得 O→ D 的最佳路线和 D→O 的最佳路线并不完全重合． 对比表 2 中数据可知: 基于传统 Dijstra 算法计算 O→D或 D→O 的最佳运输路线其时效性最好，能 使运输时间在物资需求点可承受范围内，但是其 安全性不佳，车辆沿该路线行驶时风险较高，而且 运输成本也超出了可承受运输成本的最大值; 而 基于本文所提算法，分情况计算得到两条不同的 运输路线，其中 O→D 的最佳运输路线不仅兼顾了 物资运输的时效性和安全性的要求，还最大限度 地保障了救援人员的安全，而 D→O 的最佳运输路 线，由于没有时间限制条件，在使安全概率最大化 的同时最大限度的降低了物资运输成本，一定程 度上可以缓解运力紧张的状况． 因此在多属性应 急物流决策中，相比Dijstra算法，本文算法在优化 结果上更具优势． 表 2 基于本文算法与 Dijstra 算法的参数设置与路线优化结果 Table 2 Parameters and route selection results of the proposed algorithm and Dijstra algorithm 算法 车辆行进方向 首要优化目标 限制条件 次要优化 目标数量 X 最佳运输路线 路线行驶时间/min 路线安全概率/% 路线运输成本/元 Dijstra 算法 O→D( 或 D→O) 行驶时间最短 无 0 239 51. 08 1232 本文算法 D→O 安全概率最大化 运输成本≤900 元 1 357 86. 75 899 本文算法 O→D 安全概率最大化 运输成本≤1100 元 运输时间≤300 min 2 274 91. 62 1015 图 6 应急救援物资运输最佳往返路线 Fig． 6 Best round-trip route of transporting emergency goods and materials 综上测试结果可以得出结论，算法的模拟测试 结果与本文理论分析一致，证明本文模型及算法在 应急救援物资车辆运输路线多目标优化问题中有较 好的应用效果，并且求解效率较高． 4 结论 ( 1) 本文运用运筹学中图论及多目标优化的理 论和方法建立应急救援物资车辆最佳运输路线数学 模型，并在辅助决策函数构造的搜索空间上通过反 复迭代调用 Dijstra 算法寻找最优解． 经随机路网和 真实路网的模拟测试表明，本文算法在应急救援物 资车辆运输路线的多目标优化问题中有较好的应用 效果，并且求解效率较高． ( 2) 本文从简单的应急救援物资车辆运输路线 双目标优化问题入手，利用辅助决策函数性质设计 应急救援物资车辆运输路线的双目标优化搜索算 法，并将之推广至含有三个及三个以上优化目标的 应急救援物资车辆运输路线选择问题，不仅可以对 车辆的单一方向路线进行多目标优化，还能对车辆 的往返路线进行多目标优化． 最后引入动态网络流 分析中的时间扩展图的概念，将本文算法推广至应 急物资运输路线的动态优化问题． 应急物资车辆运 输路线的确定对于事故灾害应急预案的编制具有重 要的意义． ( 3) 本文应急救援物资车辆运输路线的多目标 优化数学模型适用于灾变条件下救援物资运输调度 优化问题，也可以扩展到应急决策中的其他路线选 择与优化问题． 参 考 文 献 ［1］ Wu Q S，Qian X M，Guo Z F． Probability of receptor lethality in blowout of sour gas wells． Pet Explor Dev，2009，36( 5) : 641 · 2931 ·

第10期 盖文妹等：应急救援物资车辆运输路线多目标优化 ·1393· (吴庆善，钱新明，郭再富.含硫气井井喷事故受体致死概率 优化问题.沈阳建筑大学学报：自然科学版，2012,28(5)： 分析.石油勘探与开发，2009,36(5)：641) 944) Deng Y F.Study on Pedestrian Eracuation Model for Accident [11]Wang HJ,Wang J,Ma S H,et al.Dynamic decision-making for Releasing Taric Vapors [Dissertation].Beijing:University of Sci- emergency materials dispatching based on fuzzy demand.Ind Eng ence and Technology Beijing,2008 Manage,2012,17(3):16 (邓云峰.毒气泄漏事故人员疏散模型及应用研究[学位论 (王海军，王婧，马士华，等。模糊需求条件下应急物资调度 文].北京：北京科技大学，2008) 的动态决策研究.工业工程与管理，2012,17(3)：16) B]Zhang Y,Guo X F,Wang X F.Route choice for transporting [12]Zhang L,Ma L,Yuan C A.Research on multi-objective model exigency succor materials.J Saf Enriron,2006,6(3):51 for emergency rescue assignment with time limit.China Saf Sci (张毅，郭晓汾，王笑风.应急救援物资车辆运输线路的选 J,2012,22(6):170 择.安全与环境学报，2006,6(3)：51) (张雷，马璐，元昌安.应急救援多目标时限指派模型.中国 4]Papinski D,Scott D M.A GIS-based toolkit for route choice anal- 安全科学学报，2012,22(6)：170) ysis.J Transp Geogr,2011,19(3)434 [13]Handler G Y,Zang I.A dual algorithm for the constrained shor- [5]Xiao GQ,Wen L M,Chen BZ,et al.Shortest evacuation route test path problem.Netcorks,1980,10(4):293 on toxic leakage.J Northeast Univ Nat Sci,2001,22(6):674 [14]Rahmati S H A,Hajipour V,Niaki S T A.A soft-computing (肖国清，温丽敏，陈宝智，等.毒气泄漏时的最佳疏散路径 pareto-based meta-heuristic algorithm for a multiobjective multi- 东北大学学报：自然科学版，2001,22(6)：674) server facility location problem.Appl Soft Comput,2013,13 Gao R,JiangZA,Dong F,et al.Mathematical model and algorithm (4):1728 of a dynamic optimum rescue route during mine fire time based on 15]Li D M.Mean Gaussian Characteristics and Comparative Study. MapObject.J Univ Sci Technol Beijing,2008,30(7):705 Changchun:Jilin University Press,2012 (高蕊，蒋仲安，董枫，等.基于MapObject的矿井火灾动态 (李大矛.平均值的高斯特征与比较研究.长春：吉林大学 最佳救灾路线数学模型和算法.北京科技大学学报，2008,30 出版社，2012) (7):705) [16]Xie C,Lin D Y,Travis Waller S.A dynamic evacuation network Yu W B,Wu X G,Wang T,et al.Research on the evacuation optimization problem with lane reversal and crossing elimination route of passage in ship based on shortest paths algorithm.Chin J strategies.Transp Res Part E,2010,46(3):295 Ship Res,2008,3(2):16 [17]Jarvis JJ,Ratliff H D.Note:some equivalent objectives for (余为波，吴晓光，王涛，等.基于最短路径算法的舰船通道 dynamic network flow problems.Manage Sci,1982,28 (1): 逃逸路线研究.中国舰船研究，2008,3(2)：16) 106 Current J,Marsh M.Multiobjective transportation network design [18]Barbehenn M.A note on the complexity of Dijkstra's algorithm for and routing problems:taxonomy and annotation.EurOper Res, graphs with weighted vertices.IEEE Trans Comput,1998,47 1993,65(1):4 (2):263 9]Li M,Wu L,Zhang K B.Comparative study of several algorithm [19]Yuan Y,Wang D.Path selection model and algorithm for emer- for travelling salesman problem.Chongqing Unie Posts Telecom- gency logistics management.Comput Ind Eng,2009,56(3): mun Nat Sci,2008,20(5):624 1081 (李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研 20]Zhang X,Zhang Z,Zhang Y,et al.Route selection for emergen- 究.重庆邮电大学学报：自然科学版，2008,20(5)：624) cy logistics management:a bio-inspired algorithm.Saf Sci, [10]Zhao M,Song X Y,Dong J,et al.Using genetic algorithm to 2013,54:87 solve scheduling optimization problem of emergeney supplies. 221]Ni Q,Rossetti M D.Simulation evacuation modeling of a Shenyang Jianzhu Univ Nat Sci,2012,28 (5):944 commercial shopping district to safe zones.Int Mass Emerg Dis- (赵明，宋晓宇，董洁，等.利用遗传算法求解应急物资调度 asters,2013,31(1):38

第 10 期 盖文妹等: 应急救援物资车辆运输路线多目标优化 ( 吴庆善，钱新明，郭再富． 含硫气井井喷事故受体致死概率 分析． 石油勘探与开发，2009，36( 5) : 641) ［2］ Deng Y F． Study on Pedestrian Evacuation Model for Accident Ｒeleasing Toxic Vapors［Dissertation］． Beijing: University of Sci￾ence and Technology Beijing，2008 ( 邓云峰． 毒气泄漏事故人员疏散模型及应用研究［学位论 文］． 北京: 北京科技大学，2008) ［3］ Zhang Y，Guo X F，Wang X F． Ｒoute choice for transporting exigency succor materials． J Saf Environ，2006，6( 3) : 51 ( 张毅，郭晓汾，王笑风． 应急救援物资车辆运输线路的选 择． 安全与环境学报，2006，6( 3) : 51) ［4］ Papinski D，Scott D M． A GIS-based toolkit for route choice anal￾ysis． J Transp Geogr，2011，19( 3) : 434 ［5］ Xiao G Q，Wen L M，Chen B Z，et al． Shortest evacuation route on toxic leakage． J Northeast Univ Nat Sci，2001，22( 6) : 674 ( 肖国清，温丽敏，陈宝智，等． 毒气泄漏时的最佳疏散路径． 东北大学学报: 自然科学版，2001，22( 6) : 674) ［6］ Gao Ｒ，Jiang Z A，Dong F，et al． Mathematical model and algorithm of a dynamic optimum rescue route during mine fire time based on MapObject． J Univ Sci Technol Beijing，2008，30( 7) : 705 ( 高蕊，蒋仲安，董枫，等． 基于 MapObject 的矿井火灾动态 最佳救灾路线数学模型和算法． 北京科技大学学报，2008，30 ( 7) : 705) ［7］ Yu W B，Wu X G，Wang T，et al． Ｒesearch on the evacuation route of passage in ship based on shortest paths algorithm． Chin J Ship Ｒes，2008，3( 2) : 16 ( 余为波，吴晓光，王涛，等． 基于最短路径算法的舰船通道 逃逸路线研究． 中国舰船研究，2008，3( 2) : 16) ［8］ Current J，Marsh M． Multiobjective transportation network design and routing problems: taxonomy and annotation． Eur J Oper Ｒes， 1993，65( 1) : 4 ［9］ Li M，Wu L，Zhang K B． Comparative study of several algorithm for travelling salesman problem． J Chongqing Univ Posts Telecom￾mun Nat Sci，2008，20( 5) : 624 ( 李敏，吴浪，张开碧． 求解旅行商问题的几种算法的比较研 究． 重庆邮电大学学报: 自然科学版，2008，20( 5) : 624) ［10］ Zhao M，Song X Y，Dong J，et al． Using genetic algorithm to solve scheduling optimization problem of emergency supplies． J Shenyang Jianzhu Univ Nat Sci，2012，28( 5) : 944 ( 赵明，宋晓宇，董洁，等． 利用遗传算法求解应急物资调度 优化问题． 沈阳建筑大学学报: 自然科学版，2012，28( 5) : 944) ［11］ Wang H J，Wang J，Ma S H，et al． Dynamic decision-making for emergency materials dispatching based on fuzzy demand． Ind Eng Manage，2012，17( 3) : 16 ( 王海军，王婧，马士华，等． 模糊需求条件下应急物资调度 的动态决策研究． 工业工程与管理，2012，17( 3) : 16) ［12］ Zhang L，Ma L，Yuan C A． Ｒesearch on multi-objective model for emergency rescue assignment with time limit． China Saf Sci J，2012，22( 6) : 170 ( 张雷，马璐，元昌安． 应急救援多目标时限指派模型． 中国 安全科学学报，2012，22( 6) : 170) ［13］ Handler G Y，Zang I． A dual algorithm for the constrained shor￾test path problem． Networks，1980，10( 4) : 293 ［14］ Ｒahmati S H A，Hajipour V，Niaki S T A． A soft-computing pareto-based meta-heuristic algorithm for a multi-objective multi￾server facility location problem． Appl Soft Comput，2013，13 ( 4) : 1728 ［15］ Li D M． Mean Gaussian Characteristics and Comparative Study． Changchun: Jilin University Press，2012 ( 李大矛． 平均值的高斯特征与比较研究． 长春: 吉林大学 出版社，2012) ［16］ Xie C，Lin D Y，Travis Waller S． A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies． Transp Ｒes Part E，2010，46( 3) : 295 ［17］ Jarvis J J，Ｒatliff H D． Note: some equivalent objectives for dynamic network flow problems． Manage Sci，1982，28 ( 1 ) : 106 ［18］ Barbehenn M． A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices． IEEE Trans Comput，1998，47 ( 2) : 263 ［19］ Yuan Y，Wang D． Path selection model and algorithm for emer￾gency logistics management． Comput Ind Eng，2009，56 ( 3 ) : 1081 ［20］ Zhang X，Zhang Z，Zhang Y，et al． Ｒoute selection for emergen￾cy logistics management: a bio-inspired algorithm． Saf Sci， 2013，54: 87 ［21］ Ni Q， Ｒossetti M D． Simulation evacuation modeling of a commercial shopping district to safe zones． Int J Mass Emerg Dis￾asters，2013，31( 1) : 38 · 3931 ·