# [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] 点击复制 点、边带约束成本的最短路问题及其算法() 分享到： var jiathis_config = { data_track_clickback: true };

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

Author(s):
Institute of Communications Engineering, PLA University of Science and Technology, Nanjing 210007, China

Keywords:

TP393.01
DOI:
10.3969/j.issn.1001-0505.2003.01.028

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.