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