Solving the Time Dependent Chinese Postman Problem by Branch-and-Bound Algorithm

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.