[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Bin Packing Problem with Mixing Constraints for Containerizing Items for Logistics Service Providers

  • Conference paper
  • First Online:
Computational Logistics (ICCL 2020)

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

Included in the following conference series:

Abstract

Large logistics service providers often need to containerize and route thousands or millions of items per year. In practice, companies specify business rules of how to pack and transport items from their origin to destination. Handling and respecting those business rules manually is a complex and time-consuming task. We propose a variant of the variable sized bin packing problem applicable to the containerization process occurring at logistics service providers. This novel model variant extends the bin packing problem with color constraints by adding multiple item mixing constraints. We present a binary integer program along with a first-fit decreasing heuristic and compare the performance on instances from a global logistics service provider. The numerical results indicate promising results to solve this computationally hard combinatorial optimization 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
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 71.50
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 89.99
Price includes VAT (United Kingdom)
  • 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

Notes

  1. 1.

    Uniqueness indicates how many items are sharing the same property value in percent, averaged over all rules of the instances.

  2. 2.

    We define MIP gap as \(\frac{|best\_bound - incumbent|}{max(|best\_bound|, |incumbent|)}\).

References

  1. Belov, G., Scheithauer, G.: A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Euro. J. Oper. Res. 141(2), 274–294 (2002)

    Article  MathSciNet  Google Scholar 

  2. Capua, R., Frota, Y., Ochi, L.S., Vidal, T.: A study on exponential-size neighborhoods for the bin packing problem with conflicts. J. Heuristics 24(4), 667–695 (2018). https://doi.org/10.1007/s10732-018-9372-2

    Article  Google Scholar 

  3. Christensen, H.I., Khan, A., Pokutta, S., Tetali, P.: Approximation and online algorithms for multidimensional bin packing: a survey. Comput. Sci. Rev. 24, 63–79 (2017)

    Article  MathSciNet  Google Scholar 

  4. Coffman, E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D.: Bin packing approximation algorithms: survey and classification. In: Pardalos, P.M., Du, D.-Z., Graham, R.L. (eds.) Handbook of Combinatorial Optimization, pp. 455–531. Springer, New York (2013). https://doi.org/10.1007/978-1-4419-7997-1_35

    Chapter  Google Scholar 

  5. Coffman, E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin-packing — an updated survey. In: Ausiello, G., Lucertini, M., Serafini, P. (eds.) Algorithm Design for Computer System Design. ICMS, vol. 284, pp. 49–106. Springer, Vienna (1984). https://doi.org/10.1007/978-3-7091-4338-4_3

    Chapter  Google Scholar 

  6. Coffman, E.G., Garey, M., Johnson, D.: Approximation algorithms for bin packing: a survey. Approximation algorithms for NP-hard problems, pp. 46–93 (1996)

    Google Scholar 

  7. Crévits, I., Hanafı, S., Mahjoub, A.R., Taktak, R., Wilbaut, C.: A special case of variable-sized bin packing problem with color constraints. In: 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT), pp. 1150–1154. IEEE (2019)

    Google Scholar 

  8. Dawande, M., Kalagnanam, J., Sethuraman, J.: Variable sized bin packing with color constraints. Electron. Notes Discrete Math. 7, 154–157 (2001)

    Article  MathSciNet  Google Scholar 

  9. Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Euro. J. Oper. Res. 255(1), 1–20 (2016)

    Article  MathSciNet  Google Scholar 

  10. Delorme, M., Iori, M., Martello, S.: Bpplib: a library for bin packing and cutting stock problems. Optimization Lett. 12(2), 235–250 (2018)

    Article  MathSciNet  Google Scholar 

  11. Epstein, L., Levin, A.: On bin packing with conflicts. SIAM J. Optimization 19(3), 1270–1298 (2008)

    Article  MathSciNet  Google Scholar 

  12. Fasano, G.: A mip approach for some practical packing problems: balancing constraints and tetris-like items. Q. J. Belgian, French and Italian Oper. Res. Soc. 2(2), 161–174 (2004)

    MathSciNet  MATH  Google Scholar 

  13. Friesen, D.K., Langston, M.A.: Variable sized bin packing. SIAM J. Comput. 15(1), 222–230 (1986)

    Article  Google Scholar 

  14. Haouari, M., Serairi, M.: Heuristics for the variable sized bin-packing problem. Comput. Oper. Res. 36(10), 2877–2884 (2009)

    Article  MathSciNet  Google Scholar 

  15. Johnson, D.S.: Near-optimal bin packing algorithms. Ph.D. thesis, Massachusetts Institute of Technology (1973)

    Google Scholar 

  16. Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3(4), 299–325 (1974)

    Article  MathSciNet  Google Scholar 

  17. Kang, J., Park, S.: Algorithms for the variable sized bin packing problem. Euro. J. Oper. Res. 147(2), 365–372 (2003)

    Article  MathSciNet  Google Scholar 

  18. Kochetov, Y., Kondakov, A.: Vns matheuristic for a bin packing problem with a color constraint. Electron. Notes Discrete Math. 58, 39–46 (2017)

    Article  MathSciNet  Google Scholar 

  19. Kondakov, A., Kochetov, Y.: A core heuristic and the branch-and-price method for a bin packing problem with a color constraint. In: Eremeev, A., Khachay, M., Kochetov, Y., Pardalos, P. (eds.) OPTA 2018. CCIS, vol. 871, pp. 309–320. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93800-4_25

    Chapter  Google Scholar 

  20. Korte, B., Vygen, J.: Bin-Packing, pp. 407–422. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-76919-4_18

  21. Levine, J., Ducatelle, F.: Ant colony optimization and local search for bin packing and cutting stock problems. J. Oper. Res. Soc. 55(7), 705–716 (2004)

    Article  Google Scholar 

  22. Martello, S., Toth, P.: Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimization (1990)

    Google Scholar 

  23. Pisinger, D., Sigurd, M.: The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optimization 2(2), 154–167 (2005)

    Article  MathSciNet  Google Scholar 

  24. Sadykov, R., Vanderbeck, F.: Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J. Comput. 25(2), 244–255 (2013)

    Article  MathSciNet  Google Scholar 

  25. Statista Research Department: Estimated containerized cargo flows on major container trade routes in 2018, by trade route (in million teus). Accessed May 2020. https://www.statista.com/statistics/253988/estimated-containerized-cargo-flows-on-major-container-trade-routes/

  26. UN Conference on Trade and Development: Review of maritime transport 2013. Technical report, United Nations (2013)

    Google Scholar 

  27. World Shipping Council: World shipping council trade statistics. Accessed May 2020. http://www.worldshipping.org/about-the-industry/global-trade/trade-statistics

Download references

Author information

Authors and Affiliations

  1. A.P. Moller Maersk R&D, Bangalore, India

    Sajini Anand

  2. A.P. Moller Maersk R&D, Copenhagen, Denmark

    Stefan Guericke

Authors
  1. Sajini Anand
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stefan Guericke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sajini Anand .

Editor information

Editors and Affiliations

  1. University of Twente, Enschede, The Netherlands

    Eduardo Lalla-Ruiz

  2. University of Twente, Enschede, The Netherlands

    Martijn Mes

  3. University of Hamburg, Hamburg, Germany

    Stefan Voß

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Anand, S., Guericke, S. (2020). A Bin Packing Problem with Mixing Constraints for Containerizing Items for Logistics Service Providers. In: Lalla-Ruiz, E., Mes, M., Voß, S. (eds) Computational Logistics. ICCL 2020. Lecture Notes in Computer Science(), vol 12433. Springer, Cham. https://doi.org/10.1007/978-3-030-59747-4_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-59747-4_22

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-59746-7

  • Online ISBN: 978-3-030-59747-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation