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

第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≤1，设P.和Ps分别为0=a 研究 和0=B时满足公式(3)的一条路，根据性质1可知 2.1含两个优化目标的最佳运输路线算法 ∑[a·(-lrg）+(1-a)·72ua]≤ (yeP。 应急救援物资车辆运输路线双目标优化问题 (bi-objective optimization problem,BOOP）是 ∑[a(-lr)+(1-a)·n2a#], (ieP8 (MOOP)中的一个常见情况，Handler和Zangti证 明了该问题是NP完全的.为降低计算的复杂度， 多.B-(-l+1-nJ> 本文基于启发式算法思想，借助加权平均法构造 ∑.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)<L,那么对于Hk=1,2, (epeep …,X,根据式(1)和式(2)可知P。=P ∑.(n240)=4A:(P)， 可eP 对于(u,)二(0,1)，若将区间(u,)均分为 有 N份，N为正整数，对于K1<K2∈{1,2，…，N-1}, -lnR(Pa)≥-lnR(Pg), 基于辅助决策函数的上述性质，容易证明有如下结 72Ak(Pa）≤n2sA(Pg)， 论成立 得 结论1假设对应于0=u+K,(v-u)/W、0= f4(a)≤fr(B),fi(a)≥fiu(B) u+K,(v-)/N及0=5的满足式(3)的路径存在且 所以f(0)和f.(0)分别为0,1]上的增函数和减 分别为P.Pa和P,那么： 函数.假设0=0和0=1时满足式(3)的路径分别 ①若f(u+K1(w-)/N)>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)<n24,则R(P)≤ ()P0 R(Pe)且Ax(P)<l,Hg∈(u,u+K2(u-u)/N]: f(1)=-,Πrg=max ③若((u+K,(u-u)/W)-2)(f(u+ 所以 K2(u-)/N)-2ul4)<0,则R(P）≤R(PB)与 A24(P)>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), 若l<n2f(0),P无解；若1=n2f4(0),则 fu(1)=-InR(P)=min(-InR(P))= P=P。;若l4≥nf（1),则P=P:若n2· min (-InR(P))minfi(). f4(0)<l<n4·f(1),则可以通过N分区间D, 命题得证. 1]的方法获得满足A24(P)<l4的一系列，→n的 性质3设0=0和0=1时满足公式(3)的路 路，这些路径即为最优解的采样值，其中满足式(1) 径分别为P和P,那么：若4(0)>n24l,P无解； 的采样值即为(BOOP)的最优解. 若f(0）=刀2lk,则P=P。:若f（1)≤72xlk,则 (2)算法可行性及流程分析.根据辅助决策函 P=P:若f4(0)<门2xl<f(1),并且存在满足 数性质1，满足式(3)的路径P,可利用Floyd算法、 式(3)的一条路P,恰能使f2（8)=n24l4,则P= Dijstra算法及A-star算法等传统最短路算法直接求 解.根据结论1可知，若将区间，]细分成N份， 证明：若日=0时P。满足式(3)，根据性质2可只要任取两个点0=u+K(v-u)/小N和0=u+ 知f(0）=724Ak（Po）=min(24A:（P)）.若 K,(v-)N作为试探点计算满足式(3)的路径，其 f(0)>n2,则A4(P）>l恒成立，因此对k=1, 中K1<K2∈{1,2，…，N-1},对于k=1,2,…,X, 2,…,X,不存，→心的一条路能同时满足式(1)和 通过比较函数值f4(u+K（v-u)/N)或f(u+ 式(2)，所以P无解；若f(0)=2,根据性质2 K,(m-）/N)与n2xl之间的关系，或者可以求得 易知不可能有另一条路径P同时满足R(P)>RP,或者至少有一段区间去掉后不会丢失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 立否 否 6<12？ Dj.PB (D-jP-P 个是 上是 0一1.调用Dktr算法 f0≤12？ 求满足式(3)的路径P, 业否 计算fj+】 40.1☐ R 0-+K(-u/N -<02-- Pmp 调用Dijkstra算法求 满足式(3)的路径P u+temp.+6 是 0)>1,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 <RPP? 2.2含三个及以上优化目标的最佳运输路线算法 1.2.…,X.N 否 >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 ·