Approximating the length of Chinese postman tours - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue 4OR: A Quarterly Journal of Operations Research Année : 2014

Approximating the length of Chinese postman tours

Résumé

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.
Fichier non déposé

Dates et versions

hal-01105336 , version 1 (20-01-2015)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More