| Article ID: | iaor20171826 |
| Volume: | 12 |
| Issue: | 4 |
| Start Page Number: | 359 |
| End Page Number: | 372 |
| Publication Date: | Dec 2014 |
| Journal: | 4OR |
| Authors: | Langevin Andr, Dejax Pierre, Bostel Nathalie, Castagliola Philippe |
| Keywords: | combinatorial optimization, programming: travelling salesman, heuristics |
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.