| 二层SA/GA算法解决时间依赖中国邮路问题 |
| |
| 引用本文： | 孙景昊,吴雄,谭国真,闫超.二层SA/GA算法解决时间依赖中国邮路问题[J].计算机科学,2011,38(5):93-95. |
| |
| 作者姓名： | 孙景昊 吴雄 谭国真 闫超 |
| |
| 作者单位： | 大连理工大学计算机科学与技术学院,大连,116023 |
| |
| 基金项目： | 本文受国家973项目(2005CB321904)，国家自然科学基金项目(60873256)资助。 |
| |
| 摘 要： | 中国邮路问题是图论中的经典问题，得到了深入研究和广泛应用。近年来，由于计算机网络与通信、智能交通系统等复杂应用领域的需求，研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义，然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立，最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题，对随机产生的实例进行了测试，并根据问题下界对算法结果进行了分析。
|
| 关 键 词： | 时间依赖，中国邮路问题，模拟退火，遗传算法 |
Time-dependent Chinese Postman Problem Solved by Two Layers SA/GA Algorithm |
| |
| SUN Jing-hao,WU Xiong,TAN Guo-zhen,YAN Chao.Time-dependent Chinese Postman Problem Solved by Two Layers SA/GA Algorithm[J].Computer Science,2011,38(5):93-95. |
| |
| Authors: | SUN Jing-hao WU Xiong TAN Guo-zhen YAN Chao |
| |
| Affiliation: | (School of Computer Science and Technology,Dalian University of Technology,Dalian 116023,China) |
| |
| Abstract: | 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 timcdependent 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 timcdependent 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. |
| |
| Keywords: | Time-dependent Chinese postman problem Simulated annealing Genetic algorithm |
| 本文献已被 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
