·1390 北京科技大学学报 第36卷 表示列数，令1=(0,0)，tn=(Y-1,Z-1),图3表 1.8 ·…y=f《( 示(0,0)→(Y-1,Z-1)的一张有向随机路网图. 1.6 首先测试辅助函数的单调性.假设求(0,0)→(Y- 14 1,L 可行域 1,Z-1)的一条应急救援物资车辆最佳行进路线 1.2 ( 7*1 可行域 P,路P的首要优化目标为安全概率最大化，路P的 运输成本、行驶时间等作为第k(k=1,2,…,X)个次 0.8 要优化目标.将自变量0的区间D,1]平均分成N 0.6 份，在随机网络上反复测试发现，当N较大时均能 0.4 获得类似图4的辅助决策函数曲线.从图4可以看 0% 0.2 0.4 0.6 0.8 1.0 出，f(0)和f2()随系数0递减，f(0)和f2(0) 加权系数.0 随系数0递增，与本文辅助函数性质2描述一致 图4基于ython平台的辅助决策函数曲线(X=2,N=100) 其次，在未知次要优化目标限制条件值的情况下， Fig.4 Auxiliary function curves based on Python platform (Y=2, 若想提出新的路线优化问题，只要选定一个值满 N=100) 足2l落入图4所示可行域即可；若己知4的值，只 次数并不随！直线上升.根据本文第2.4节对算法 要根据图4所示曲线判断7244是否落入可行域，若 时间复杂度的分析可知，算法求解效率与Dijstra算 在可行域内可根据图1和图2所示算法求解该问 法调用次数成反比，因此基于图5(a)的分析说明图 题，否则该问题无解，与本文第2.4节关于算法优势 1所示算法结构削弱了参数1的变化对模型求解速 的理论分析一致.此外，从图4中曲线可以看出，若 度的影响，从而验证了第2.4节关于算法终止条件 L己知，由于N设置的比较大(N=100),所以存在 的理论.从图5(b)可以看出，当节点规模n增加 多个相邻的点处P的采样值相同的情况，这在求解 时，算法求解效率有变慢的趋势.这是因为随着节 (MOOP)时会使算法搜索范围较大而影响求解效 点数的增加，起点到终点的路段组合方式增加，最优 率，因此在求解模型时需要合理设置V的值，与本 解的搜索范围随之增大.但反复测试发现，当X=2 文第2.4节关于算法终止条件的理论分析一致：而 时，在10000节点以内的随机路网图上利用本文算 当4未知需要根据图4所示曲线提出问题时，可适 法计算最优路线，调用Dijstra算法10次以内即可获 当增大N的值，以保证有足够多f:(a)和fx（0)的 得最优解，证明本文算法对于含有两个优化目标的 观测值用于确定不同的应急救援物资车辆运输路线 应急救援物资车辆路线选择问题有较高的求解效 优化问题 率.从图5(c)可以看出，优化目标数量越多，算法 (4.0) 3.0 (2.0 的求解速度越慢.但应急物资运输车辆路线决策中 1.0 (4,1 0.0 的优化目标一般不会超过五个，对于400节点的随 3.1) ● 机路网而言，当X≤5时利用本文算法一般调用 4.2) 2.1 /.D 0.1) Dijstra算法30次以内即可获得模型的最优解，说明 /3.2 43 2.2 在节点规模较小的地图上寻找运输路线多目标优化 12 0.2 /33 的最优解时，本文算法求解效率较高。若在较大的 /2.3) (3.4) 1.3) 0.3) 地图上寻找最佳运输路线，且含有三个以上优化目 (249 (1,4) 0.4 标时，保证本文模型求解效率的一个可行的办法是， 图35×5随机路网 针对不同场合设计多个最优路径算法，当距离终点 Fig.3 5 x5 type random road network 较远时用大网格粗略寻找最优前进方向，而当接近 其次，测试算法的求解效率.令参数l=(4- 终点的时候切换到小网格精细寻找最优前进方向. f(0))/(fx(1)-f4(0))(0≤l≤1)，当X=1时， 当X=1时假设决策者以经济性指标作为次要优化 若设置一个较大的V值并根据式(2)检验每一个点 目标，假定车辆从心，→时可承受的运输成本最大 的f()值来搜索最优解，会导致计算最优解的速 值为1100元，测试图1所示算法的求解效率与δ的 度随！的增加而减慢：而图1所示算法在设计时令 关系.分析表1中数据可知，当0.001<8≤0.1时， N=3,并以两个三等分点作为试探点反复缩减搜索 随着δ的减小，所求近似最优路径P聊的安全概率 区间寻找最优解，结合图5(a)可知Dijstra算法调用 增加，说明6过大可能使近似最优解P与理想最北 京 科 技 大 学 学 报 第 36 卷 表示列数，令 v1 = ( 0，0) ，vn = ( Y － 1，Z － 1) ，图 3 表 示( 0，0) →( Y － 1，Z － 1) 的一张有向随机路网图． 首先测试辅助函数的单调性． 假设求( 0，0) →( Y － 1，Z － 1) 的一条应急救援物资车辆最佳行进路线 P，路 P 的首要优化目标为安全概率最大化，路 P 的 运输成本、行驶时间等作为第 k( k = 1，2，…，X) 个次 要优化目标． 将自变量 θ 的区间［0，1］平均分成 N 份，在随机网络上反复测试发现，当 N 较大时均能 获得类似图 4 的辅助决策函数曲线． 从图 4 可以看 出，f11 ( θ) 和 f12 ( θ) 随系数 θ 递减，f21 ( θ) 和 f22 ( θ) 随系数 θ 递增，与本文辅助函数性质 2 描述一致． 其次，在未知次要优化目标限制条件值 lk的情况下， 若想提出新的路线优化问题，只要选定一个 lk值满 足 η2k lk落入图 4 所示可行域即可; 若已知 lk的值，只 要根据图 4 所示曲线判断 η2k lk是否落入可行域，若 在可行域内可根据图 1 和图 2 所示算法求解该问 题，否则该问题无解，与本文第 2. 4 节关于算法优势 的理论分析一致． 此外，从图 4 中曲线可以看出，若 lk已知，由于 N 设置的比较大( N = 100) ，所以存在 多个相邻的点处 P* k 的采样值相同的情况，这在求解 ( MOOP) 时会使算法搜索范围较大而影响求解效 率，因此在求解模型时需要合理设置 N 的值，与本 文第 2. 4 节关于算法终止条件的理论分析一致; 而 当 lk未知需要根据图 4 所示曲线提出问题时，可适 当增大 N 的值，以保证有足够多 f1k ( θ) 和 f2k ( θ) 的 观测值用于确定不同的应急救援物资车辆运输路线 优化问题． 图 3 5 × 5 随机路网 Fig． 3 5 × 5 type random road network 其次，测试算法的求解效率． 令参数l = ( lk － f2k ( 0) ) /( f2k ( 1) － f2k ( 0) ) ( 0≤l≤1) ，当 X = 1 时， 若设置一个较大的 N 值并根据式( 2) 检验每一个点 的 f2k ( θ) 值来搜索最优解，会导致计算最优解的速 度随 l 的增加而减慢; 而图 1 所示算法在设计时令 N = 3，并以两个三等分点作为试探点反复缩减搜索 区间寻找最优解，结合图 5( a) 可知 Dijstra 算法调用 图 4 基于 Python 平台的辅助决策函数曲线( X = 2，N = 100) Fig． 4 Auxiliary function curves based on Python platform ( X = 2， N = 100) 次数并不随 l 直线上升． 根据本文第 2. 4 节对算法 时间复杂度的分析可知，算法求解效率与 Dijstra 算 法调用次数成反比，因此基于图 5( a) 的分析说明图 1 所示算法结构削弱了参数 l 的变化对模型求解速 度的影响，从而验证了第 2. 4 节关于算法终止条件 的理论． 从图 5 ( b) 可以看出，当节点规模 n 增加 时，算法求解效率有变慢的趋势． 这是因为随着节 点数的增加，起点到终点的路段组合方式增加，最优 解的搜索范围随之增大． 但反复测试发现，当 X = 2 时，在 10000 节点以内的随机路网图上利用本文算 法计算最优路线，调用 Dijstra 算法 10 次以内即可获 得最优解，证明本文算法对于含有两个优化目标的 应急救援物资车辆路线选择问题有较高的求解效 率． 从图 5( c) 可以看出，优化目标数量越多，算法 的求解速度越慢． 但应急物资运输车辆路线决策中 的优化目标一般不会超过五个，对于 400 节点的随 机路网而言，当 X≤5 时利用本文算法一般调用 Dijstra算法 30 次以内即可获得模型的最优解，说明 在节点规模较小的地图上寻找运输路线多目标优化 的最优解时，本文算法求解效率较高． 若在较大的 地图上寻找最佳运输路线，且含有三个以上优化目 标时，保证本文模型求解效率的一个可行的办法是， 针对不同场合设计多个最优路径算法，当距离终点 较远时用大网格粗略寻找最优前进方向，而当接近 终点的时候切换到小网格精细寻找最优前进方向． 当 X = 1 时假设决策者以经济性指标作为次要优化 目标，假定车辆从 v1→vn时可承受的运输成本最大 值为 1100 元，测试图 1 所示算法的求解效率与 δ 的 关系． 分析表 1 中数据可知，当 0. 001 ＜ δ≤0. 1 时， 随着 δ 的减小，所求近似最优路径 Papp k 的安全概率 增加，说明 δ 过大可能使近似最优解 Papp k 与理想最 · 0931 ·