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