中国邮路问题的一个解法

本文给出中国邮路问题的一个解法。虽然它仍只是初始方案,但因考虑了问题的足够信息,因而这种方案至少拉近了与最优解的距离。

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.

时间窗-时间依赖中国邮路问题的图转换算法

研究时间依赖网络上带时间窗的中国邮路问题(TDCPPTW),该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势。首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题(GRPP);最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验。

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

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

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

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

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

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

利用Floyed-Hungary法求解中国邮路问题

对于中国邮路问题,可以用奇偶点作业法,但当顶点较多时,寻找每一个圈并对其进行检验的工作十分复杂。利用求图中各点之间最短路径的方法Floyed法和求解指派问题的方法Hun-gary法可提供一种对任意个顶点的中国邮路问题的解法—Floyed-Hungary法。

一种改进的量子进化算法及其在乡村邮路问题的应用

针对基本量子进化算法易陷于局部最优解的缺陷,提出一种改进的量子进化算法(QEA)。结合乡村邮路问题,对算法进行了测试,结果表明,改进算法在全局寻优能力和种群多样性方面比基本量子进化算法有所改进,是求解乡村邮路问题的一种有效算法。

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

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

关于E_0的Steiner邮路问题

给定图G=(V,E,w),E_0E是一个指定通过的边子集,本文讨论了关于E_0的Steiner邮路问题的特殊情况,即由E_0导出的子图仅有两个连通分支。我们分别考虑了三种不同的情形,并给出了子闭迹消去算法和带限制的最短链算法,前者是一个基于整数规划的精确算法,而后者是一个近似算法。

关于E0的Steiner邮路问题的转化求解

简述了图论中的中国邮路问题的求解方法,设法将有两个连通分支的子图转化为中国邮路问题,从而求解那些满足E0的Steiner邮路问题边界条件的两个连同分支问题。

基于中国邮路问题的配送线路规划

烟草配送到户的特点是停留点分布分散,配送车辆需穿行于城市的每一条街道,与邮递员的工作特点非常相似。以运筹学上的中国邮路问题为模型,对某烟草配送公司的配送线路进行规划,用定量的方法提高行驶路线的精确性和标准化程度,争取以更少的车辆、人力和里程数完成更大的服务量。

遗传算法求解有向中国邮路问题

在图形变换的基础上，用遗传算法实现了对有向邮路问题的求解本文所提方法较之传统方法更易于编程实现和求解大规模复杂网络问题实例表明。

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

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

基于中国邮路问题的移动基站切换链路测方法研究

文章基于中国邮路问题,提出了移动基站切换链路测的新方法。根据基站与城市道路之间的关系以及交通规则,提出了移动基站切换链路测方法的有向图模型,使移动基站切换链路测问题成为了中国邮路问题。在移动基站切换链路测方法的有向图模型中,通过把单行道转化为双行道后,使该方法的有向图模型由非欧拉图转化成了欧拉图,经过这样特殊处理后,大大降低了求解移动基站切换链路测问题的复杂性。为了验证该方法的有效性,文章用一个具体的实例来证明了其有效性。

Euler图中的中国邮路问题的Fleury算法

本文首先对什么是中国邮路问题以及它的图论模型进行了解释，并对只含有偶顶点的Euler图中的中国邮路问题用Flew算法做了解答，而这一方法在解决含有奇顶点的一般性的中国邮路问题，同样具有重要的参考价值。

中国邮路最短路问题的研究

中国邮路问题意义重大,在现实中应用广泛。中国邮路问题即利用一种计算方法来求解邮递员投递所需要经历的最短路线。该方法把邮递线路看作连通加权无向图,然后通过Fleury算法求解得到最优邮路。在实际例子的求解过程中,发现该方法并不能求出唯一解即存在次优解。我们将继续研究邮路问题以便获得最佳的计算方法。

“中国邮路问题”及其应用

一个邮递员从邮局出发,要走遍他负责投递范围内的街道、然后回到邮局.试问:邮递员选择怎样的行走路线,才能使所走的路程为最短呢?类似这样的问题还有:奶场送奶人员、街道清扫机、走什么样的路线才能使所走的路程为最短呢?电话线从交换台引出来、电从发电厂发出来、煤气管道铺设选择何种路线把各用户联结才能使材料用量为最少呢?等等.我们可将这类问题归纳为"中国邮路问题".

基于中国邮路算法的装配序列规划

基于中国邮路问题及其解法,提出装配序列规划的新方法。把网络图理论引入装配关系模型表达,提出无向装配网络图模型,使装配序列规划问题成为中国邮路问题;通过对装配网络图实施变换,装配模型转换为有向图,生成装配序列,同时给出变换为有向图的方法。该方法计算量小,产生的装配序列均为有效序列。最后,以一个装配实例验证算法的有效性。

Lingo关于TSP问题的新解及应用

目前关于lingo软件求解旅行商售货员问题(Traveling Salesman Problem,TSP)的解法基本上都是采用了二维坐标形式,本文采用了三维坐标形式运用lingo软件对TSP给出新解,并给出若干应用.可以看到lingo软件求解效果还是不错的,而且直观意义很明显,容易理解和控制.