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

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

摘要：考虑到城市电缆网闭环设计、开环运行,在满足相关巡检原则的条件下,以巡检时间最短为目标,将电缆及通道巡检问题归类为中国邮路问题,提出基于整数规划的电力电缆及通道巡检策略,分析该策略的数学模型,根据状态评价结果,将待检修设备所耗的时间计入网络权值,并以某实际电缆网络为研究对象,验证了所提策略的有效性。

摘要：为了提高无线传播模型校正等路测工作中路径规划的准确性,本文利用图论中的欧拉回路概念,结合中国邮路问题的相关研究,综合考虑测试区域的道路拓扑结构、路径长度、交通规则等因素,提出一种基于欧拉回路并采用改进的深度优先搜索算法实现的道路测试路径优化方法。该方法可以实现自动生成最优测试路线,提升了路测效率。