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

关于不确定条件下的最短路径问题的研究 摘 要：在利用最短路模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的权值经常很难给出确切的值。对传统的最短路径优化模型提出了挑战，也为最短路径优化模型的进一步发展提供了新的机遇。本文主要就不确定条件下最短路径问题进行研究，介绍了一种不确定条件下最短路径问题随机优化模型――有约束的期望最短路径模型，利用结合随机模拟方法和遗传算法的混合智能算法进行求解。通过系统的学习不确定条件下的最短路径问题的解决方法，开拓了思路，对自己运用系统思维解决自己研究方向的问题有很大的启发。 关键字：网络优化；不确定最短路径问题；系统思维 一、引言 最短路径问题是指在网络中寻找节点间具有最小长度(或最小费用)的路径，具有重要的理论和实际应用意义。一方面，它可以直接应用于许多实际问题，如各种管道的铺设，线路安排等;另一方面，它也常被利用为解决其他一些优化问题的工具，是网络优化中的一个基本而又重要的问题。因此运筹界、工业界的学者对最短路径及其变形问题就算法和应用等方面进行了广泛的研究。 然而在很多具体的应用中，我们遇到的信息，存在着客观的或者人为的不确定性，这种不确定性的表现形式是多种多样的，例如随机性、模糊性等。在利用最短路径模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的权值经常很难给出确切的估计，这样只能根据历史数据获得其概率分布情况，即这些数据是随机的。但是随机性只是不确定性的一个方面，对于一些情况，譬如缺少历史数据、或者历史数据不可靠时，这些数据只能由专家根据自己的经验给出主观的估计，譬如通过该条路径的时间大概是3小时，流经该线路需时40分钟左右，这样表征弧上权值的量也因此而模糊起来，此时利用最短路径模型解决实际问题必须考虑这种不确定性。 虽然对于不确定条件下的最短路径问题，学者们可通过研究动态随机网络中路径的分布函数以及期望值来研究网络问题，给出了分布函数为某一类型的求解方法，并没有考虑不同的决策要求，或者是分布函数为一般情况时的求解方法。至于模糊最短路径问题，最早由Dubois和Prade[1，2]在1980年首次提出，他们根据模糊集理论中的最大、最小值算子和Zadeh扩展原理，来求模糊最短路的长度，但由于模糊运算的特点，经过多次运算得到的模糊长度有时候并不能和某条路径对应上。有的学者根据多准则决策理论求非被支配解路径集合，但当网络较大时，该集合就会很大，对于决策者从中选择满意的方案就会很困难。因此，在不确定条件下建立模型给出算法，为决策者提供有价值的方案，具有重要的意义。 二、问题描述 为了对最短路问题进行建模，本文考虑无圈有向网络图，将网络的拓扑结构用图论术语可以描述如下:在有向图G=(V,A,W)中,V={l, 2, ..., n}代表节点集(设节点总数共计n个),A代表弧集,每个弧使用节点的有序对来表示，其中，并假设从节点i到节点j之间只有一条有向弧。代表弧的权集。这里我们考虑和每条弧关联着两个权值（也可以关联着多个)，对图G中的每一条边，相应的权向量。在实际问题中分量有相应的物理量对应，如Qos路由问题中每条链路可以给出带宽、时延、代价，丢包率等，交通问题中每条弧对应着运行的时间和费用等。在实际应用中，由于各种原因，权向量的每个分量并不是确定的，可能部分不确定或都不确定。 我们令权向量,分量为随机变量,勺为确定的量。实际上这样的网络是存在的，如交通网络中两地的运输费用是确定的但运行时间可能不确定;网络路由中的丢包率是随机的但是其他的量可能是确定的。在有些情况下，随机变量可能服从某种分布函数，可以为正态分布、均匀分布等等。如当服从正态分布时，可以记为;在另外一些情况下，随机变量可能无法获得它的准确分布函数，只能根据先前经验获得或估计其概率。由于在无圈网络 G＝（V，A）中，对于所有的，所有的节点能够重新编号使得ij,这样我令1和n分别表示路径的起点和终点，则从节点1到n的一条路P的权向量定义为P中所有边的权向量之和，记为 有约束的最短路问题就是对于给定的约束C，要在所有从1到n的所有路径中，求一条路径使得最小且，设决策变量为，用下面的方法来表示一条路径 其中表示弧包含在该路径中，表示弧不包含在该路径中，容易证明在有向无圈图中是一条从节点1到节点n的路，当且仅当 记，那么路长度（目标函数）就可以写成为 优化的目标是使最小。如果为确定的数，则求的最小值是有定义的，但是随机变量时，导致目标函数也为随机变量，这样求的最小值也就失去了意义。因此，我们有必要根据随机理论知识，对随机条件下的最短路径进行定义，建立相关的数学模型。 三、有约束的期望最短路径模型的建立 定义1：设为图G中从源节点1到目标节点n的不同路径，若有,则称期望条件下路比路短，其中称为的期望路长。 在实际应用中境下