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

-- -- 关于不确定条件下的最短路径问题的研究 摘要：在利用最短路模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的权值经常很难给出确切的值。 对传统的最短路径优化模型提出了挑战， 也为最短路径优化模型的进一步发展提供了新的机遇。本文主要就不确定条件下最短路径问题进行研究， 介绍了一种不确定条件下最短路径问题随机优化模型――有约束的期望最

短路径模型，利用结合随机模拟方法和遗传算法的混合智能算法进行 求解。通过系统的学习不确定条件下的最短路径问题的解决方法， 开拓了思路，对自己运用系统思维解决自己研究方向的问题有很大的启

发。 关键字：网络优化；不确定最短路径问题；系统思维 一、引言 最短路径问题是指在网络中寻找节点间具有最小长度 ( 或最小费

用 ) 的路径，具有重要的理论和实际应用意义。一方面，它可以直接应用于许多实际问题，如各种管道的铺设，线路安排等 ; 另一方面，它也常被利用为解决其他一些优化问题的工具， 是网络优化中的一个基本而又重要的问题。 因此运筹界、 工业界的学者对最短路径及其变形问题就算法和应用等方面进行了广泛的研究。

然而在很多具体的应用中， 我们遇到的信息， 存在着客观的或者人为的不确定性， 这种不确定性的表现形式是多种多样的， 例如随机性、模糊性等。在利用最短路径模型解决问题时，由于天气、运输条件以及时间段等原因， 网络中弧的权值经常很难给出确切的估计， 这 --

-- 样只能根据历史数据获得其概率分布情况， 即这些数据是随机的。 但是随机性只是不确定性的一个方面， 对于一些情况， 譬如缺少历史数据、或者历史数据不可靠时， 这些数据只能由专家根据自己的经验给出主观的估计， 譬如通过该条路径的时间大概是 3 小时，流经该线路需时 40 分钟左右，这样表征弧上权值的量也因此而模糊起来，此时利用最短路径模型解决实际问题必须考虑这种不确定性。

虽然对于不确定条件下的最短路径问题， 学者们可通过研究动态随机网络中路径的分布函数以及期望值来研究网络问题， 给出了分布函数为某一类型的求解方法， 并没有考虑不同的决策要求， 或者是分布函数为一般情况时的求解方法。至于模糊最短路径问题，最早由 Dubois 和 Prade[1 ，2] 在 1980 年首次提出，他们根据模糊集理论中的最 大、最小值算子和 Zadeh扩展原理，来求模糊最短路的长度，但由于 模糊运算的特点，经过多次运算得到的模糊长度有时候并不能和某条 路径对应上。有的学者根据多准则决策理论求非被支配解路径集合， 但当网络较大时， 该集合就会很大， 对于决策者从中选择满意的方案 就会很困难。因此，在不确定条件下建立模型给出算法，为决策者提 供有价值的方案，具有重要的意义。 二、问题描述 为了对最短路问题进行建模， 本文考虑无圈有向网络图， 将网络 的拓扑结构用图论术语可以描述如下 : 在有向图 G=(V,A,W)中,V={l, 2, ..., n} 代表节点集 ( 设节点总数共计 n 个),A 代表弧集 , 每个弧使

用节点的有序对 i, j 来表示，其中 i , j A ，并假设从节点 i 到节点

j -- -- 之间只有一条有向弧。 W {Wij | i , j A} 代表弧的权集。 这里我们考虑 和每条弧关联着两个权值（也可以关联着多个 ) ，对图 G中的每一条

边 e i , j ，相应的权向量 Wij (Wij1 ,Wij2 ) 。在实际问题中分量有相应的物理量对应，如 Qos路由问题中每条链路可以给出带宽、 时延、代价，

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

有约束的最短路问题就是对于给定的约束 C，要在所有从 1 到 n 的所 有路径中，求一条路径使得 ij 最小且 cij C ，设决策变量为 xij ， (i, j) P (i, j) P

用下面的方法来表示一条路径 x { xij | i, j E} -- -- 其中 xij 1 表示弧 i , j 包含在该路径中， xij 0 表示弧 i, j 不包含在该 路径中，容易证明在有向无圈图中 x { xij | i , j A} 是一条从节点 1 到 节点 n 的路，当且仅当 1 i 1 xij x ji

0 2 i n 1

(i, j) E ( j ,i ) E 1 i n

