·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 ·