Skip to Main content Skip to Navigation
Journal articles

Approximating the length of Chinese postman tours

Abstract : This article develops simple and easy-to-use approximation formulae for the length of a Chinese Postman Problem (CPP) optimal tour on directed and undirected strongly connected planar graphs as a function of the number of nodes and the number of arcs for graphs whose nodes are randomly distributed on a unit square area. These approximations, obtained from a multi-linear regression analysis, allow to easily forecast the length of a CPP optimal tour for various practical combinations of number of arcs and nodes ranging, from 10 to 300 nodes and 15 to 900 arcs.
Document type :
Journal articles
Complete list of metadata
Contributor : Nathalie Bostel Connect in order to contact the contributor
Submitted on : Tuesday, January 20, 2015 - 10:50:30 AM
Last modification on : Wednesday, April 27, 2022 - 3:44:03 AM



Nathalie Bostel, Philippe Castagliola, Pierre Dejax, André Langevin. Approximating the length of Chinese postman tours. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2014, 12 (4), pp.359-372. ⟨10.1007/s10288-014-0260-9⟩. ⟨hal-01105336⟩



Record views