检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

中国邮路问题的0-1规划解法

北方交通大学学报 1992年第1期16卷 65-70页

作者：廖业元北方交通大学工业与建筑管理工程系

在用“奇偶点图上作业法”求解“中国邮路问题”时,需检查图中的每一个回路.当图中回路较多时,检查不便且易出错.针对此,本文建立了求解“中国邮路问题”的0-1规划模型,并给出了算例。

关键词： 0-1规划最短路中国邮路问题

在线全文

学校读者我要写书评

暂无评论

时间依赖网络中国邮路问题

计算机工程与科学 2010年第10期32卷 122-125页

作者：孙景昊孟亚坤谭国真大连理工大学计算机科学与技术学院辽宁大连116023

中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建... 详细信息

中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。

关键词：中国邮路问题时间依赖网络整数线性规划模型上界分析

在线全文

学校读者我要写书评

暂无评论

时间依赖无向中国邮路问题的分支限界算法

计算机科学 2011年第2期38卷 110-113页

作者：谭国真孙景昊肖宏业吕凯大连理工大学计算机科学与技术学院大连116023

时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如... 详细信息

时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。

关键词：时变网络中国邮路问题分支限界先进先出

二层SA/GA算法解决时间依赖中国邮路问题

在线全文

学校读者我要写书评

暂无评论

计算机科学 2011年第5期38卷 93-95,101页

作者：孙景昊吴雄谭国真闫超大连理工大学计算机科学与技术学院大连116023

中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明... 详细信息

中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。

关键词：时间依赖中国邮路问题模拟退火遗传算法

在线全文

学校读者我要写书评

暂无评论

基于蚂蚁算法的中国邮路问题

河南师范大学学报（自然科学版） 2011年第5期39卷 169-171页

作者：于红斌薛占熬河南师范大学计算机与信息技术学院河南新乡453007

针对中国邮路问题中先寻找奇数度结点,再进行奇数度结点之间路线添加的问题,引入了蚂蚁算法,通过其随机概率选择和最短路线激励策略,有效地解决了结点之间的最短路线的问题,避免了常规方法中必须先进行奇数度结点匹配的问题.算法易于实... 详细信息

针对中国邮路问题中先寻找奇数度结点,再进行奇数度结点之间路线添加的问题,引入了蚂蚁算法,通过其随机概率选择和最短路线激励策略,有效地解决了结点之间的最短路线的问题,避免了常规方法中必须先进行奇数度结点匹配的问题.算法易于实现,实验仿真表明算法耗时短、效率高.

关键词：中国邮路问题蚂蚁算法随机概率选择最短路线

在线全文

学校读者我要写书评

暂无评论

时间依赖网络中国邮路问题研究

时间依赖网络中国邮路问题研究

作者：金运通大连理工大学

学位级别：硕士

与传统中国邮路问题相比，对动态网络中国邮路问题的研究具有更为重要的现实应用意义，成为了智能交通系统、计算机网络通信等复杂应用领域迫切需要解决的问题。解决传统中国邮路问题虽然已经有高效的算法，由于交通事故，天气变化等偶... 详细信息

