[1]齐东元,汪泽焱,邵军力.点、边带约束成本的最短路问题及其算法[J].东南大学学报(自然科学版),2003,33(1):111-114.[doi:10.3969/j.issn.1001-0505.2003.01.028]
 Qi Dongyuan,Wang Zeyan,Shao Junli.Shortest path problem with constraints of node’s and edge’s cost and its algorithm[J].Journal of Southeast University (Natural Science Edition),2003,33(1):111-114.[doi:10.3969/j.issn.1001-0505.2003.01.028]
点击复制

点、边带约束成本的最短路问题及其算法()
分享到:

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

卷:
33
期数:
2003年第1期
页码:
111-114
栏目:
计算机科学与工程
出版日期:
2003-01-20

文章信息/Info

Title:
Shortest path problem with constraints of node’s and edge’s cost and its algorithm
作者:
齐东元 汪泽焱 邵军力
解放军理工大学通信工程学院, 南京 210007
Author(s):
Qi Dongyuan Wang Zeyan Shao Junli
Institute of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China
关键词:
最短路问题 点、边带约束成本 拉格朗日松弛算法 次梯度算法
Keywords:
shortest path constraints of node’s cost and edge’s cost Lagrangean relaxation subgradient algorithm
分类号:
TP393.01
DOI:
10.3969/j.issn.1001-0505.2003.01.028
摘要:
提出了点和边都带有成本约束的最短路问题,证明了该问题是NP-完全的.建立了这类问题的数学规划模型,并采用拉格朗日松弛算法对模型进行求解,给出了次梯度优化求解算法的一般步骤.考虑到算法在实际求解过程中收敛速度较慢的问题,进一步对拉格朗日松弛算法进行了2个方面的改进,一方面确定适当的迭代步长,另一方面选择较好的迭代方向.算法实例表明,改进后的拉格朗日松弛算法迭代步数显著减少,证明算法是有效的.
Abstract:
The shortest path(SP)problem with constraints of node’s cost and edge’s cost is put forward, and it is proven to be NP-complete. A mathematics programming model of this modified SP is proposed. To solve this model Lagrangean relaxation algorithm is adopted. The general algorithm steps based on subgradient optimization mathematics method are presented. In view of the weak convergence performance in this algorithm, the Lagrangean relaxation algorithm is modified in two points, i.e. determining a proper step length and choosing a better iterative direction. Computational examples show that the modified subgradient optimization algorithm for Lagrangean relaxation can reduce the iterative steps obviously, and is proved to be efficient.

参考文献/References:

[1] Cai X.Time-varying shortest path problem with constraints[J]. Networks,1997,29(2):141-149.
[2] Loachim I.A dual programming algorithm for the shortest path problem[J].Networks,1998,31(2):193-204.
[3] Handier G.A dual algorithm for the constrained shortest path[J].Networks,1980,10(2):293-310.
[4] 李帮义,何勇,姚恩瑜.点带约束成本的最短路问题[J].高校应用数学学报A辑,2000,15(1):93-96.
  Li Bangyi,He Yong,Yao Enyu.Shortest path problem with constraints of node’s cost[J]. Applied Mathematics A Journal of Chinese Universities, 2000, 15(1):93-96.(in Chinese)
[5] Sara B,Allen G.Computer algorithms:introduction to design and analysis.3rd edition[M].Beijing:Higher Education Press,2002.403-411.
[6] Nemhauser G,Wolsey L.Integer and combinatorial optimization[M].New York:John Wiley & Sons,1988.155-269.
[7] Goffin J.On convergence rate of subgradient optimization methods[J].Mathematical Programming,1977,13(3):329-347.
[8] Kim S,Ahn H.Convergence properties of the modified subgradient method of Camerini,et al[J].Naval Research Logistics,1990,37(8):961-966.
[9] Kim S,Ahn H,Cho S.Variable target value subgradient method[J].Mathematical Programming,1991,49(3):359-469.
[10] Fumero F.A modified subgradient algorithm for Lagrangean relaxation[J].Computers & Operations Research, 2001,28(1):33-52.
[11] Ziegelmann M.Constrained shortest path and related problems[D].Saarbrücken:Max-Planck-Institute,2001.

备注/Memo

备注/Memo:
基金项目: 战术通信抗干扰技术国防科技重点实验室基金资助项目(00JS04.4.1.JB3801).
作者简介: 齐东元(1973—),男,博士生,讲师,qidy@vip.sina.com; 邵军力(联系人),男,教授,博士生导师.
更新日期/Last Update: 2003-01-20