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

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.

Authors:

• Jinghao Sun
• Guozhen Tan
• Guangjian Hou

Keywords:

• Chinese Postman Problem
• Time Dependent
• Integer Programming
• Upper Bound Analysis.

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.