点击次数：

论文类型：期刊论文

发表时间：2012-12-01

发表刊物：INFORMATION-AN INTERNATIONAL INTERDISCIPLINARY JOURNAL

收录刊物：SCIE、Scopus

卷号：15

期号：12A,SI

页面范围：5263-5270

ISSN号：1343-4500

关键字：Time Dependent; Chinese Postman Problem; Branch-and-Bound

摘要：The Chinese Postman Problem (CPP) is one of the classical problems in graph theory and is applicable in a wide range of fields. With the rapid development of hybrid systems and model based testing, CPP defined on the time dependent network becomes more realistic than the classical problems. This paper proposes the Time Dependent Chinese Postman Problem (TDCPP) theoretically based on the two classical algorithmic approaches for solving the traditional problems in the literature, namely, two-stage strategy and arc routing transformation, which can respectively solve the conventional and timing-sensitive CPPs. This paper proves that these two algorithms are not available for time dependent networks. On the positive side, we propose a branch-and-bound algorithm for the problem with the First-In-First-Out property. Experimental results show that the dominance relation in the branch-and-bound algorithm is more efficient when the network is not Euclidian, and that small to medium-sized instances can be solved to proven optimality.