IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v237y2014i3p794-801.html
   My bibliography  Save this article

A fast algorithm for identifying minimum size instances of the equivalence classes of the Pallet Loading Problem

Author

Listed:
  • Lu, Yiping
  • Cha, Jianzhong

Abstract

In this paper, a novel and fast algorithm for identifying the Minimum Size Instance (MSI) of the equivalence class of the Pallet Loading Problem (PLP) is presented. The new algorithm is based on the fact that the PLP instances of the same equivalence class have the property that the aspect ratios of their items belong to an open interval of real numbers. This interval characterises the PLP equivalence classes and is referred to as the Equivalence Ratio Interval (ERI) by authors of this paper. The time complexity of the new algorithm is two polynomial orders lower than that of the best known algorithm. The authors of this paper also suggest that the concept of MSI and its identifying algorithm can be used to transform the non-integer PLP into its equivalent integer MSI.

Suggested Citation

  • Lu, Yiping & Cha, Jianzhong, 2014. "A fast algorithm for identifying minimum size instances of the equivalence classes of the Pallet Loading Problem," European Journal of Operational Research, Elsevier, vol. 237(3), pages 794-801.
    • Handle: RePEc:eee:ejores:v:237:y:2014:i:3:p:794-801
    DOI: 10.1016/j.ejor.2014.02.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221714001234
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2014.02.008?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. E G Birgin & R D Lobato & R Morabito, 2010. "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(2), pages 306-320, February.
    2. Dowsland, Kathryn A., 1987. "An exact algorithm for the pallet loading problem," European Journal of Operational Research, Elsevier, vol. 31(1), pages 78-84, July.
    3. G, Young-Gun & Kang, Maing-Kyu, 2001. "A fast algorithm for two-dimensional pallet loading problems of large size," European Journal of Operational Research, Elsevier, vol. 134(1), pages 193-202, October.
    4. L Lins & S Lins & R Morabito, 2003. "An L-approach for packing (ℓ, w)-rectangles into rectangular and L-shaped pieces," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(7), pages 777-789, July.
    5. Letchford, Adam N. & Amaral, Andre, 2001. "Analysis of upper bounds for the Pallet Loading Problem," European Journal of Operational Research, Elsevier, vol. 132(3), pages 582-593, August.
    6. Martins, Gustavo H.A. & Dell, Robert F., 2007. "The minimum size instance of a Pallet Loading Problem equivalence class," European Journal of Operational Research, Elsevier, vol. 179(1), pages 17-26, May.
    7. Bortfeldt, Andreas & Wäscher, Gerhard, 2013. "Constraints in container loading – A state-of-the-art review," European Journal of Operational Research, Elsevier, vol. 229(1), pages 1-20.
    8. Ram, Balasubramanian, 1992. "The pallet loading problem: A survey," International Journal of Production Economics, Elsevier, vol. 28(2), pages 217-225, November.
    9. Martins, Gustavo H.A. & Dell, Robert F., 2008. "Solving the pallet loading problem," European Journal of Operational Research, Elsevier, vol. 184(2), pages 429-440, January.
    10. E G Birgin & R Morabito & F H Nishihara, 2005. "A note on an L-approach for solving the manufacturer's pallet loading problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(12), pages 1448-1451, December.
    11. Kocjan, W. & Holmström, K., 2010. "Computing stable loads for pallets," European Journal of Operational Research, Elsevier, vol. 207(2), pages 980-985, December.
    12. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sheng, Liu & Hongxia, Zhao & Xisong, Dong & Changjian, Cheng, 2016. "A heuristic algorithm for container loading of pallets with infill boxes," European Journal of Operational Research, Elsevier, vol. 252(3), pages 728-736.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. E G Birgin & R D Lobato & R Morabito, 2010. "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(2), pages 306-320, February.
    2. Martins, Gustavo H.A. & Dell, Robert F., 2008. "Solving the pallet loading problem," European Journal of Operational Research, Elsevier, vol. 184(2), pages 429-440, January.
    3. G M Ribeiro & L A N Lorena, 2008. "Optimizing the woodpulp stowage using Lagrangean relaxation with clusters," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 600-606, May.
    4. Martins, Gustavo H.A. & Dell, Robert F., 2007. "The minimum size instance of a Pallet Loading Problem equivalence class," European Journal of Operational Research, Elsevier, vol. 179(1), pages 17-26, May.
    5. Elia, Valerio & Gnoni, Maria Grazia, 2015. "Designing an effective closed loop system for pallet management," International Journal of Production Economics, Elsevier, vol. 170(PC), pages 730-740.
    6. Hugo Barros & Teresa Pereira & António G. Ramos & Fernanda A. Ferreira, 2021. "Complexity Constraint in the Distributor’s Pallet Loading Problem," Mathematics, MDPI, vol. 9(15), pages 1-20, July.
    7. McDonald, Conor M., 2016. "Integrating packaging and supply chain decisions: Selection of economic handling unit quantities," International Journal of Production Economics, Elsevier, vol. 180(C), pages 208-221.
    8. E G Birgin & J M Martínez & W F Mascarenhas & D P Ronconi, 2006. "Method of sentinels for packing items within arbitrary convex regions," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(6), pages 735-746, June.
    9. Adamos Daios & Nikolaos Kladovasilakis & Ioannis Kostavelis, 2024. "Mixed Palletizing for Smart Warehouse Environments: Sustainability Review of Existing Methods," Sustainability, MDPI, vol. 16(3), pages 1-15, February.
    10. L Lins & S Lins & R Morabito, 2003. "An L-approach for packing (ℓ, w)-rectangles into rectangular and L-shaped pieces," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(7), pages 777-789, July.
    11. Bhattacharya, Subir & Roy, Rahul & Bhattacharya, Sumita, 1998. "An exact depth-first algorithm for the pallet loading problem," European Journal of Operational Research, Elsevier, vol. 110(3), pages 610-625, November.
    12. Carlos A. Vega-Mejía & Jairo R. Montoya-Torres & Sardar M. N. Islam, 2019. "Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review," Annals of Operations Research, Springer, vol. 273(1), pages 311-375, February.
    13. Linda S. Moonen & Frits C. R. Spieksma, 2006. "Exact Algorithms for a Loading Problem with Bounded Clique Width," INFORMS Journal on Computing, INFORMS, vol. 18(4), pages 455-465, November.
    14. Letchford, Adam N. & Amaral, Andre, 2001. "Analysis of upper bounds for the Pallet Loading Problem," European Journal of Operational Research, Elsevier, vol. 132(3), pages 582-593, August.
    15. Lins, Lauro & Lins, Sostenes & Morabito, Reinaldo, 2002. "An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container," European Journal of Operational Research, Elsevier, vol. 141(2), pages 421-439, September.
    16. Bennell, Julia A. & Oliveira, Jose F., 2008. "The geometry of nesting problems: A tutorial," European Journal of Operational Research, Elsevier, vol. 184(2), pages 397-415, January.
    17. Arenales, Marcos & Morabito, Reinaldo, 1995. "An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems," European Journal of Operational Research, Elsevier, vol. 84(3), pages 599-617, August.
    18. Lehnfeld, Jana & Knust, Sigrid, 2014. "Loading, unloading and premarshalling of stacks in storage areas: Survey and classification," European Journal of Operational Research, Elsevier, vol. 239(2), pages 297-312.
    19. German Pantoja-Benavides & Daniel Giraldo & Ana Montes & Andrea García & Carlos Rodríguez & César Marín & David Álvarez-Martínez, 2024. "Comprehensive Review of Robotized Freight Packing," Logistics, MDPI, vol. 8(3), pages 1-24, July.
    20. Hadjiconstantinou, Eleni & Christofides, Nicos, 1995. "An exact algorithm for general, orthogonal, two-dimensional knapsack problems," European Journal of Operational Research, Elsevier, vol. 83(1), pages 39-56, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:237:y:2014:i:3:p:794-801. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.