[1]周海刚,汪泽焱,肖军模.一种基于多条件约束的路由优化启发式算法[J].东南大学学报(自然科学版),2003,33(3):275-279.[doi:10.3969/j.issn.1001-0505.2003.03.007]
 Zhou Haigang,Wang Zeyan,Xiao Junmo.Heuristic algorithm for optimizing routing with multiple constraints[J].Journal of Southeast University (Natural Science Edition),2003,33(3):275-279.[doi:10.3969/j.issn.1001-0505.2003.03.007]
点击复制

一种基于多条件约束的路由优化启发式算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
33
期数:
2003年第3期
页码:
275-279
栏目:
计算机科学与工程
出版日期:
2003-05-20

文章信息/Info

Title:
Heuristic algorithm for optimizing routing with multiple constraints
作者:
周海刚1 汪泽焱2 肖军模1
1 1 解放军理工大学通信工程学院,南京 210007; 2 2 解放军理工大学理学院, 南京 211101
Author(s):
Zhou Haigang1 Wang Zeyan2 Xiao Junmo1
1 Institute of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China
2 Institute of Sciences, PLA University of Science and Technology, Nanjing 211101, China
关键词:
路由优化 交互式算法 启发式算法 多目标规划
Keywords:
optimizing routing interactive algorithm heuristic algorithm multi-object programming
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2003.03.007
摘要:
主要研究了2个问题:其一是在网络中寻找一条从源节点到目的节点的路径,该路径满足总长度不大于预设值且总耗费也不大于预设值; 其二是在满足总长度和总耗费均不超过各自预设值的条件下,寻找一条优化路径,使得决策者满意其总长度和总耗费.文中首先提出了一个交互式算法来求解后一个问题,该算法利用一个多目标整数规划模型来求解长度和耗费优化的路径.该算法引入目标参考点,在算法的每一次交互步骤中,让决策者通过调整目标参考点来寻找满意解,并压缩了目标搜索空间.然后提出了一个启发式算法来综合解决以上提出的问题,并在文中给出了该算法的完整描述.最后给出了一个仿真实例来验证文中提出的2个算法.
Abstract:
Two issues are studied. The first is to find a path from source point to destination point such that the total length and the total cost of the path are no more than the preset values. The second is to optimize the path and so to satisfy the decision-maker with the condition that the path’s total length and total cost are less than respective preset values. To solve the latter, an interactive algorithm after the problem is formulated by a multi-objective integer programming model is proposed, in which the length and cost of the path are optimized. A reference point of the objective value considered is introduced in the algorithm and it is generated in each iteration step to adapt to decision-maker’s information, which makes the solution space compressed. Then a heuristic algorithm is put forward to solve the two problems. The complete description of the algorithm is given. Finally an example demonstrates the effectiveness of two algorithms proposed.

参考文献/References:

[1] Bazaraa M S,Jarvis J J,Sherali H D. Linear programming and network flows[M].New York:Wiley,1990.483-492.
[2] Garey M R,Johnson D S.Computers and intractability,a guide to the theory of NP-completeness[M].San Francisco:Freeman,1979.52-68.
[3] Xiao Xipeng,Lionel M N.Internet QoS:a big picture[J].IEEE Network,1999,13(2):8-18.
[4] Jaffe J M.Algorithms for finding paths with multiple constraints [J].Networks,1984,14(1):95-116.
[5] Fandel G,Gal T.Multiple criteria decision making—theory and application[M].Berlin:Springer-Verlag,1980.30-62.
[6] Wang X M,Qin Z L,Hu Y D.An interactive algorithm for multicriteria decision making:the attainable reference point method [J]. IEEE Transactions on System, 2001,31(3):194-198.
[7] Nemhauser G L,Wolsey L A.Integer and combinatorial optimization[M].New York:John Wiley & Sons,1988.189-221.
[8] Pinsiger D.Algorithms for knapsack problems[D].Denmark:University of Copenhagen,1995.
[9] Trick M A.A dynamic programming approach for consistency and propagation for knapsack constraints [EB/OL].http://mat.gsia.cmu.edu/trick/knapsack.pdf.2001-5-28/2002-9-1.

备注/Memo

备注/Memo:
基金项目: 国家自然科学基金重点资助项目(69931040)、国防科技预研跨行业基金资助项目(00J6.4.2.JB3804).
作者简介: 周海刚(1974—),男,博士生,讲师,zhouhg@yahoo.com; 肖军模(联系人),男,教授,博士生导师.
更新日期/Last Update: 2003-05-20