多面体理论在时间依赖中国邮路问题中的应用

发布时间：2020-12-23 10:35

　　中国邮路问题问题是一类著名的弧路由问题,在信件投递、校车路线规划、软件测试等领域有着重要的应用。近年来,随着分布式处理、智能交通、物联网等技术的兴起,许多问题变得具有实时性,传统中国邮路问题的理论面临着前所未有的挑战。因此,我们有必要研究时间依赖的中国邮路问题来适应这些需求。然而,时间依赖的中国邮路问题的研究面临着以下一些难点。由于加入了时间因素,问题的求解变得很困难,即使是欧拉图上的时间依赖中国邮路问题也是NP-hard问题。而求解NP-hard问题的最优化算法中,基于多面体部分描述设计的方法是很效的算法。但是,时间依赖的点路由问题很难直接应用或修正传统问题的多面体结果,然而,更困难的是时间依赖的弧路由问题,国际上至今还没有其进行直接建模求解的研究,国内学者给出的方法大都存在求解规模不大、效率不高等局限性。本文的研究正是围绕上述问题展开的,主要包含以下三方面工作。首先,分析了圈向量和问题可行解的联系,依此建立了便于对时间依赖中国邮路问题进行多面体分析的数学规划模型,对其进行了线性化处理,然后分析了模型规模的上界,并给出了两个更有效的时间不等式用于加强模型。其次,由于模型不等式约束集中... 

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

【文章页数】：66 页

【学位级别】：硕士

【部分图文】：

TDCPP可行解不能写成圈排列的形式

图3.3时间依赖的旅行函数Fig.3.3Travelfunetionwithtime一dePendent

原始图

【参考文献】：
期刊论文
[1]时间窗-时间依赖中国邮路问题的图转换算法[J]. 陈加萍,孟宪超,孙景昊,谭国真.  计算机与数字工程. 2010(08)
[2]随机时间依赖网络的K期望最短路径[J]. 谭国真,柳亚玲,高文.  计算机学报. 2003(03)
[3]时间依赖的网络中最小时间路径算法[J]. 谭国真,高文.  计算机学报. 2002(02)
[4]奇偶点图上作业法[J]. 管梅谷.  数学学报. 1960(03)

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



本文编号：2933565