Hits:

Indexed by:期刊论文

Date of Publication:2012-12-01

Journal:INFORMATION-AN INTERNATIONAL INTERDISCIPLINARY JOURNAL

Included Journals:SCIE、Scopus

Volume:15

Issue:12A,SI

Page Number:5263-5270

ISSN No.:1343-4500

Key Words:Time Dependent; Chinese Postman Problem; Branch-and-Bound

Abstract: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.