@article{(Open Science Index):https://publications.waset.org/pdf/9764, title = {A New Integer Programming Formulation for the Chinese Postman Problem with Time Dependent Travel Times}, author = {Jinghao Sun and Guozhen Tan and Guangjian Hou}, country = {}, institution = {}, 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, Chinese Postman Problem with Time Dependent Travel Times (CPPTDT) becomes more realistic than the classical problems. In the literature, we have proposed the first integer programming formulation for the CPPTDT problem, namely, circuit formulation, based on which some polyhedral results are investigated and a cutting plane algorithm is also designed. However, there exists a main drawback: the circuit formulation is only available for solving the special instances with all circuits passing through the origin. Therefore, this paper proposes a new integer programming formulation for solving all the general instances of CPPTDT. Moreover, the size of the circuit formulation is too large, which is reduced dramatically here. Thus, it is possible to design more efficient algorithm for solving the CPPTDT in the future research.}, journal = {International Journal of Computer and Information Engineering}, volume = {5}, number = {4}, year = {2011}, pages = {410 - 414}, ee = {https://publications.waset.org/pdf/9764}, url = {https://publications.waset.org/vol/52}, bibsource = {https://publications.waset.org/}, issn = {eISSN: 1307-6892}, publisher = {World Academy of Science, Engineering and Technology}, index = {Open Science Index 52, 2011}, }