# [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] 点击复制 一种基于多条件约束的路由优化启发式算法() 分享到： var jiathis_config = { data_track_clickback: true };

33

2003年第3期

275-279

2003-05-20

## 文章信息/Info

Title:
Heuristic algorithm for optimizing routing with multiple constraints

1 1 解放军理工大学通信工程学院,南京 210007; 2 2 解放军理工大学理学院, 南京 211101
Author(s):
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:

TP393
DOI:
10.3969/j.issn.1001-0505.2003.03.007

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.