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

Branch-bound Algorithm for Undirected Time-depended Chinese Postman Problem

作　　者：谭国真[1] 孙景昊[1] 肖宏业[1] 吕凯[1] 

机构地区：[1]大连理工大学计算机科学与技术学院,大连116023

出　　处：《计算机科学》2011年第2期110-113,共4页Computer Science

基　　金：国家973项目(2005CB321904);国家自然科学基金项目(60873256)资助。

摘　　要：时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。The time-dependent network Chinese postman problems（TDCPP） have more applications than the classical Chinese postman problem（CPP）.Many transportation and communication systems can be represented by network with travel times that are time-dependent.When the arc traveling time of system model is time-dependent,the problem be-comes considerably more difficult.Firstly,it was proved that the standard CPP algorithms can not be used to solve the TDCPP.Then according to the properties for the TDCPP,a branch and bound algorithm for undirected time-depended Chinese postman problem was derived.While,particularly,for the FIFO time varying network,a branch and bound algo-rithm was proposed which can solve the problem more effective.Finally,experiment was implemented on micro compu-ter and results show that the algorithm can solve the TDCPP successfully.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]