模糊随机最短路径问题模型与算法

Models and Algorithm for Fuzzy-ramdom Shortest Path Problem

最短路径问题在现实生活中有着广泛应用,许多专家学者对此问题进行了深入研究.到目前为止,所有这些研究都是针对静态最短路径问题以及不确定最短路径问题中具有模糊或随机参数的问题.然而在现实世界中,有些系统中有很多不确定因素,因此很有必要对具有多重不确定参数的最短路径问题进行研究.本文主要研究具有模糊随机参数的最短路径问题,基于机会测度理论,分别建立了模糊随机期望值模型、机会约束规划模型及相关机会约束规划模型,然后设计遗传算法求解.

The shortest path problem has been widely applied in real-life and has been extensively studied by many researchers. By far, all the studies are focused on the static shortest path problems and the shortest path problems with uncertain parameter such as fuzzy or random parameters. In the real life,however,a lot of parameters of some systems are uncertain. So it is very necessary to study the shortest path problem with multi-uncertain parameter. The main purpose of this thesis is to study the shortest path problem with fuzzy random variables. Based on the chance measure of fuzzy random variable, the shortest path problem is formulated as the expected value model, the chance-constrained programming and the dependent-chance programming respectively. Then a genetic algorithm is designed for solving the fuzzy random shortest path problem.