Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Approximation Algorithms for the Generalized Stacker Crane Problem

  • Conference paper
  • First Online:
Combinatorial Optimization and Applications (COCOA 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10627))

  • 888 Accesses

Abstract

The stacker crane problem is treated as one modified arc routing problem. This problem is to find some route for stacker cranes on a construction site such that all arcs in a mixed graph \(G=(V,E\cup A;w)\) must be traversed at least once. In the real literature, since many different building materials must be handled, we consider the generalized stacker crane (GSC) problem, and the objective of this new problem is to determine a minimum weighted tour C traversing each arc e (in A) a number of times between the lower demand and upper demand.

In this paper, we design two approximation algorithms for the GSC problem. The first algorithm uses some exact algorithm to solve the integral circulation problem, and the second algorithm uses some approximation algorithm to solve the metric traveling salesman problem. Combining these two approximation algorithms, we can design a 9/5-approximation algorithm to solve the GSC problem.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5, 88–124 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  2. Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7(2), 178–193 (1978)

    Article  MathSciNet  Google Scholar 

  3. Frederickson, G.N.: Approximation algorithms for some postman problems. J. ACM 26, 538–554 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  4. Guan, M.G.: Graphic programming using odd and even points (in Chinese). Acta Mathematica Sinica 10, 263–266 (1960). [English translation: Chinese Mathematics, 1, 273–277 (1962)]

    Google Scholar 

  5. Lenstra, J.K., Rinnooy Kan, A.H.G.: On general routing problems. Networks 6, 273–280 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  6. Orloff, C.S.: A fundamental problem in vehicle routing. Networks 4, 35–64 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  7. Papadimitriou, C.H.: On the complexity of edge traversing. J. ACM 23(3), 544–554 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  8. Raghavachari, B., Veerasamy, J.: A 3/2-approximation algorithm for the mixed postman problem. SIAM J. Discrete Math. 12(4), 425–433 (1999)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The work is supported in part by the National Natural Science Foundation of China [Nos. 11461081, 61662088, 11761078] and the Natural Science Foundation of Education Department of Yunnan Province [No. 2017ZZX235].

Author information

Authors and Affiliations

  1. Department of Mathematics, Yunnan University, Kunming, 650091, People’s Republic of China

    Jianping Li, Xiaofei Liu, Weidong Li, Li Guan & Junran Lichen

Authors
  1. Jianping Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaofei Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Weidong Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Li Guan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Junran Lichen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jianping Li .

Editor information

Editors and Affiliations

  1. Shanghai Jiao Tong University, Shanghai, China

    Xiaofeng Gao

  2. Harbin Institute of Technology, Shenzhen, China

    Hongwei Du

  3. Kennesaw State University, Kennesaw, Georgia, USA

    Meng Han

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Li, J., Liu, X., Li, W., Guan, L., Lichen, J. (2017). Approximation Algorithms for the Generalized Stacker Crane Problem. In: Gao, X., Du, H., Han, M. (eds) Combinatorial Optimization and Applications. COCOA 2017. Lecture Notes in Computer Science(), vol 10627. Springer, Cham. https://doi.org/10.1007/978-3-319-71150-8_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-71150-8_8

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-71149-2

  • Online ISBN: 978-3-319-71150-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation