Nathalie Bostel, Philippe Castagliola, Pierre Dejax and André Langevin
Article (2014)
An external link is available for this item
Show abstract
Hide abstract
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.
| Supplementary Material: | |
|---|---|
| Department: | Department of Mathematics and Industrial Engineering |
| Funders: | NSERC |
| PolyPublie URL: | https://publications.polymtl.ca/12668/ |
| Journal Title: | 4or-a Quarterly Journal of Operations Research (vol. 12, no. 4) |
| Publisher: | Springer |
| DOI: | 10.1007/s10288-014-0260-9 |
| Official URL: | https://doi.org/10.1007/s10288-014-0260-9 |
| Date Deposited: | 18 Apr 2023 15:07 |
| Last Modified: | 23 Mar 2026 15:37 |
| Cite in APA 7: | Bostel, N., Castagliola, P., Dejax, P., & Langevin, A. (2014). Approximating the length of Chinese postman tours. 4or-a Quarterly Journal of Operations Research, 12(4), 359-372. https://doi.org/10.1007/s10288-014-0260-9 |
|---|---|
Statistics
Dimensions
Repository Staff Only
|
View Item |
