带约束条件的K最短路问题

• 作者: 石宁 贾迎琳
• 来源期刊: 中大管理研究
• 学科: 教育
• 关键词: 物流 网络 运筹学 路径规划
• 年，卷（期）: 2009,（1）
• 页码范围: 34-56
• 页数: 23页
• 分类号: G633.7

摘要

在本文中，我们研究了一个生成K条满足一组约束条件的最短路问题。为了求解此问题，我们设计了一个结构化分支策略，将此问题划分为最多必｜N｜个子问题，这里｜N｜表示网络中的结点数。每个子问题通过一个网络修正步骤均可转化为一个带约束的最短路问题（constraint shortest path problem，CSP）。当这些约束条件满足所谓的可分性质时，子问题便可得到进一步简化。基于这个结构化分支策略，我们针对一个需要考虑资源和无回路约束的应用问题设计了一个专门的算法。数据实验表明，我们的算法十分有效而稳定。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	石宁	中山大学管理学院	8	72	4.0	8.0
2	贾迎琳	中山大学管理学院	2	0	0.0	0.0