有害危险废弃物运输网络优化选线模型研究.pdf

万方数据 万方数据 1 3 6 运筹与管 理 2 0 l O 年第1 9 卷 险和运输成本的优化选线问题模型。在以往的研究中，对于如上的风险考虑的不多，或者即使考虑了，但 是没有针对问题本身从问题复杂性和算法的角度出发考虑该问题。本文将在如上分析的条件下，考虑有 害危险废弃物运输优化选线问题中涉及的两类因素：选择该边所需要承担的风险，以及选择该边所需要承 担的成本。论文将建立相应的选线问题，并构造出相应的选线优化策略，最后证明得到的选线性能结果。 2 问题的建模与分析 首先，由于本文研究的重点是对选线算法策略的设计和策略性能的研究上，因此，我们假设，在选线问 题进行研究之前，所给运输网络图上的各条边上所具有的风险都已经经过检测后全部知道。即认为在优 化选线决策之前，给定的运输网络图上的待选线的边所具有的风险的数值已经全部已知的条件下进行的 优化选址和选线的问题。同样的，我们也假设，在选线问题进行研究之前。所给运输网络图上的各条边上 的运输成本都已经经过检测后全部知道。即认为在优化选线决策之前，给定的运输网络图上的待选线的 边所具有的运输成本的数值已经全部已知的条件下进行的优化选址和选线的问题。 同时我们假设，任意两条边上的运输风险与运输成本是其相应边上的相应运输风险与运输成本之和， 即可以直接相加。在此基础上，我们进行相应的理论建模与求解算法分析。 根据实际问题，定义有害危险废弃物品道路运输网为一个无向网络图G = ( y ，E ) ，其中顶点集合 y = ，t J ：，口。 表示一系列节点，边集合E = e = ( q ，移f ，E l ，2 ，n ，i 表示运输路径的边。 定义边上带有两个不同的非负权重，记为c o s t ：E 一尺+ 表示通过两点问的边所需要花费的费用，以及 D a n g e r ：E 一只+ 表示通过两点间的边所需要承担的风险。这两个权重函数只假设具有非负性。需要注意 的是，这里并不需要假设这两个权重函数满足三角不等式。我们考虑更为一般的问题，即上述假设中的无 向网络图G = ( y ，E ) 中的两个权重函数不考虑是否具有一定的关系。 本文所要研究的问题是：对给定的图G = ( 1 ，E ) ，和两个关于边的权重函数，c o s t ，D a n g e r ，对图上给定 的两个起迄点对s 和t ，问题是希望能够寻找到关于这两个费用都能达到最小的连接s 和f 的最短路。 以往关于最短路的相关研究已经有很多，对于上述的任意一个目标，都可以利用简单的算法( 例如 D i j l 【s t r a 算法等) 在多项式时间内得到最优解。同以往的研究不同的是，我们这里研究的是同时满足两个 目标，并且这两个目标间并没有数量关系。同时，考虑到这两个因素目标有可以相抵触，即在一个因素下 达到最优的最短路可能在另一个因素下的路径测度非常差。在以往的研究中是将这个问题处理成一个多 目标规划的问题，从而在获得目标的权重或是决策者的偏好的条件下，将其转化成一个单目标优化问题求 解。这类方法的缺陷在于：( 1 ) 权重或偏好不易获得；( 2 ) 多个目标之间的量纲不一致，不便于处理。如有 的目标可能是成本，有的目标是效用。( 3 ) 即使通过变权法，将多个目标集成起来还是无法找到不是在凸 包边界上的解。 本文将把上述问题考虑成将一个因素作为约束条件，考虑另一个因素最小化的问题，并从问题本身直 接进行分析和选线策略设计，并证明得到的算法的近似性能。考虑到在有害危险废弃物运输管理中，政府 具有主导的地位，对风险的要求特别高，我们考虑将之放到目标函数中。随后我们将考虑直接对这个问题 本身进行分析，设计出有效的选线策略算法，并证明算法所具有的良好的性能。 本文研究的问题的规范形式如下：对给定的图G = ( y ，E ) ，和两个关于边的权重函数，C o s t ，D a n g e r ，为 了分析方便，不妨假设这两个权重函数都是正整数。设P ( s t ) 表示图G = ( y ，E ) 上所有的从s 和t 的路径 的集合，对于VP 尸( s ，t ) ，定义P 上的权重为路径上各边相应权重之和，即 c o s t ( P ) = 芝：c o s t ( e ) ，D a n g e r ( P ) = ：D a n g e r ( e ) 而石 问题是对任意给定的常数B ，寻找如下最小化问题的最优解： m i nD a n g e r ( P ) 文tC o s t ( P ) 曰 P P ( s ，t ) 3 有害废弃物运输网络选线优化模型的算法设计 我们这里首先拓展近似算法的定义。以外的近似算法都是针对单目标优化问题，这里我们考虑将其 万方数据 第6 期代文强：有害危险废弃物运输网络优化选线模型研究 1 3 7 拓展到有一个约束条件下的优化问题。 定义l对于本文研究的问题，对于给定的输入常数曰，如果某算法A L G 能够输出一个结果，其运输 风险D a n g e r 测度是A L G 。，运输成本c o s t 测度是A L G c 。，并使得： A L G c a B 且A L G D 。g 。，卢O P T D 。s 。，o 其中。盯D a n 。，= m i n D a n g e r ( P ) l c o s t ( P ) B ，P P ( 5 ，) 是原始问题的最优解。 则称该算法是原始问题的一个( d ，卢) 近似算法。 显然，a l ，p l ，并且当仅= l 时，我们得到常规定义的卢近似算法。 我们设计的基于运输风险和费用约束的有害危险废弃物处理网络的算法如下，首先我们注意到对于 一个单目标的处理网络选线问题，问题非常简单，就是一个求最短路的问题，对于该问题，可以在多项式时 间内得到解决。我们下面构造的算法中要用到该算法。 定义2 对任意的针对运输网络C 上关于边定义的某个非负实函数，求最短路的算法记为 A L G ( G 。 注意到对任意的单目标的求一个网络图上的最短路问题，该算法能在多项式时间内得到最优解( 例 如，D i j k s t r a 算法) 。因此，A L G ( G 是一个多项式时间算法。在下面的叙述中，有时为了叙述方便，我们 同样用A L G ( c 表示在网络图C 上关于边上的非负实函数厂求最短路问题的得到的算法输出。 定义3 对任意的针对运输网络G 关于边上的两个非负实函数，和g ，以及两个正常数口和6 ，矿+ 略 表示对同样的网络G ，其每一条边上的权重函数被定义为盯+ 6 9 得到的图。 定义4 对任意的髫 O ，以及针对运输网络G 上关于边的两个非负实函数，和g ，记 ( 髫) 表示算法 A L G ( G ，苦+ g ) 得到的最短路的权重。 D 本文设计的针对运输风险与运输成本的有害危险废弃物运输选线策略算法如下，在后面我们将分析 其近似性能。 查墨堡堕堕童望堡堕塑笙垄堡垡丝旦望堡型塑垄堡箜鲨一 s t e pl ：设K 表示在图G 上在c o s t 8 的约束下的任意的路径的相应的D a n g e r 函数一个上界。 S t e p2 ：在区间 O ，K 】做二分搜索，寻找一个D ，使得下列两个条件成立：( a ) 针对图c ，定义另一个赋权图为：图C 不变，边上的权重为 告c l + D a n g e r 算法A L G ( c 告c t + D a “g c f ) 产生一个最短路，使得丛导 2 且( b ) 针对圈G ，定义另一个赋权图为：图G 不变边上 的权重为旦 c 。e t + D a n g e r ，算法A L G ( c 。旦笋c 。s t + D a n g e r ) 产生一个最短路，使得垒；! 2 。 s t e p 3 ：如果在上述二分搜索中，算法不能寻找到一个有效的D ，则输出“问题无解”否则输出第2 步中得到的针对图c ，权重为旦乒 C 0 8 t + D a n g e r 的赋权图得到的最短路，算法停止。 下面我们分析算法的运行效果，首先我们注意到如下的事实。 F a c t5 算法中第2 步所用到的二分搜索是可以进行的。 证明 因为V 茗 O ，有二A L G ( G = A L G ( G ，土) ，因此 等竽= A L G ( G ，舌c o s t + D a n g e r ) = A L G ( G ，古c 。s t + D a n g e r ) 因此，函数坠型是一个关于菇 o 的单调非增函数。因此算法中第2 步所用到的二分搜索是可以进行的。 定理1算法是一个多项式时间算法。 证明 该算法的时间依赖于l o g K ，这是一个多项式时间算法，同时算法中所调用的算法A L G 是一个 多项式时间算法，因此，这里设计的算法是一个多项式时间算法。定理证毕。 定理2如果图G 至少有一个可行解，则设计的算法输出一条路径P ，使得C o s t ( P ) 2 日，D a n g e r ( P ) 2 D P r D 。；2 m i n D a n g e r ( P ) ：C o s t ( P ) Bf 。其中C o s t ( P ) 和D a n g e r 9 ( P ) 是算法输出的路径P 对应 的运输成本和运输风险的测度结果。即设计的算法是一个( 2 ，2 ) 近似算法。 证明 根据F a c t5 ，在算法中第2 步使用二分搜索是合理的。现假设路径集合P ( s ，t ) 至少包含一条 运输成本费用不大于口的条件下的路径，首先根据算法2 ( a ) ，我们得到D + 1 0 P T 。 根据2 ( b ) ，我们得到 万方数据 1 3 8运 筹与管理 2 0 1 0 年第1 9 卷 D a n g e r ( P ) 矗( D + 1 ) 2 ( D + 1 ) 2 0 P T 川c o s t ( 尸) 者 ( D + 1 ) 舟( D + 1 ) 2 B 即我们算法得到的解是一个( 2 ，2 ) 一近似算法。定理证明完毕。 4 结束语 在有害危险废弃物品的后勤学研究中，对运输线路的优化选择的研究具有非常重要的地位。本文根 据实际情况，研究了针对有害危险废弃处理网络的选线问题。论文首先经过分析发现，实际的关于有害危 险废弃物运输管理中，危险品道路运输路径优化是政府监管部门与危险品生产经营单位之间风险与成本 的两难决策。运输企业侧重最低运输成本路径，政府监管部门多通过法规禁止某些路段通行，侧重最小运 输风险路径。在此基础上，我们建立了在风险约束和费用约束的条件下考虑有害危险废弃物处理网络选 线优化模型，目标是对给定的运输网络图和两个关于运输风险和运输成本的权重函数，问题是寻找关于这 两个费用的最短路。对于上述的任意单个目标，都可以利用简单的算法( 例如D i j k s t r a 算法等) 在多项式 时间内得到最优解。同以往的研究不同的是，我们这里研究的是同时满足两个目标，并且这两个目标间并 没有数量关系，并且这两个因素目标间有可以互相抵触。考虑到在有害危险废弃物运输管理中，政府处于 主导地位，对风险的要求特别高，论文把模型建立成一个在运输费用不大于给定的容忍上界的条件下，寻 求最小化风险的问题。论文随后对该选线问题模型给出了相应的选线策略，证明了该选线算法是一个 ( 2 ，2 ) 一近似算法。论文所得结论不论对于实际的选线决策具有一定的理论指导意义，同时对已有的研 究结果具有较强的互补性。 参考文献： 【1 B m n d e a uML ，C h i uSS A no v e r v i e wo fr e p r e s e n t a t i v ep r o b l e m 8i n1 0 c a t i o n si nl o c a t i o nr e s e 8 r c h J M 明a g e m e n tS c i e n c e ， 1 9 8 9 ：3 5 6 4 5 - 6 7 4 2 c u r r e n IJ ，D a s k i nM ，s c h