导读:本文包含了中国邮路问题论文开题报告文献综述及选题提纲参考文献，主要关键词:图论应用,中国邮路问题,欧拉回路
中国邮路问题论文文献综述
顾戍杰[1]（2017）在《中国邮路最短路问题的研究》一文中研究指出中国邮路问题意义重大,在现实中应用广泛。中国邮路问题即利用一种计算方法来求解邮递员投递所需要经历的最短路线。该方法把邮递线路看作连通加权无向图,然后通过Fleury算法求解得到最优邮路。在实际例子的求解过程中,发现该方法并不能求出唯一解即存在次优解。我们将继续研究邮路问题以便获得最佳的计算方法。(本文来源于《信息通信》期刊2017年02期）
廖宏军[2]（2013）在《中国邮路问题的新型图书物流方案》一文中研究指出针对以京东为例的图书配送线路的优化问题,以图书配送路线总路程最短为目标,在充分考虑"中国邮递员问题"基础上,建立了图书配送线路优化模型。通过该模型可以得到图书配送的总路程和配送路线。最后,基于WINQSB软件综合考虑运费、路程、时间等众多因素,将其重要性进行排序,优化了目前单一的配送方式。(本文来源于《承德石油高等专科学校学报》期刊2013年06期）
孙景昊[3]（2012）在《时变中国邮路问题的整数规划模型及算法研究》一文中研究指出本文提出了一类新的时变网络优化问题—时间依赖网络中国邮路问题。时间依赖特性使得该问题变得十分困难,传统理论在时间依赖网络中不再适用。因此本文围绕时间依赖网络中国邮路问题的计算复杂性、整数规划模型和算法等方面开展研究,具体说来,分为一下叁个方面：(1)从计算复杂性、传统算法适用性以及最优解性质叁个层面对时间依赖网络中国邮路问题的性质进行分析：①证明了即使在时间依赖网络满足欧拉性质和先进先出性质的条件下,时间依赖网络中国邮路问题依然是NP-困难问题；②证明了传统中国邮路中的经典算法—二阶段算法和弧路由转换算法均不适用于时间依赖网络,为修正和改良已有算法提供了理论依据；③提出了先进先出网络中国邮路问题的两个最优解性质,并将最优解性质应用于精确算法的支配条件和递推方程的设计。(2)从整数线性规划模型、多面体分析两方面入手研究了时间依赖网络中国邮路问题的数学规划方法：①建立了时间依赖网络中国(乡村)邮路问题的圈变量、交错圈变量、弧变量以及弧-路径变量等四类整数线性规划模型：②基于圈变量和弧-路径变量整数规划模型进行了多面体分析,证明了多面体的维数和极大诱导不等式,并给出了两类时间相关强有效不等式,将这些不等式作为割平面动态添加到算法中,能够有效提高问题最优解下界。(3)提出时间依赖网络中国邮路问题的叁类算法：①提出了先进先出网络中国邮路问题的分支限界算法和动态规划算法；②基于圈变量模型和弧-路径变量模型的多面体分析,提出了时间依赖网络中国(乡村)邮路问题的割平面算法；③基于时间自动机,给出叁类时变中国邮路问题：时间窗中国邮路、时间依赖旅行时间中国邮路、时间依赖服务代价中国邮路的统一求解框架。(本文来源于《大连理工大学》期刊2012-03-01）
于红斌,薛占熬[4]（2011）在《基于蚂蚁算法的中国邮路问题》一文中研究指出针对中国邮路问题中先寻找奇数度结点,再进行奇数度结点之间路线添加的问题,引入了蚂蚁算法,通过其随机概率选择和最短路线激励策略,有效地解决了结点之间的最短路线的问题,避免了常规方法中必须先进行奇数度结点匹配的问题.算法易于实现,实验仿真表明算法耗时短、效率高.(本文来源于《河南师范大学学报(自然科学版)》期刊2011年05期）
谭国真,孙景昊,王宝财,姚卫红[5]（2011）在《时变网络中国邮路问题的时间自动机模型》一文中研究指出基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.(本文来源于《软件学报》期刊2011年06期）
孙景昊,吴雄,谭国真,闫超[6]（2011）在《二层SA/GA算法解决时间依赖中国邮路问题》一文中研究指出中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。(本文来源于《计算机科学》期刊2011年05期）
谭国真,孙景昊,肖宏业,吕凯[7]（2011）在《时间依赖无向中国邮路问题的分支限界算法》一文中研究指出时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。(本文来源于《计算机科学》期刊2011年02期）
陈加萍[8]（2010）在《图转换方法求解带时间窗的时间依赖中国邮路问题》一文中研究指出近年来,随着信息技术的高速发展和以物联网为驱动的研究热潮的到来,人们对应用系统的实时性提出了更高的要求,越来越多的实际问题变得与时间因素有着密切的联系。带时变特性的问题是一个与实际应用结合紧密、发展前景广阔的研究领域,它能够提供一种对现实问题建模更精确的方法,显然成为一个值得去深入研究的非常具有挑战性的领域。本文研究的是时变网络上的带时间窗的中国邮路问题(TDCPPTW),该问题是传统中国邮路问题在动态时间属性方面的扩展。由于传统的静态网络的路由算法并未对网络的动态性给出有效的解决方案。因此,如何针对时间依赖网络的时间约束和实时性变化进行建模,并迅速、精确的对其进行优化求解是一类至关重要的问题。本文首先对带时间窗的时间依赖中国邮路问题的定义和特性进行了深入研究,并分析了时间依赖旅行时间和时间窗所引起的求解难度,发现传统的弧路由转换方法不再适用于时间依赖网络。然后,针对时间依赖网络提出一个新的图转换算法,把原始时间依赖网络离散为一个有着“弧集簇”结构的静态辅助图。进一步基于图转换后的静态辅助图,把原始时间依赖问题转换为静态图辅助图上的广义弧路由问题,并从理论上证明了转换前后问题的等价性。同时,为了克服转换后静态网络的规模严重增大的缺陷,设计出一个图缩减算法,且从理论上证明了该缩减算法的正确性和有效性。接着,建立求解广义弧路由问题的0-1混合整数规划模型,并分析其变量和约束的个数,发现当问题规模增大时模型的变量会变得相当庞大；因此,进一步将模型分割为主问题和子问题,以采用列生成算法来适应大规模实例的求解。最后,采用随机生成的方法构造大量TDCPPTW的测试实例,并应用本文所提出的转换算法和数学模型对其进行求解实验。实验结果并得充分肯定了本文所构造的图转换算法和求解模型的正确性和有效性。(本文来源于《大连理工大学》期刊2010-11-15）
孟亚坤[9]（2010）在《时间依赖网络中国邮路问题的列生成算法》一文中研究指出中国邮路问题是图论中的经典问题,得到了广泛的研究。该问题有着众多的应用领域,如邮件投递路线,扫雪车路线,警车出巡安排,机器人检测路线路线以及软、硬件系统的测试序列优化等等,因此吸引了众多学者的研究兴趣。近年来,由于计算机网络与通信、智能交通系统以及混合系统实时测试等复杂应用领域的需求,时变网络中国邮路问题的研究具有更为重要的现实应用意义。带时间窗的中国邮路问题、时间依赖服务代价中国邮路问题以及时间依赖旅行时间中国邮路问题均属于时变网络中国邮路问题。其中,前两个问题已经得到了较好的研究,但由于时间依赖旅行时间中国邮路问题建模十分困难,因此,一直鲜有研究。然而,本文将致力于时间依赖旅行时间中国邮路问题的研究。本文首先对传统的中国邮路问题和时变网络中国邮路问题的研究方法进行了归纳总结,并介绍了列生成算法的原理及其在时变网络中的应用。然后,通过将中国邮路可行解看成是图中圈的排列组合,设计了以基本圈为决策变量的整数线性规划模型,并从理论上证明了该模型中基本圈数的上界为m-n+1。由于该整数规划模型的规模比较大,因此,本文设计了列生成算法求解该问题。首先,将圈变量整数规划模型抽象为带偏序关系的集合覆盖主问题模型,降低了解空间的维数；然后,通过对偶理论设计了时间依赖最短路子问题,并应用遗传算法求解,从而进一步确定了最优解的搜索方向。但是,这个模型只能解决所有圈均过原点的特例,针对存在圈不过原点的网络拓扑,文章针对可行解的特点给出了另外一个“层路径”数学规划模型,同时对该模型的上界进行了理论分析,算例验证了该模型的正确性。(本文来源于《大连理工大学》期刊2010-11-13）
王金香[10]（2010）在《时变网络有向中国邮路问题的割平面算法研究》一文中研究指出中国邮路问题是着名的图论问题,也是组合优化、运筹规划领域经典的问题之一在通信系统、交通管理、机器人探测、交互式系统分析、网站可用性和软件测试等领域有着重要的应用。然而,随着通信技术与分布式系统的发展,混合系统测试和智能交通等复杂领域的应用都在关注实际问题中的时间特性,即网络中弧的权值依赖于时间变化而变化,我们称具有这种性质的网络为时变网络。在以往中国邮路问题的研究中,都是假设网络中的权值是静态的、确定的,而实际问题中网络往往是动态的,比如现实交通网络中,交通事故和天气变化等偶然事件都有可能造成道路交通状况的变化,那么邮递员送信沿途所经过街道的旅行时间也会随之变化。中国邮路问题的传统模型和算法只能求解固定弧权条件下的问题,在时变网络中应用传统算法求得的解根本不符合实际情况的要求。因此,研究时变网络中国邮路问题的模型和优化算法具有更为重要的现实意义。然而,引入时间因素后新问题的求解变得非常困难,时变网络有向中国邮路问题已被证明是NP难的,直接求解最优解往往是不实际的。本文从数学规划优化方法的角度出发研究时变网络有向中国邮路问题,首先借鉴时变网络旅行商问题的建模思想结合圈覆盖相关理论建立了时变网络有向中国邮路问题的一个整数规划模型。并根据时间依赖旅行时间函数的阶梯特性,对模型进行了线性化,而且通过分析模型的上界优化了模型。然后基于整数线性规划模型,本文提出了一个启发式割平面求解算法。此外,根据旅行时间的特性,本文还提出了两类强有效不等式并作为割平面约束条件添加到了算法的迭代过程中。文章最后结合一些测试实例对模型和算法进行了测试和分析。本文所提的割平面启发式算法,是在割平面精确算法的框架中添加了一些新的启发式规则,实验结果表明,该算法虽然不是最优化算法,但对于小于15条弧的小规模问题算法能求出67%实例的最优解,对中等规模问题求得的解的上下界的差值平均不超过20%,其中,两类强有效不等式将问题解的质量提高了28%左右。启发式割平面算法快速和求解质量高的特点,扩展了数学规划优化算法和启发式算法的应用领域。此外,本文提出的新模型,对时变网络的其他弧路由问题有着很好的借鉴意义。(本文来源于《大连理工大学》期刊2010-11-12）
中国邮路问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
针对以京东为例的图书配送线路的优化问题,以图书配送路线总路程最短为目标,在充分考虑"中国邮递员问题"基础上,建立了图书配送线路优化模型。通过该模型可以得到图书配送的总路程和配送路线。最后,基于WINQSB软件综合考虑运费、路程、时间等众多因素,将其重要性进行排序,优化了目前单一的配送方式。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
中国邮路问题论文参考文献
[1].顾戍杰.中国邮路最短路问题的研究[J].信息通信.2017
[2].廖宏军.中国邮路问题的新型图书物流方案[J].承德石油高等专科学校学报.2013
[3].孙景昊.时变中国邮路问题的整数规划模型及算法研究[D].大连理工大学.2012
[4].于红斌,薛占熬.基于蚂蚁算法的中国邮路问题[J].河南师范大学学报(自然科学版).2011
[5].谭国真,孙景昊,王宝财,姚卫红.时变网络中国邮路问题的时间自动机模型[J].软件学报.2011
[6].孙景昊,吴雄,谭国真,闫超.二层SA/GA算法解决时间依赖中国邮路问题[J].计算机科学.2011
[7].谭国真,孙景昊,肖宏业,吕凯.时间依赖无向中国邮路问题的分支限界算法[J].计算机科学.2011
[8].陈加萍.图转换方法求解带时间窗的时间依赖中国邮路问题[D].大连理工大学.2010
[9].孟亚坤.时间依赖网络中国邮路问题的列生成算法[D].大连理工大学.2010
[10].王金香.时变网络有向中国邮路问题的割平面算法研究[D].大连理工大学.2010