与传统中国邮路问题相比，对动态网络中国邮路问题的研究具有更为重要的现实应用意义，成为了智能交通系统、计算机网络通信等复杂应用领域迫切需要解决的问题。解决传统中国邮路问题虽然已经有高效的算法，由于交通事故，天气变化等偶发因素，使得当网络为时间依赖网络时，应用传统算法得到的解将不符合实际情况的要求。所以需要提出时间依赖网络中国邮路问题的模型，并借鉴时间依赖网络车路由问题算法思想给出高效的算法。本文总结了中国邮路问题各个分支的研究成果，详细介绍了时间依赖网络在最短路径，货郎担问题，车路由问题中的研究情况;然后介绍了时间依赖网络的基本概念、线性规划模型和FIFO特性，并给出了求解时间依赖网络中最短路径算法的理论基础，对动态的中国邮路问题进行了分类和综述，定义了时间依赖网络中的中国邮路问题，总结了问题的特性，对动态网络和静态网络中的中国邮路问题进行了比较，证明了该问题为NP完全问题，并对静态算法在时间依赖网络中的病态实例作了分析;建立了问题的线性规划模型，给出了时间依赖网络中的中国邮路问题第一种情况即时间依赖欧拉问题的动态规划算法，并提出最近邻居启发式算法和随机最近邻居启发式算法。文章随后提出时间依赖中国邮路问题的分支割平面的精确求解算法和基于时间依赖信息素空间的蚁群启发式求解算法，在随机产生的时间依赖网络中的实验结果表明，此算法在解决时间依赖网络中的中国邮路问题上是有效的。理论证明及实验测试都表明，时间依赖网络中国邮路问题算法为动态中国邮路问题的研究提供了新的思路。时间依赖网络中国邮路问题算法的优点不仅在于模型更符合实际情况，能够应用于各种实际问题，而且算法的效率较高，这对于某些领域的应用是很重要的。

关键词：时间依赖网络中国邮路问题线性规划分支割平面算法蚁群优化方法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

时间依赖中国邮路问题的智能算法研究

时间依赖中国邮路问题的智能算法研究

作者：闫超大连理工大学

学位级别：硕士

中国邮路问题是管梅谷教授在1960年第一次提出来的。它描述了一个极具现实意义的问题:一个邮递员负责一个地区的信件投递,每天从邮局出发,走遍该地区的所有街道再返回邮局,问应该怎样安排送信路线可以使所走的路程最短。该问题得到了深... 详细信息

中国邮路问题是管梅谷教授在1960年第一次提出来的。它描述了一个极具现实意义的问题:一个邮递员负责一个地区的信件投递,每天从邮局出发,走遍该地区的所有街道再返回邮局,问应该怎样安排送信路线可以使所走的路程最短。该问题得到了深入研究并产生了许多新的分类。近年来,人们日益关注网络中的时变特性,研究时间依赖网络中的问题更具有现实意义。时间依赖最短路径问题、时间依赖旅行商问题和时间依赖车路由问题都得到了深入的研究,旅行商问题和车路由问题都是点路由问题,而作为重要的边路由问题——中国邮路问题与时间依赖网络的结合在国际上还没有相关研究。传统的静态中国邮路算法无法求解时间依赖中国邮路问题,本文提出时间依赖网络中国邮路问题的模型,并借鉴时间依赖网络车路由问题算法思想给出适合于时间依赖网络中国邮路问题的高效求解算法。本文的研究丰富了时间依赖网络的理论。本文首先总结了中国邮路问题各个分支的研究成果,并详细介绍了时间依赖网络车路由问题的研究成果;然后详细介绍了传统中国邮路问题及算法;之后介绍了时间依赖网络的基本概念和性质,通过研究时间依赖中国邮路问题的性质,对时间依赖网络和静态网络中的中国邮路问题进行了比较;之后,证明了时间依赖中国邮路问题是NP-hard问题;最后,给出了求解大规模时间依赖中国邮路问题的二层SA/GA算法,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。实验结果表明,此算法在解决时间依赖网络中的中国邮路问题上是有效的。

关键词：时间依赖网络中国邮路问题模拟退火遗传算法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

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

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

作者：王金香大连理工大学

学位级别：硕士

中国邮路问题是著名的图论问题,也是组合优化、运筹规划领域经典的问题之一在通信系统、交通管理、机器人探测、交互式系统分析、网站可用性和软件测试等领域有着重要的应用。然而,随着通信技术与分布式系统的发展,混合系统测试和智能... 详细信息

