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

Time-dependent Chinese Postman Problem Solved by Two Layers SA/GA Algorithm

作　　者：孙景昊[1] 吴雄[1] 谭国真[1] 闫超[1] 

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

出　　处：《计算机科学》2011年第5期93-95,101,共4页Computer Science

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

摘　　要：中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。The Chinese postman problem is one of the classical problems in graph theory and has been widely and deeply researched since it was proposed.It is applicable in a wide range of fields.With the rapid development of computer networks,computer communication and intelligent transportation system,problems in time-dependent networks become more realistic than the classical problems.First,we presented the definition of time-dependent Chinese postman problem（TDCPP） and the property of TDCPP.Then we showed that the classical algorithms of Chinese postman problem（CPP） can＇t work in the time-dependent circumstances.Finally,two layers SA/GA algorithm（simulated annealing/ genetic algorithm） was proposed,this approach was tested on some randomly generated data,the computational results were analyzed by comparing with lower bound of the problem.

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

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