Hits:

Indexed by:期刊论文

Date of Publication:2011-11-01

Journal:ICIC Express Letters

Included Journals:EI、Scopus

Volume:5

Issue:11

Page Number:4071-4077

ISSN No.:1881803X

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