时变网络有向中国邮路问题的割平面算法研究

发布时间：2021-10-29 15:01

　　中国邮路问题是著名的图论问题,也是组合优化、运筹规划领域经典的问题之一在通信系统、交通管理、机器人探测、交互式系统分析、网站可用性和软件测试等领域有着重要的应用。然而,随着通信技术与分布式系统的发展,混合系统测试和智能交通等复杂领域的应用都在关注实际问题中的时间特性,即网络中弧的权值依赖于时间变化而变化,我们称具有这种性质的网络为时变网络。在以往中国邮路问题的研究中,都是假设网络中的权值是静态的、确定的,而实际问题中网络往往是动态的,比如现实交通网络中,交通事故和天气变化等偶然事件都有可能造成道路交通状况的变化,那么邮递员送信沿途所经过街道的旅行时间也会随之变化。中国邮路问题的传统模型和算法只能求解固定弧权条件下的问题,在时变网络中应用传统算法求得的解根本不符合实际情况的要求。因此,研究时变网络中国邮路问题的模型和优化算法具有更为重要的现实意义。然而,引入时间因素后新问题的求解变得非常困难,时变网络有向中国邮路问题已被证明是NP难的,直接求解最优解往往是不实际的。本文从数学规划优化方法的角度出发研究时变网络有向中国邮路问题,首先借鉴时变网络旅行商问题的建模思想结合圈覆盖相关理论建立了时... 

【文章来源】：大连理工大学辽宁省 211工程院校 985工程院校 教育部直属院校

【文章页数】：62 页

【学位级别】：硕士

【部分图文】：

弧路由转换算法示例

的最优解不符合整数要求，假设是分量气一b不符合要求，其中b取分数。那么，分支限界法则会将问题分为两部分，增加两个约束条件xi‘[bl和xi、[bl+1，分别将不等式并入上级松弛问题中，如图2.3所示，从而形成两个分支。两个分支问题的可行域中包含原整数规划问题的所有可行解，图2.3中灰色阴影部分被去掉了，因为它们不会包含任何整数规划的可行解。依此类推，根据需要，分支问题也可以产生自己的分支问题，如此

直到获得整数最优解。而对于割平面算法，此时会根据分数分量xi一b产生一个新的约束(通常称为割平面约束)，并将其添加到线性松弛问题中继续求解，再次求解后若还遇到分数变量，则继续添加割平面约束，如图2.4所示直到找到最优整数解。占图 2.3右十1丫分支限界算法示意图 Fig.2.3AsimPlediagramofbranehandboundalgorithm毛图2.4割平面算法示意图 Fig.2.4AsimPlediagramofcuttingPlanealgorithm分支限界法其实是一种隐枚举法或者部分枚举法，它不是一种有效算法，只是枚举法基础上的改进。整数规划问题一般有无限多个可行解，随着问题规模的扩大，其可行解的数目也将急剧增加。因此，即使通过添加良好的剪枝条件使其枚举部分可行解，也

【参考文献】：
期刊论文
[1]动态网络最短路问题的复杂性与近似算法[J]. 林澜,闫春钢,蒋昌俊,周向东.  计算机学报. 2007(04)
[2]时间依赖的网络中最小时间路径算法[J]. 谭国真,高文.  计算机学报. 2002(02)
[3]中国投递员问题综述[J]. 管梅谷.  数学研究与评论. 1984(01)

硕士论文
[1]时间依赖的无向中国邮路问题分支切割算法[D]. 武雪平.大连理工大学 2009
[2]时间依赖网络中国邮路问题的分支限界算法[D]. 吕凯.大连理工大学 2008
[3]时间依赖中国邮路问题的智能算法研究[D]. 闫超.大连理工大学 2008
[4]时间依赖网络中国邮路问题研究[D]. 金运通.大连理工大学 2006



本文编号：3464879