关于不确定条件下的最短路径问题的研究

《关于不确定条件下的最短路径问题的研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、--关于不确定条件下的最短路径问题的研究摘要：在利用最短路模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的权值经常很难给出确切的值。对传统的最短路径优化模型提出了挑战，也为最短路径优化模型的进一步发展提供了新的机遇。本文主要就不确定条件下最短路径问题进行研究，介绍了一种不确定条件下最短路径问题随机优化模型――有约束的期望最短路径模型，利用结合随机模拟方法和遗传算法的混合智能算法进行求解。通过系统的学习不确定条件下的最短路径问题的解决方法，开拓了思路，对自己运用系统思维解决自己研究方向的问题有很大的启发。关键字：网络优化；不确定最短路径问题；

2、系统思维一、引言最短路径问题是指在网络中寻找节点间具有最小长度(或最小费用)的路径，具有重要的理论和实际应用意义。一方面，它可以直接应用于许多实际问题，如各种管道的铺设，线路安排等;另一方面，它也常被利用为解决其他一些优化问题的工具，是网络优化中的一个基本而又重要的问题。因此运筹界、工业界的学者对最短路径及其变形问题就算法和应用等方面进行了广泛的研究。然而在很多具体的应用中，我们遇到的信息，存在着客观的或者人为的不确定性，这种不确定性的表现形式是多种多样的，例如随机性、模糊性等。在利用最短路径模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的

3、权值经常很难给出确切的估计，这----样只能根据历史数据获得其概率分布情况，即这些数据是随机的。但是随机性只是不确定性的一个方面，对于一些情况，譬如缺少历史数据、或者历史数据不可靠时，这些数据只能由专家根据自己的经验给出主观的估计，譬如通过该条路径的时间大概是3小时，流经该线路需时40分钟左右，这样表征弧上权值的量也因此而模糊起来，此时利用最短路径模型解决实际问题必须考虑这种不确定性。虽然对于不确定条件下的最短路径问题，学者们可通过研究动态随机网络中路径的分布函数以及期望值来研究网络问题，给出了分布函数为某一类型的求解方法，并没有考虑不同的决策要求，或者

4、是分布函数为一般情况时的求解方法。至于模糊最短路径问题，最早由Dubois和Prade[1，2]在1980年首次提出，他们根据模糊集理论中的最大、最小值算子和Zadeh扩展原理，来求模糊最短路的长度，但由于模糊运算的特点，经过多次运算得到的模糊长度有时候并不能和某条路径对应上。有的学者根据多准则决策理论求非被支配解路径集合，但当网络较大时，该集合就会很大，对于决策者从中选择满意的方案就会很困难。因此，在不确定条件下建立模型给出算法，为决策者提供有价值的方案，具有重要的意义。二、问题描述为了对最短路问题进行建模，本文考虑无圈有向网络图，将网络的拓扑结构用图

5、论术语可以描述如下:在有向图G=(V,A,W)中,V={l,----2,...,n}代表节点集(设节点总数共计n个),A代表弧集,每个弧使----用节点的有序对i,j来表示，其中i,jA，并假设从节点i到节点j----之间只有一条有向弧。W{Wij

6、i,jA}代表弧的权集。这里我们考虑和每条弧关联着两个权值（也可以关联着多个)，对图G中的每一条边ei,j，相应的权向量Wij(Wij1,Wij2)。在实际问题中分量有相应的物理量对应，如Qos路由问题中每条链路可以给出带宽、时延、代价，丢包率等，交通问题中每条弧对应着运行的时间和费用

7、等。在实际应用中，由于各种原因，权向量Wij的每个分量并不是确定的，可能部分不确定或都不确定。我们令权向量Wij(ij,cij),分量ij为随机变量,cij勺为确定的量。实际上这样的网络是存在的，如交通网络中两地的运输费用是确定的但运行时间可能不确定;网络路由中的丢包率是随机的但是其他的量可能是确定的。在有些情况下，随机变量ij可能服从某种分布函数，可以为正态分布、均匀分布等等。如当服从正态分布时，可以记为ij~N(ij,ij2);在另外一些情况下，随机变量ij可能无法获得它的准确分布函数，只能根据先前经验获得或估计其概率。由于在无圈网络G＝（V，A）中

8、，对于所有的i,jA，所有的节点能够重新编号使得i

9、i,jE}----其中xij1表示弧i,j包含在该路径中，xij0表示弧i,j不包含在该路径中，容易证明在有向无圈图中x{xij

10、i,jA

11、}是一条从节点1到节点n的路，当且仅当1i1xijxji02in1(i,j)E(