中国邮路问题是著名的图论问题,也是组合优化、运筹规划领域经典的问题之一在通信系统、交通管理、机器人探测、交互式系统分析、网站可用性和软件测试等领域有着重要的应用。然而,随着通信技术与分布式系统的发展,混合系统测试和智能交通等复杂领域的应用都在关注实际问题中的时间特性,即网络中弧的权值依赖于时间变化而变化,我们称具有这种性质的网络为时变网络。在以往中国邮路问题的研究中,都是假设网络中的权值是静态的、确定的,而实际问题中网络往往是动态的,比如现实交通网络中,交通事故和天气变化等偶然事件都有可能造成道路交通状况的变化,那么邮递员送信沿途所经过街道的旅行时间也会随之变化。中国邮路问题的传统模型和算法只能求解固定弧权条件下的问题,在时变网络中应用传统算法求得的解根本不符合实际情况的要求。因此,研究时变网络中国邮路问题的模型和优化算法具有更为重要的现实意义。然而,引入时间因素后新问题的求解变得非常困难,时变网络有向中国邮路问题已被证明是NP难的,直接求解最优解往往是不实际的。本文从数学规划优化方法的角度出发研究时变网络有向中国邮路问题,首先借鉴时变网络旅行商问题的建模思想结合圈覆盖相关理论建立了时变网络有向中国邮路问题的一个整数规划模型。并根据时间依赖旅行时间函数的阶梯特性,对模型进行了线性化,而且通过分析模型的上界优化了模型。然后基于整数线性规划模型,本文提出了一个启发式割平面求解算法。此外,根据旅行时间的特性,本文还提出了两类强有效不等式并作为割平面约束条件添加到了算法的迭代过程中。文章最后结合一些测试实例对模型和算法进行了测试和分析。本文所提的割平面启发式算法,是在割平面精确算法的框架中添加了一些新的启发式规则,实验结果表明,该算法虽然不是最优化算法,但对于小于15条弧的小规模问题算法能求出67%实例的最优解,对中等规模问题求得的解的上下界的差值平均不超过20%,其中,两类强有效不等式将问题解的质量提高了28%左右。启发式割平面算法快速和求解质量高的特点,扩展了数学规划优化算法和启发式算法的应用领域。此外,本文提出的新模型,对时变网络的其他弧路由问题有着很好的借鉴意义。

关键词：时变网络中国邮路问题整数线性规划割平面算法启发式

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

随机网络中国邮路问题算法研究

随机网络中国邮路问题算法研究

作者：崔晓婷大连理工大学

学位级别：硕士

与传统中国邮路问题相比,对随机网络中国邮路问题的研究具有更为重要的现实应用意义,成为了智能交通系统、计算机网络通信等复杂应用领域迫切需要解决的问题。解决传统中国邮路问题虽然已经有高效的算法,但由于交通事故,天气变化等偶发... 详细信息

与传统中国邮路问题相比,对随机网络中国邮路问题的研究具有更为重要的现实应用意义,成为了智能交通系统、计算机网络通信等复杂应用领域迫切需要解决的问题。解决传统中国邮路问题虽然已经有高效的算法,但由于交通事故,天气变化等偶发因素,使得当网络为随机网络时,应用传统算法得到的解将不符合实际情况的要求。所以需要提出随机网络中国邮路问题的模型,并借鉴随机网络最短路径问题算法思想给出高效的算法。本文首先给出了随机网络的模型和随机网络无向中国邮路问题的定义,在网络中引入随机因素,每条弧上的权值包含两个状态,网络中不同弧上的权值是相互依赖的随机变量。其次,当利用传统算法求得的最优方案中有边发生拥挤时,给出替换方法和求解替换方法的理论基础。同时,给出了求解随机网络无向中国邮路问题的算法,从理论上证明了算法的正确性,并给出了算法的时间复杂度分析,可以得出算法具有较高的效率。然后,给出了解决随机网络有向中国邮路问题的定义和理论基础,利用增量算法对原有的替换方法进行改进,进一步提高了算法的效率,并给出实例。最后,给出启发式算法与该算法进行比较,对问题的进一步研究提供可以借鉴的思路。理论证明及实验测试都表明,随机网络中国邮路问题算法为动态中国邮路问题的研究提供了新的思路。随机网络中国邮路问题算法的优点不仅在于模型更符合实际情况,能够应用于各种实际问题。而且算法的效率较高,这对于某些领域的应用是很重要的。

关键词：随机网络中国邮路问题欧拉回路增量算法