点击次数：

论文类型：期刊论文

发表时间：2011-11-01

发表刊物：ICIC Express Letters

收录刊物：EI、Scopus

卷号：5

期号：11

页面范围：4071-4077

ISSN号：1881803X

摘要：This paper studies the Chinese Postman Problem with Time Dependent travel times. This problem is motivated by hybrid system testing where the "timing" of each transition is crucial. The first integer programming for this problem, namely, circuit formulation, was presented in our previous work, which has a main drawback that it is only available for solving the special instances with all circuits passing through the origin. To deal with the general instances, this paper establishes a new integer programming using not only circuit but also arc traversal order as decision variables. Moreover, the most crucial factor of the formulation size, circuit number K, is improved from {pipe}A{pipe} - {pipe}V{pipe} + 1 to the maximum in/out degree in the network G(V,A), which can reduce the size of integer programming dramatically. ? 2011 ICIC International.