第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所示算法循环部分增加一个终止条件-u<δ， 根据辅助决策函数曲线设置合理的限制条件，从而 如图1中虚线所示，其中δ>0：同理，合理设置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 ·