带模糊权值的最短路问题及启发式算法

Shortest Path Problem with Fuzzy Weights and Heuristic Algorithm

研究网络链路权值是三角型模糊数时的最短路问题,建立模糊线性整数优化模型。通过引入目标函数的正、负理想点和隶属度概念,将模糊优化问题转化为确定系数的单目标优化问题,并给出求解算法。该算法通过调整反映决策者意图的目标函数权系数,得到决策者的满意解。对14个节点的实例网络进行仿真,经过6步就能得到令决策者满意的解,表明了模型和算法的有效性。

This paper studies the Shortest Path（SP） with fuzzy weights on edges.A Fuzzy linear Integer-Programming model（FIP） is established,which has triangular fuzzy numbers in object function.Applying the fuzzy membership functions and positive and negative ideal point of object function FIP can be transformed into a linear integer programming with a single determinate objective functions.A new algorithm is presented.If decision maker is not satisfied with the solution,the weights of objective function in the single objective programming can be modified until the satisfactory solution can be obtained.A satisfactory solution can be obtained after 6 steps by simulating the network with 14 nodes,which demonstrates the efficiency of the model and algorithm.