带均匀分布权值的最短路问题

Shortest Path Problem with Uniform Distribution Weights

最短路问题是网络设计中的一个基本问题,当前研究工作都基于边的权值是确定的这一假设。论文研究边的权值是一区间数时的最短路问题,利用优化理论,建立了目标函数系数在区间上均匀分布的模糊线性整数规划模型。通过引入正、负理想点概念,将模型转化为具有确定系数的单目标优化问题,给出了求解算法,并证明了算法的时间复杂性是多项式时间的。仿真实例说明了模型和算法的有效性。

The shortest path problem(SP) is a basic problem in network design,which is NP-complete.Most research works of SP are based on the supposition that the weights on edges are determinate numbers currently.The paper studies the SP with non-determinate weights on edges.A fuzzy linear integer-programming model(FIP) is established,which has a uniform distribution parameter in object function.Applying the positive and negative idea point,FIP can be transformed into a linear integer programming with a single determinate objective function.A new algorithm is presented and is proved to have a polynomial time complexity.The efficiency of the algorithm is demonstrated by simulating example.