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

https://hal.inria.fr/hal-01105336
Contributor : Nathalie Bostel <>
Submitted on : Tuesday, January 20, 2015 - 10:50:30 AM
Last modification on : Friday, July 30, 2021 - 11:12:02 AM

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

205