**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**30761

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

**Authors:**
Jinghao Sun,
Guozhen Tan,
Guangjian Hou

**Abstract:**

**Keywords:**
Integer Programming,
time dependent,
upper bound analysis,
Chinese Postman Problem

**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.