点、边带约束成本的最短路问题及其算法

• 作者: 汪泽焱 邵军力 齐东元
• 来源期刊: 东南大学学报(自然科学版)
• 学科: 工学
• 关键词: 最短路问题 点、边带约束成本 拉格朗日松弛算法 次梯度算法
• 年，卷（期）: 2003,（1）
• 页码范围: 111-114
• 页数: 4页
• 分类号: TP393.01
• 字数: 2911字
• 语种: 中文
• DOI: 10.3321/j.issn:1001-0505.2003.01.028

摘要

提出了点和边都带有成本约束的最短路问题,证明了该问题是NP-完全的.建立了这类问题的数学规划模型,并采用拉格朗日松弛算法对模型进行求解,给出了次梯度优化求解算法的一般步骤.考虑到算法在实际求解过程中收敛速度较慢的问题,进一步对拉格朗日松弛算法进行了2个方面的改进,一方面确定适当的迭代步长,另一方面选择较好的迭代方向.算法实例表明,改进后的拉格朗日松弛算法迭代步数显著减少,证明算法是有效的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪泽焱	解放军理工大学通信工程学院	43	602	12.0	24.0
2	邵军力	解放军理工大学通信工程学院	13	158	7.0	12.0
3	齐东元	解放军理工大学通信工程学院	3	21	2.0	3.0