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

A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach

Author

Listed:
  • Wang, Zhoujing
  • Li, Kevin W.
  • Levy, Jason K.

Abstract

Increasing fuel costs, post-911 security concerns, and economic globalization provide a strong incentive for container carriers to use available container space more efficiently, thereby minimizing the number of container trips and reducing socio-economic vulnerability. A heuristic algorithm based on a tertiary tree model is proposed to handle the container loading problem (CLP) with weakly heterogeneous boxes. A dynamic space decomposition method based on the tertiary tree structure is developed to partition the remaining container space after a block of homogeneous rectangular boxes is loaded into a container. This decomposition approach, together with an optimal-fitting sequencing and an inner-right-corner-occupying placement rule, permits a holistic loading strategy to pack a container. Comparative studies with existing algorithms and an illustrative example demonstrate the efficiency of this algorithm.

Suggested Citation

  • Wang, Zhoujing & Li, Kevin W. & Levy, Jason K., 2008. "A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach," European Journal of Operational Research, Elsevier, vol. 191(1), pages 86-99, November.
    • Handle: RePEc:eee:ejores:v:191:y:2008:i:1:p:86-99
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)00888-0
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Bischoff, E. E. & Ratcliff, M. S. W., 1995. "Issues in the development of approaches to container loading," Omega, Elsevier, vol. 23(4), pages 377-390, August.
    2. Bischoff, E. E. & Janetz, F. & Ratcliff, M. S. W., 1995. "Loading pallets with non-identical items," European Journal of Operational Research, Elsevier, vol. 84(3), pages 681-692, August.
    3. Bortfeldt, Andreas & Gehring, Hermann, 2001. "A hybrid genetic algorithm for the container loading problem," European Journal of Operational Research, Elsevier, vol. 131(1), pages 143-161, May.
    4. Terno, Johannes & Scheithauer, Guntram & Sommerwei[ss], Uta & Riehme, Jan, 2000. "An efficient approach for the multi-pallet loading problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 372-381, June.
    5. Pisinger, David, 2002. "Heuristics for the container loading problem," European Journal of Operational Research, Elsevier, vol. 141(2), pages 382-392, September.
    6. Davies, A. Paul & Bischoff, Eberhard E., 1999. "Weight distribution considerations in container loading," European Journal of Operational Research, Elsevier, vol. 114(3), pages 509-527, May.
    7. Eley, Michael, 2002. "Solving container loading problems by block arrangement," European Journal of Operational Research, Elsevier, vol. 141(2), pages 393-409, September.
    8. Bischoff, E.E., 2006. "Three-dimensional packing of items with limited load bearing strength," European Journal of Operational Research, Elsevier, vol. 168(3), pages 952-966, February.
    9. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    10. Zhihong Jin & Katsuhisa Ohno & Jiali Du, 2004. "An Efficient Approach For The Three-Dimensional Container Packing Problem With Practical Constraints," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 21(03), pages 279-295.
    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. Y Wu, 2011. "Modelling of containerized air cargo forwarding problems under uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1211-1226, July.
    2. Xianbo Xiang & Caoyang Yu & He Xu & Stuart X. Zhu, 2018. "Optimization of Heterogeneous Container Loading Problem with Adaptive Genetic Algorithm," Complexity, Hindawi, vol. 2018, pages 1-12, November.
    3. Lu, Hao-Chun & Huang, Yao-Huei, 2015. "An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry," European Journal of Operational Research, Elsevier, vol. 246(1), pages 51-65.
    4. 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.
    5. 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.
    6. Li, Yanzhi & Tao, Yi & Wang, Fan, 2009. "A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning," European Journal of Operational Research, Elsevier, vol. 199(2), pages 553-560, December.
    7. Ren, Jidong & Tian, Yajie & Sawaragi, Tetsuo, 2011. "A tree search method for the container loading problem with shipment priority," European Journal of Operational Research, Elsevier, vol. 214(3), pages 526-535, November.

    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. 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.
    2. Bischoff, E.E., 2006. "Three-dimensional packing of items with limited load bearing strength," European Journal of Operational Research, Elsevier, vol. 168(3), pages 952-966, February.
    3. Lim, Andrew & Ma, Hong & Qiu, Chaoyang & Zhu, Wenbin, 2013. "The single container loading problem with axle weight constraints," International Journal of Production Economics, Elsevier, vol. 144(1), pages 358-369.
    4. Zhu, Wenbin & Lim, Andrew, 2012. "A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem," European Journal of Operational Research, Elsevier, vol. 222(3), pages 408-417.
    5. Huang, Wenqi & He, Kun, 2009. "A caving degree approach for the single container loading problem," European Journal of Operational Research, Elsevier, vol. 196(1), pages 93-101, July.
    6. Araya, Ignacio & Moyano, Mauricio & Sanchez, Cristobal, 2020. "A beam search algorithm for the biobjective container loading problem," European Journal of Operational Research, Elsevier, vol. 286(2), pages 417-431.
    7. Ren, Jidong & Tian, Yajie & Sawaragi, Tetsuo, 2011. "A tree search method for the container loading problem with shipment priority," European Journal of Operational Research, Elsevier, vol. 214(3), pages 526-535, November.
    8. F. Parreño & R. Alvarez-Valdes & J. M. Tamarit & J. F. Oliveira, 2008. "A Maximal-Space Algorithm for the Container Loading Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 412-422, August.
    9. 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.
    10. 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.
    11. Ramos, António G. & Silva, Elsa & Oliveira, José F., 2018. "A new load balance methodology for container loading problem in road transportation," European Journal of Operational Research, Elsevier, vol. 266(3), pages 1140-1152.
    12. M-K Kang & C-S Jang & K-S Yoon, 2010. "Heuristics with a new block strategy for the single and multiple containers loading problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 95-107, January.
    13. Andreas Bortfeldt & Gerhard Wäscher, 2012. "Container Loading Problems - A State-of-the-Art Review," FEMM Working Papers 120007, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    14. Wang, Ning & Lim, Andrew & Zhu, Wenbin, 2013. "A multi-round partial beam search approach for the single container loading problem with shipment priority," International Journal of Production Economics, Elsevier, vol. 145(2), pages 531-540.
    15. Tobias Fanslau & Andreas Bortfeldt, 2010. "A Tree Search Algorithm for Solving the Container Loading Problem," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 222-235, May.
    16. Tian, Tian & Zhu, Wenbin & Lim, Andrew & Wei, Lijun, 2016. "The multiple container loading problem with preference," European Journal of Operational Research, Elsevier, vol. 248(1), pages 84-94.
    17. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    18. Galrão Ramos, A. & Oliveira, José F. & Gonçalves, José F. & Lopes, Manuel P., 2016. "A container loading algorithm with static mechanical equilibrium stability constraints," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 565-581.
    19. T N Wong & P S Chow & D Sculli, 2006. "A heuristic for sea-freight container selection, cargo allocation and cargo orientation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(12), pages 1452-1463, December.
    20. Gajda, Mikele & Trivella, Alessio & Mansini, Renata & Pisinger, David, 2022. "An optimization approach for a complex real-life container loading problem," Omega, Elsevier, vol. 107(C).

    More about this item

    Statistics

    Access and download statistics

    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:191:y:2008:i:1:p:86-99. 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.