iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/S10288-014-0260-9
Approximating the length of Chinese postman tours | 4OR Skip to main content
Springer Nature Link
Log in

Approximating the length of Chinese postman tours

  • Research paper
  • Published:
4OR Aims and scope Submit manuscript

An Erratum to this article was published on 27 May 2017

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. http://www.mpi-inf.mpg.de/LEDA/.

  2. http://mathsrv.ku-eichstaett.de/MGF/homes/grothmann/java/TSP/.

  3. http://www.scicoslab.org/.

References

  • Beardwood J, Halton J, Hammersley J (1959) The shortest path through many points. Math Proc Cambr Philos Soc 55(4):299–327

    Article  Google Scholar 

  • Box G, Cox D (1964) An analysis of transformations. J R Stat Soc Ser B 26(2):211–252

    Google Scholar 

  • Butsch A, Kalcsics J, Laporte G (2013) Districting for arc routing. Tech. rep, Karlsruhe Institute of Technology

  • Christofides N, Eilon S (1969) Expected distances in distribution problems. Oper Res Q 20(4):437–443

    Article  Google Scholar 

  • Daganzo C (1984a) The distance travelled to visit \(n\) points with a maximum of \(c\) stops per vehicle: an analytic model and an application. Transp Sci 18(4):331–350

    Article  Google Scholar 

  • Daganzo C (1984b) The length of tours in zones of different shapes. Transp Res B Methodol 18(2):135–145

    Article  Google Scholar 

  • Daganzo C (2005) Logistics systems analysis. Lecture notes in economics and mathematical systems, vol 36, 4th edn. Springer, Berlin

  • Edmonds J (1965) Paths, trees, and flowers. Can J Math 17:449–467

    Article  Google Scholar 

  • Eilon S, Watson-Gandy C, Christofides N (1971) Distribution management: mathematical modelling and practical analysis, vol 36. Hafner, New York

    Google Scholar 

  • Geoffrion A (1976) The purpose of mathematical programming is insight not numbers. Interfaces 7(1):81–92

    Article  Google Scholar 

  • Guan M (1962) Graphic programming using odd and even points. Chin Math 1:273–277

    Google Scholar 

  • Hall R (1986) Discrete models/continuous models. Omega Int J Manag Sci 14(3):213–220

    Article  Google Scholar 

  • Langevin A, Mbaraga P, Campbell J (1996) Continuous approximation models in freight distribution: an overview. Transp Res Part B Methodol 30(3):163–188

    Article  Google Scholar 

  • Muyldermans L (2013) District and sector design for arc routing applications. In: Worshop on arc mouting problems 1 (WARP 1), Copenhagen

  • Nelder J, Mead R (1965) A simplex method for function minimization. Comput J 7(4):308–313

    Article  Google Scholar 

  • Newell G (1973) Scheduling, location, transportation and continuum mechanics: some simple approximations to optimization problems. SIAM J Appl Math 25(3):346–360

    Article  Google Scholar 

Download references

Acknowledgments

The authors wish to thank Mr. Thomas Pleyber for his contribution to develop the graph generator.

Author information

Authors and Affiliations

  1. LUNAM Université, Université de Nantes, IRCCyN UMR CNRS 6597, Nantes, France

    Nathalie Bostel & Philippe Castagliola

  2. LUNAM Université, École des Mines de Nantes, IRCCyN UMR CNRS 6597, Nantes, France

    Pierre Dejax

  3. Department of Mathematics and Industrial Engineering, CIRRELT, École Polytechnique de Montréal, Montreal, QC, Canada

    André Langevin

Authors
  1. Nathalie Bostel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philippe Castagliola
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pierre Dejax
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. André Langevin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Philippe Castagliola.

Additional information

The authors wish to acknowledge the support of CPCFQ (Commission Permanente de Coopération Franco-Québécoise) and of the Natural Sciences and Engineering Research Council of Canada.

An erratum to this article is available at http://dx.doi.org/10.1007/s10288-017-0346-2.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bostel, N., Castagliola, P., Dejax, P. et al. Approximating the length of Chinese postman tours. 4OR-Q J Oper Res 12, 359–372 (2014). https://doi.org/10.1007/s10288-014-0260-9

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10288-014-0260-9

Keywords

Mathematics Subject Classification

Search

Navigation