A New Integer Programming Formulation for the Chinese Postman Problem with Time Dependent Travel Times

Authors: Jinghao Sun, Guozhen Tan, Guangjian Hou

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.

Keywords: Chinese Postman Problem, Time Dependent, Integer Programming, Upper Bound Analysis.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1073389

References:

[1] M. K. Guan, Graphic programming using odd or even points, Chinese Mathematics, vol.1, pp.273-277, 1962.
[2] A. V. Aho, A. T. Dahbura, D. Lee, M. U. Uyar, An Optimisation technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours, IEEE transactions on communications vol.39, pp.1604-1615, 1991.
[3] R. Lai, A survey of communication protocol testing, Journal of Systems and Software vol.62, pp.21-46, 2002.
[4] M. Yannakakis, Testing, optimization, and games, In Proceedings of the Nineteenth Annual IEEE Symposium on Logic In Computer Science, LICS, pp.78-88, 2004.
[5] C. Chi, R, Hao, Test Generation for Interaction Detection in Feature-Rich Communication Systems, Computer Networks vol.51, pp.426-438, 2007.
[6] H. A. Eiselt, M. Gendreau, G. Laporte, Arc routing problems, Part I: The Chinese postman problem, Operations Research, vol.43, pp.231-242, 1995.
[7] H. A. Eiselt, M. Gendreau, G. Laporte, Arc routing problems, Part II: The Chinese postman problem, Operations Research, vol.43, pp.399-414, 1995.
[8] M. Dror, Arc routing: Theory, solutions and applications, Kluwer Academic Publishers. Boston, 2000.
[9] A. Hessel, K. G. Larsen, B. Nielsen, P. Pettersson, A. Skou, Time-Optimal Test Cases for Real-Time Systems, In 3rd International Workshop on Formal approaches to Testing of Software (FATES 2003), Montreal, Quebec, Canada, October 2003.
[10] P. R. Springintveld, F. Vaandrager, Testing timed automata, Theoretical computer science vol.254, pp.225-257, 2001.
[11] G. Z. Tan, J. H. Sun, J. X. Wang, Chinese Postman Problem with Time Dependent Travel Times: Polyhedron Results, Discrete Optimization, 2010, Summited to be published
[12] P. A. Mullaseril, Capacitated rural postman problem with time windows and split delivery, Ph.d thesis. University of Arizona, 1996.
[13] M. Tagmouti, M. Gendreau, J. Y. Potvin, Arc routing problems with time-dependent service costs, European Journal of Operational Research, vol.181, pp.30-39, 2007.
[14] W. L. Pearn, A. Assad, B. L. Golden, Transforming arc routing into node routing problems, Computers and Operations Research, vol.14, no.4, pp.285-288, 1987.
[15] G. Laporte, Modeling and solving several classes of arc routing problems as traveling salesman problems, Computers and Operations Research vol.24, pp.1057-1061, 1997.
[16] H. Longo, M. P. Aragao, E. Uchoa, Solving capacitated arc routing problems using a transformation to the CVRP, Computers and Operations Research, vol.33, pp.1823-1837, 2006.