记 { ij | i , j A} ，那么路 x 长度（目标函数）就可以写成为 f ( x, ) ij xij (i, j) E

优化的目标是使 f ( x, ) 最小。如果 ij 为确定的数，则求 f (x, ) 的最小

值是有定义的，但 i

j

是随机变量时，导致目标函数 f ( x, ) 也为随机变

量，这样求 f ( x, ) 的最小值也就失去了意义。因此，我们有必要根据 随机理论知识， 对随机条件下的最短路径进行定义， 建立相关的数学 模型。 三、有约束的期望最短路径模型的建立 定义 1：设 x, x 为图 G中从源节点 1 到目标节点 n 的不同路径，若有 E ( f ( x, ) ) E (f (x , , )则 称期望条 件下路 x 比路 x 短，其 中

E( f ( x, )称)为 x的期望路长。 在实际应用中境下的期望值模型决策者根据路径长度的期望值 来做决策，则考虑不确定环期望值模型是指在期望约束下， 使目标函 数的期望值达到最优。 为了寻找期望的最短路径， 建立了最短路径的 期望值模型。 min E[ f (x, )] E( ij xij ) （3.1 ） (i, j) E -- -- St cij

xij C （3.2 ）

(i, j) P --

-- 1 i 1 xij

xji0 2 i n 1 （3.3 ）

(i, j) E ( j ,i ) E i n 1

xij {0,1}

其中 , 式 (3.1) 为优化目标，即路的期望权值最小，亦即期望最短路

;

式 (3.2) 为约束条件，表示路权的第二分量不超过 C; 式 (3.3) 保证

x { xij | i , j E} 为有向图中节点 1 到节点 n 的一条路。 四、有约束的期望最短路径模型的求解 通常情况下，不确定规划模型由于包含有不确定函数而变得很难 用传统的方法来求解。 我们这里介绍一种结合随机模拟方法和遗传算 法的混合智能算法来求解以上建立的模型。 4.1 计算不确定函数的随机模拟方法

对于随机不确定优化模型， 将其转化为等价的确定性优化模型是非常困难的 . 只有在一些特殊情况下才能做到，对一些较复杂的问题通常很难做到这一点。 为了在起点 1 与终点 n 之间的众多路径中搜索出满足约束条件的最优路径， 我们采用随机模拟方法来计算最短路问题中的不确定函数 . 随机模拟 ( 也称 Monte Carlo 模拟 ) 是随机系统建模中刻画抽样试验的一门技术 , 它主要依据概率分布对随机变量进行抽样。虽然模拟技术只给出统计估计而非精确结果 , 且应用其研究问题需花费大量的计算时间 , 但对那些无法得到解析结果的复杂问题来

说 , 这种手段可能是惟一的有效的工具。随机模拟的基本思想是根据问题建立一个概率模型， 通过某种用数字进行的假象试验得到抽样值，然后进行统计处理， 将结果作为问题的解。 随机模拟处理问题的基本 --

-- 步骤是 : ①构造概率统计模型 ; ②定义随机变量 ; ③通过模拟获得子 样 ; ④统计计算。随机模拟主要依据分布函数或经验分布对随机变量进行抽样，它的理论基础是大数定理。 下面介绍计算最短路径中不确

定函数的随机模拟步骤： 模拟不确定函数 : U1 : x E[ f (x, )] 首先根据随机向量 各分量的分布函数从样本空间产生样本 k , k 1, 2,...,N ，由强大数定律可知，当 n 时

N f (x, k ) k 1 E[ f ( x, )]

N N 因此只要 N充分大，( f (x, k )) N 就可以用来作为 E[ f ( x, )] 的估计值。 k 1

这样设计求 E[ f ( x, )] 的随机模拟方法如下： 步骤 1. 设 L＝0 步骤 2. 根据各条弧上的随机变量的分布函数产生样本 ( 1 , 2 ,..., m ) 步骤 3. L L f( x, ) 步骤 4. 重复步骤 2 和 3 共 N次 步骤 5. E[ f ( x, )] L/ N 4.2 遗传算法 遗传算法是一种通过模拟自然进化过程搜索最优解的方法。 在解 决复杂的全局优化问题方面， 过去 30 年中 , 遗传算法在解决复杂的全 局优化问题方面得到了成功的应用 , 并受到了人们的广泛关注。在优 化问题中，如果目标函数是多峰的，或者搜索空间不规则，很容易在