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.
Type de document :
Article dans une revue
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2014, 12 (4), pp.359-372. 〈10.1007/s10288-014-0260-9〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01105336
Contributeur : Nathalie Bostel <>
Soumis le : mardi 20 janvier 2015 - 10:50:30
Dernière modification le : mercredi 16 mai 2018 - 11:48:03

Identifiants

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〉

Partager

Métriques

Consultations de la notice

121