导读:本文包含了时间依赖中国邮路问题论文开题报告文献综述及选题提纲参考文献，主要关键词:时间依赖,中国邮路问题,模拟退火,遗传算法
时间依赖中国邮路问题论文文献综述
孙景昊,吴雄,谭国真,闫超[1]（2011）在《二层SA/GA算法解决时间依赖中国邮路问题》一文中研究指出中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。(本文来源于《计算机科学》期刊2011年05期）
谭国真,孙景昊,肖宏业,吕凯[2]（2011）在《时间依赖无向中国邮路问题的分支限界算法》一文中研究指出时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。(本文来源于《计算机科学》期刊2011年02期）
陈加萍[3]（2010）在《图转换方法求解带时间窗的时间依赖中国邮路问题》一文中研究指出近年来,随着信息技术的高速发展和以物联网为驱动的研究热潮的到来,人们对应用系统的实时性提出了更高的要求,越来越多的实际问题变得与时间因素有着密切的联系。带时变特性的问题是一个与实际应用结合紧密、发展前景广阔的研究领域,它能够提供一种对现实问题建模更精确的方法,显然成为一个值得去深入研究的非常具有挑战性的领域。本文研究的是时变网络上的带时间窗的中国邮路问题(TDCPPTW),该问题是传统中国邮路问题在动态时间属性方面的扩展。由于传统的静态网络的路由算法并未对网络的动态性给出有效的解决方案。因此,如何针对时间依赖网络的时间约束和实时性变化进行建模,并迅速、精确的对其进行优化求解是一类至关重要的问题。本文首先对带时间窗的时间依赖中国邮路问题的定义和特性进行了深入研究,并分析了时间依赖旅行时间和时间窗所引起的求解难度,发现传统的弧路由转换方法不再适用于时间依赖网络。然后,针对时间依赖网络提出一个新的图转换算法,把原始时间依赖网络离散为一个有着“弧集簇”结构的静态辅助图。进一步基于图转换后的静态辅助图,把原始时间依赖问题转换为静态图辅助图上的广义弧路由问题,并从理论上证明了转换前后问题的等价性。同时,为了克服转换后静态网络的规模严重增大的缺陷,设计出一个图缩减算法,且从理论上证明了该缩减算法的正确性和有效性。接着,建立求解广义弧路由问题的0-1混合整数规划模型,并分析其变量和约束的个数,发现当问题规模增大时模型的变量会变得相当庞大；因此,进一步将模型分割为主问题和子问题,以采用列生成算法来适应大规模实例的求解。最后,采用随机生成的方法构造大量TDCPPTW的测试实例,并应用本文所提出的转换算法和数学模型对其进行求解实验。实验结果并得充分肯定了本文所构造的图转换算法和求解模型的正确性和有效性。(本文来源于《大连理工大学》期刊2010-11-15）
孟亚坤[4]（2010）在《时间依赖网络中国邮路问题的列生成算法》一文中研究指出中国邮路问题是图论中的经典问题,得到了广泛的研究。该问题有着众多的应用领域,如邮件投递路线,扫雪车路线,警车出巡安排,机器人检测路线路线以及软、硬件系统的测试序列优化等等,因此吸引了众多学者的研究兴趣。近年来,由于计算机网络与通信、智能交通系统以及混合系统实时测试等复杂应用领域的需求,时变网络中国邮路问题的研究具有更为重要的现实应用意义。带时间窗的中国邮路问题、时间依赖服务代价中国邮路问题以及时间依赖旅行时间中国邮路问题均属于时变网络中国邮路问题。其中,前两个问题已经得到了较好的研究,但由于时间依赖旅行时间中国邮路问题建模十分困难,因此,一直鲜有研究。然而,本文将致力于时间依赖旅行时间中国邮路问题的研究。本文首先对传统的中国邮路问题和时变网络中国邮路问题的研究方法进行了归纳总结,并介绍了列生成算法的原理及其在时变网络中的应用。然后,通过将中国邮路可行解看成是图中圈的排列组合,设计了以基本圈为决策变量的整数线性规划模型,并从理论上证明了该模型中基本圈数的上界为m-n+1。由于该整数规划模型的规模比较大,因此,本文设计了列生成算法求解该问题。首先,将圈变量整数规划模型抽象为带偏序关系的集合覆盖主问题模型,降低了解空间的维数；然后,通过对偶理论设计了时间依赖最短路子问题,并应用遗传算法求解,从而进一步确定了最优解的搜索方向。但是,这个模型只能解决所有圈均过原点的特例,针对存在圈不过原点的网络拓扑,文章针对可行解的特点给出了另外一个“层路径”数学规划模型,同时对该模型的上界进行了理论分析,算例验证了该模型的正确性。(本文来源于《大连理工大学》期刊2010-11-13）
吴雄[5]（2010）在《多面体理论在时间依赖中国邮路问题中的应用》一文中研究指出中国邮路问题问题是一类着名的弧路由问题,在信件投递、校车路线规划、软件测试等领域有着重要的应用。近年来,随着分布式处理、智能交通、物联网等技术的兴起,许多问题变得具有实时性,传统中国邮路问题的理论面临着前所未有的挑战。因此,我们有必要研究时间依赖的中国邮路问题来适应这些需求。然而,时间依赖的中国邮路问题的研究面临着以下一些难点。由于加入了时间因素,问题的求解变得很困难,即使是欧拉图上的时间依赖中国邮路问题也是NP-hard问题。而求解NP-hard问题的最优化算法中,基于多面体部分描述设计的方法是很效的算法。但是,时间依赖的点路由问题很难直接应用或修正传统问题的多面体结果,然而,更困难的是时间依赖的弧路由问题,国际上至今还没有其进行直接建模求解的研究,国内学者给出的方法大都存在求解规模不大、效率不高等局限性。本文的研究正是围绕上述问题展开的,主要包含以下叁方面工作。首先,分析了圈向量和问题可行解的联系,依此建立了便于对时间依赖中国邮路问题进行多面体分析的数学规划模型,对其进行了线性化处理,然后分析了模型规模的上界,并给出了两个更有效的时间不等式用于加强模型。其次,由于模型不等式约束集中的一个子集具有很强的组合结构,本文定义这部分为确定回路遍历顺序(CVO)多面体。利用圈空间的性质分析了CVO多面体的面结构,构造了一个有效不等式并证明它是CVO多面体的极大面。最后,设计并实现了基于极大诱导不等式和更有效时间不等式等部分线性描述的割平面算法。实验结果表明,极大诱导不等式能够有效地缩小解空间,更有效的时间不能够加强时间不等式进而加强整数规划模型。(本文来源于《大连理工大学》期刊2010-10-30）
孙景昊,孟亚坤,谭国真[6]（2010）在《时间依赖网络中国邮路问题》一文中研究指出中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。(本文来源于《计算机工程与科学》期刊2010年10期）
陈加萍,孟宪超,孙景昊,谭国真[7]（2010）在《时间窗-时间依赖中国邮路问题的图转换算法》一文中研究指出研究时间依赖网络上带时间窗的中国邮路问题(TDCPPTW),该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势。首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题(GRPP);最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验。(本文来源于《计算机与数字工程》期刊2010年08期）
武雪平[8]（2009）在《时间依赖的无向中国邮路问题分支切割算法》一文中研究指出路由问题具有重要的理论意义和众多的实际应用,半个多世纪得到了国内外学者深入的研究。传统的路由问题通常被认为用于服务弧或点的代价是常量,属于静态的网络优化问题。然而现实情形中旅行时间或代价常随时间发生变化并非定值,所以单纯的将代价视为常量只是对现实的一个近似。由此进一步加入时间因素成为实际应用中更为迫切的要求,即在时间依赖网络中研究上述问题。对传统的路由问题及考虑时间因素的点路由问题,其研究均包括探讨问题的性质以建立其数学模型及设计求解算法,其中从建模到算法设计是基于数学规划理论得到精确解研究这类问题的一般框架。然而对时间依赖的弧路由问题,由于其建模、设计算法等的难度和复杂性,除了本实验室的相关工作外,至今尚无其他研究报道。由谭国真教授首次提出的时间依赖中国邮路问题是经典中国邮路问题的一般化,属于时间依赖的弧路由问题。本文对此问题在无向图情形下的研究也主要从建立其数学规划模型、设计精确求解算法两个方面着手。首先,给出了时间依赖的中国邮路问题统一定义及其分类,并分析了此类问题所呈现的一些重要特性及与传统的中国邮路问题的区别。如传统的两阶段求解方法将不再成立;建模时其时间依赖函数所呈现的情形等。其次,结合上述特性给出此问题在无向图情形下,即时间依赖无向中国邮路问题的两类整数规划模型。模型中均实现了一步求解的方法并考虑了各边被遍历的次序。在模型正确性证明之后,探讨如何给出其它各变形的数学模型。最后,给出了在无向图上获得问题上下界的策略,并给出问题度约束方面的有效及加强约束不等式及两类与时间因素有关的加强约束条件。算法设计上,本文结合当前最有效求解NP-hard或NP-complete问题的精确算法:分支切割算法,给出用于求解时间依赖无向中国邮路问题的两个精确算法,并分析给出其中度约束的两个启发式识别算法。文章最后给出的一些实例,验证了整数规划模型的正确性,以及有效及加强不等式对线性松弛的加强作用。(本文来源于《大连理工大学》期刊2009-10-30）
吕凯[9]（2008）在《时间依赖网络中国邮路问题的分支限界算法》一文中研究指出中国邮路问题是图论经典问题之一,在软件测试、邮件投递等诸多领域中都被广泛应用。时间依赖中国邮路问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中,比中国邮路问题更具优势,具有重要的应用和研究价值。本文介绍了在传统静态网络中,中国邮路问题(Chinese Postman Problem简记CPP)的分类、研究现状、以及应用领域;然后分析了传统中国邮路问题的局限和在时间依赖网络环境下的中国邮路问题相对于传统中国邮路问题的优势,以及时间依赖网络中中国邮路问题的研究现状和当前遇到的困难以及研究意义;为后面研究打下了基础。在这篇文章中,有以下内容:(1)给出传统方法并不适于时间依赖网络环境的根本原因:网络的时间依赖特性导致网络各个边权值的不固定。我们给出传统方法并不适用于时变网络(即时间依赖网络)条件的病态实例,以便对传统方法不适于时变网络环境的根本原因有更深地了解。(2)给出时间依赖中国邮路问题的特性和分支限界最优化方法。我们用定理和推论的形式给出适合求解时变无向、有向中国邮路问题的特性,并且对这些特性进行了证明,确保了它们的正确性,并以此为基础构造问题的剪枝条件,设计了相应的分支限界最优化方法;(3)对于FIFO的时间依赖网络增加了一些特殊性质,并提高了算法的效率。针对FIFO(first in first out)这一类特殊的时变网络,我们给出相应的特性以及基于此的FIFO剪枝条件,从而得到更高效的分支限界最优化方法。(4)对算法进行了测试和分析。我们先构造该问题的解空间树,对问题的规模有了初步的了解,同时通过一个实例简单地演示了该算法的执行过程,并对该问题和算法进行了分析;最后,给出了算法的测试结果,并在实验的基础上对该算法进行更深一部的分析。本文首次利用分支限界方法,求解了时间依赖网络中国邮路问题的精确解。引入了时间因素,使问题的复杂性大大增加。根据实验结果我们可知算法对于小规模的时间依赖有向、无向中国邮路问题非常有效。(本文来源于《大连理工大学》期刊2008-12-10）
闫超[10]（2008）在《时间依赖中国邮路问题的智能算法研究》一文中研究指出中国邮路问题是管梅谷教授在1960年第一次提出来的。它描述了一个极具现实意义的问题:一个邮递员负责一个地区的信件投递,每天从邮局出发,走遍该地区的所有街道再返回邮局,问应该怎样安排送信路线可以使所走的路程最短。该问题得到了深入研究并产生了许多新的分类。近年来,人们日益关注网络中的时变特性,研究时间依赖网络中的问题更具有现实意义。时间依赖最短路径问题、时间依赖旅行商问题和时间依赖车路由问题都得到了深入的研究,旅行商问题和车路由问题都是点路由问题,而作为重要的边路由问题——中国邮路问题与时间依赖网络的结合在国际上还没有相关研究。传统的静态中国邮路算法无法求解时间依赖中国邮路问题,本文提出时间依赖网络中国邮路问题的模型,并借鉴时间依赖网络车路由问题算法思想给出适合于时间依赖网络中国邮路问题的高效求解算法。本文的研究丰富了时间依赖网络的理论。本文首先总结了中国邮路问题各个分支的研究成果,并详细介绍了时间依赖网络车路由问题的研究成果;然后详细介绍了传统中国邮路问题及算法;之后介绍了时间依赖网络的基本概念和性质,通过研究时间依赖中国邮路问题的性质,对时间依赖网络和静态网络中的中国邮路问题进行了比较;之后,证明了时间依赖中国邮路问题是NP-hard问题;最后,给出了求解大规模时间依赖中国邮路问题的二层SA/GA算法,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。实验结果表明,此算法在解决时间依赖网络中的中国邮路问题上是有效的。(本文来源于《大连理工大学》期刊2008-12-01）
时间依赖中国邮路问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
时间依赖中国邮路问题论文参考文献
[1].孙景昊,吴雄,谭国真,闫超.二层SA/GA算法解决时间依赖中国邮路问题[J].计算机科学.2011
[2].谭国真,孙景昊,肖宏业,吕凯.时间依赖无向中国邮路问题的分支限界算法[J].计算机科学.2011
[3].陈加萍.图转换方法求解带时间窗的时间依赖中国邮路问题[D].大连理工大学.2010
[4].孟亚坤.时间依赖网络中国邮路问题的列生成算法[D].大连理工大学.2010
[5].吴雄.多面体理论在时间依赖中国邮路问题中的应用[D].大连理工大学.2010
[6].孙景昊,孟亚坤,谭国真.时间依赖网络中国邮路问题[J].计算机工程与科学.2010
[7].陈加萍,孟宪超,孙景昊,谭国真.时间窗-时间依赖中国邮路问题的图转换算法[J].计算机与数字工程.2010
[8].武雪平.时间依赖的无向中国邮路问题分支切割算法[D].大连理工大学.2009
[9].吕凯.时间依赖网络中国邮路问题的分支限界算法[D].大连理工大学.2008
[10].闫超.时间依赖中国邮路问题的智能算法研究[D].大连理工大学.2008