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

《有害危险废弃物运输网络优化选线模型研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、136运筹与管理20lO年第19卷险和运输成本的优化选线问题模型。在以往的研究中，对于如上的风险考虑的不多，或者即使考虑了，但是没有针对问题本身从问题复杂性和算法的角度出发考虑该问题。本文将在如上分析的条件下，考虑有害危险废弃物运输优化选线问题中涉及的两类因素：选择该边所需要承担的风险，以及选择该边所需要承担的成本。论文将建立相应的选线问题，并构造出相应的选线优化策略，最后证明得到的选线性能结果。2问题的建模与分析首先，由于本文研究的重点是对选线算法策略的设计和策略性能的研究上，因此，我们假设，在选线问题进行研究之前，所给运

2、输网络图上的各条边上所具有的风险都已经经过检测后全部知道。即认为在优化选线决策之前，给定的运输网络图上的待选线的边所具有的风险的数值已经全部已知的条件下进行的优化选址和选线的问题。同样的，我们也假设，在选线问题进行研究之前。所给运输网络图上的各条边上的运输成本都已经经过检测后全部知道。即认为在优化选线决策之前，给定的运输网络图上的待选线的边所具有的运输成本的数值已经全部已知的条件下进行的优化选址和选线的问题。同时我们假设，任意两条边上的运输风险与运输成本是其相应边上的相应运输风险与运输成本之和，即可以直接相加。在此基础上，我

3、们进行相应的理论建模与求解算法分析。根据实际问题，定义有害危险废弃物品道路运输网为一个无向网络图G=(y，E)，其中顶点集合y=㈠，tJ：，⋯，口。}表示一系列节点，边集合E={e=(q，移∥f，．『E{l，2，⋯，n}，i≠．『}表示运输路径的边。定义边上带有两个不同的非负权重，记为cost：E一尺+表示通过两点问的边所需要花费的费用，以及Danger：E一只+表示通过两点间的边所需要承担的风险。这两个权重函数只假设具有非负性。需要注意的是，这里并不需要假设这两个权重函数满足三角不等式。我们考虑更为一般的问题，即上述假设中

4、的无向网络图G=(y，E)中的两个权重函数不考虑是否具有一定的关系。本文所要研究的问题是：对给定的图G=(1，，E)，和两个关于边的权重函数，cost，Danger，对图上给定的两个起迄点对s和t，问题是希望能够寻找到关于这两个费用都能达到最小的连接s和f的最短路。以往关于最短路的相关研究已经有很多，对于上述的任意一个目标，都可以利用简单的算法(例如Dijl【stra算法等)在多项式时间内得到最优解。同以往的研究不同的是，我们这里研究的是同时满足两个目标，并且这两个目标间并没有数量关系。同时，考虑到这两个因素目标有可以相抵触

5、，即在一个因素下达到最优的最短路可能在另一个因素下的路径测度非常差。在以往的研究中是将这个问题处理成一个多目标规划的问题，从而在获得目标的权重或是决策者的偏好的条件下，将其转化成一个单目标优化问题求解。这类方法的缺陷在于：(1)权重或偏好不易获得；(2)多个目标之间的量纲不一致，不便于处理。如有的目标可能是成本，有的目标是效用。(3)即使通过变权法，将多个目标集成起来还是无法找到不是在凸包边界上的解。本文将把上述问题考虑成将一个因素作为约束条件，考虑另一个因素最小化的问题，并从问题本身直接进行分析和选线策略设计，并证明得到的

6、算法的近似性能。考虑到在有害危险废弃物运输管理中，政府具有主导的地位，对风险的要求特别高，我们考虑将之放到目标函数中。随后我们将考虑直接对这个问题本身进行分析，设计出有效的选线策略算法，并证明算法所具有的良好的性能。本文研究的问题的规范形式如下：对给定的图G=(y，E)，和两个关于边的权重函数，Cost，Danger，为了分析方便，不妨假设这两个权重函数都是正整数。设P(s．t)表示图G=(y，E)上所有的从s和t的路径的集合，对于VP∈尸(s，t)，定义P上的权重为路径上各边相应权重之和，即cost(P)=芝：cost(e

7、)，Danger(P)=>：Danger(e)而石问题是对任意给定的常数B，寻找如下最小化问题的最优解：minDanger(P)文tCost(P)≤曰P∈P(s，t)3有害废弃物运输网络选线优化模型的算法设计我们这里首先拓展近似算法的定义。以外的近似算法都是针对单目标优化问题，这里我们考虑将其第6期代文强：有害危险废弃物运输网络优化选线模型研究137拓展到有一个约束条件下的优化问题。定义l对于本文研究的问题，对于给定的输入常数曰，如果某算法ALG能够输出一个结果，其运输风险Danger测度是ALG‰。，运输成本cost测度是

8、ALGc¨。，并使得：ALGc㈣≤aB且ALGD。。g。，≤卢OPTD．。s。，o其中。盯Dan。，=min{Danger(P)lcost(P)≤B，P∈P(5，￡)}是原始问题的最优解。则称该算法是原始问题的一个(d，卢)近似算法。显然，a≥l，p≥l，并且当仅=l时，我们得到常规定义的