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