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

摘要：

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

关键词：最短路问题、点、边带约束成本、拉格朗日松弛算法、次梯度算法

所属期刊栏目：33

分类号：TP393.01(计算技术、计算机技术)

资助基金：国防科技重点实验室基金00JS04.4.1.JB3801

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：111-114