时变网络的中国邮路问题：理论、模型、算法及应用研究

项目名称： 时变网络的中国邮路问题：理论、模型、算法及应用研究

项目编号： No.60873256

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 谭国真

作者单位： 大连理工大学

项目金额： 33万元

中文摘要： 随着信息技术的发展，不同学科领域日益关注网络中的时间约束和时变特性，于是能够充分反映时间特性的时变网络优化应运而生。时变网络优化突破了传统理论的局限性，产生了许多挑战性问题。这些问题有些已经得到解决，还有许多问题虽然在应用中已经遇到，但是尚未解决。本课题正是针对这些尚未解决的网络优化问题开展研究，具体的特色与创新之处：一是首次系统地提出了时变网络中国邮路问题，并研究其计算复杂性、性质、模型、精确和启发式解法以及性能评价方法，进一步发展和丰富了时变网络优化的理论体系；二是针对实时系统测试中的一个热点问题开展应用研究，为解决实时系统测试序列生成和优化这一重要问题提供了新的技术途径和新方法。本课题是计算机科学、运筹学、通信工程等综合交叉学科研究热点，不同学科的相互交叉、相互渗透、相互促进，极有可能产生新的理论和新方法。本课题是时变网络优化领域的重要组成部分，具有重要的理论意义和应用价值。

中文关键词： 时间依赖；时间窗；网络优化；中国邮路问题；软件测试

英文摘要： Along with the development of information technology, several different science branches pay more attention to the network with time constraint and time-varying characteristics, so the theory of time-varying networks optimization was presented which completely reflects the time-varying characteristic. There are many new challenge problems raised by the theory of time-varing networks optimization which break through the traditional limitation. Few of them have been solved, and most of them are never been conquered although they have been encountered in the practical applications. In this subject, a new kind of time-varing networks optimization Problems called Chinese postman problems with time-varying networks are studied intensively for the first time. There are two main contributions in this subject: first, it can enrich the theory of time-varing networks optimization which will be further studied including computational complexity, theorems of problem properties, mathematical models, exact and heuristic algorithms, as well as evaluation of algorithms. Second, it can also develop the study of a key problem in real-time system software testing, and provide new technical methods to the test generation of real-time system. This subject is a hotspot of the cross discipline of many science branches including computer science, operational research and communication engineering, which can come together, penetrate and affect each other to promote new theories and methods; it is also an important part of the time-varying networks optimization theory, and it has essential theoretical meaning and application value.

英文关键词： time dependent; time window; network optimization; Chinese postman problem; software testing