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

Complexity results for storage loading problems with stacking constraints

Author

Listed:
  • Bruns, Florian
  • Knust, Sigrid
  • Shakhlevich, Natalia V.

Abstract

In this paper, we present complexity results for storage loading problems where the storage area is organized in fixed stacks with a limited common height. Such problems appear in several practical applications, e.g., in the context of container terminals, container ships or warehouses. Incoming items arriving at a storage area have to be assigned to stacks so that certain constraints are respected (e.g., not every item may be stacked on top of every other item). We study structural properties of the general model and special cases where at most two or three items can be stored in each stack. Besides providing polynomial time algorithms for some of these problems, we establish the boundary to NP-hardness.

Suggested Citation

  • Bruns, Florian & Knust, Sigrid & Shakhlevich, Natalia V., 2016. "Complexity results for storage loading problems with stacking constraints," European Journal of Operational Research, Elsevier, vol. 249(3), pages 1074-1081.
    • Handle: RePEc:eee:ejores:v:249:y:2016:i:3:p:1074-1081
    DOI: 10.1016/j.ejor.2015.09.036
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221715008784
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2015.09.036?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. Ballis, Athanasios & Golias, John, 2002. "Comparative evaluation of existing and innovative rail-road freight transport terminals," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(7), pages 593-611, August.
    2. Kim, Kap Hwan & Park, Young Man & Ryu, Kwang-Ryul, 2000. "Deriving decision rules to locate export containers in container yards," European Journal of Operational Research, Elsevier, vol. 124(1), pages 89-101, July.
    3. 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.
    4. Delgado, Alberto & Jensen, Rune Møller & Janstrup, Kira & Rose, Trine Høyer & Andersen, Kent Høj, 2012. "A Constraint Programming model for fast optimal stowage of container vessel bays," European Journal of Operational Research, Elsevier, vol. 220(1), pages 251-261.
    5. Caserta, Marco & Schwarze, Silvia & Voß, Stefan, 2012. "A mathematical formulation and complexity considerations for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 219(1), pages 96-104.
    6. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    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. Christina Büsing & Sigrid Knust & Xuan Thanh Le, 2018. "Trade-off between robustness and cost for a storage loading problem: rule-based scenario generation," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(4), pages 339-365, December.
    2. Liu, Weimiao & Deng, Tianhu & Li, Jianbin, 2019. "Product packing and stacking under uncertainty: A robust approach," European Journal of Operational Research, Elsevier, vol. 277(3), pages 903-917.
    3. Zhongbin Zhao & Xifu Wang & Suxin Cheng & Wei Liu & Lijun Jiang, 2022. "A New Synchronous Handling Technology of Double Stack Container Trains in Sea-Rail Intermodal Terminals," Sustainability, MDPI, vol. 14(18), pages 1-18, September.
    4. Damla Kizilay & Deniz Türsel Eliiyi, 2021. "A comprehensive review of quay crane scheduling, yard operations and integrations thereof in container terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(1), pages 1-42, March.
    5. Gharehgozli, Amir & Zaerpour, Nima, 2018. "Stacking outbound barge containers in an automated deep-sea terminal," European Journal of Operational Research, Elsevier, vol. 267(3), pages 977-995.
    6. Amir Gharehgozli & Debjit Roy & Suruchika Saini & Jan-Kees Ommeren, 2023. "Loading and unloading trains at the landside of container terminals," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 25(3), pages 549-575, September.
    7. Feng, Yuanjun & Song, Dong-Ping & Li, Dong, 2022. "Smart stacking for import containers using customer information at automated container terminals," European Journal of Operational Research, Elsevier, vol. 301(2), pages 502-522.
    8. Goerigk, Marc & Knust, Sigrid & Le, Xuan Thanh, 2016. "Robust storage loading problems with stacking and payload constraints," European Journal of Operational Research, Elsevier, vol. 253(1), pages 51-67.
    9. Gharehgozli, Amir & Yu, Yugang & de Koster, René & Du, Shaofu, 2019. "Sequencing storage and retrieval requests in a container block with multiple open locations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 261-284.
    10. Gharehgozli, Amir Hossein & Vernooij, Floris Gerardus & Zaerpour, Nima, 2017. "A simulation study of the performance of twin automated stacking cranes at a seaport container terminal," European Journal of Operational Research, Elsevier, vol. 261(1), pages 108-128.
    11. Gharehgozli, Amir & Zaerpour, Nima, 2020. "Robot scheduling for pod retrieval in a robotic mobile fulfillment system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    12. El Yaagoubi, Amina & Ferjani, Aicha & Essaghir, Yasmina & Sheikhahmadi, Farrokh & Abourraja, Mohamed Nezar & Boukachour, Jaouad & Baron, Marie-Laure & Duvallet, Claude & Khodadad-Saryazdi, Ali, 2022. "A logistic model for a french intermodal rail/road freight transportation system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).

    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. Boysen, Nils & Emde, Simon, 2016. "The parallel stack loading problem to minimize blockages," European Journal of Operational Research, Elsevier, vol. 249(2), pages 618-627.
    2. Goerigk, Marc & Knust, Sigrid & Le, Xuan Thanh, 2016. "Robust storage loading problems with stacking and payload constraints," European Journal of Operational Research, Elsevier, vol. 253(1), pages 51-67.
    3. Boschma, René & Mes, Martijn R.K. & de Vries, Leon R., 2023. "Approximate dynamic programming for container stacking," European Journal of Operational Research, Elsevier, vol. 310(1), pages 328-342.
    4. 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.
    5. Feng, Yuanjun & Song, Dong-Ping & Li, Dong & Zeng, Qingcheng, 2020. "The stochastic container relocation problem with flexible service policies," Transportation Research Part B: Methodological, Elsevier, vol. 141(C), pages 116-163.
    6. Ting, Ching-Jung & Wu, Kun-Chih, 2017. "Optimizing container relocation operations at container yards with beam search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 17-31.
    7. Juan P. Cavada & Cristián E. Cortés & Pablo A. Rey, 2023. "Comparing allocation and relocation policies at a logistics service container terminal: a discrete-event simulation approach," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(4), pages 1281-1316, December.
    8. Huiling Zhu & Mingjun Ji & Wenwen Guo & Qingbin Wang & Yongzhi Yang, 2019. "Mathematical formulation and heuristic algorithm for the block relocation and loading problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(4), pages 333-351, June.
    9. Gharehgozli, A.H. & Roy, D. & de Koster, M.B.M., 2014. "Sea Container Terminals," ERIM Report Series Research in Management ERS-2014-009-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    10. Ruiyou Zhang & Shixin Liu & Herbert Kopfer, 2016. "Tree search procedures for the blocks relocation problem with batch moves," Flexible Services and Manufacturing Journal, Springer, vol. 28(3), pages 397-424, September.
    11. Zhang, Canrong & Guan, Hao & Yuan, Yifei & Chen, Weiwei & Wu, Tao, 2020. "Machine learning-driven algorithms for the container relocation problem," Transportation Research Part B: Methodological, Elsevier, vol. 139(C), pages 102-131.
    12. Boge, Sven & Goerigk, Marc & Knust, Sigrid, 2020. "Robust optimization for premarshalling with uncertain priority classes," European Journal of Operational Research, Elsevier, vol. 287(1), pages 191-210.
    13. Lennart Zey & Dirk Briskorn & Nils Boysen, 2022. "Twin-crane scheduling during seaside workload peaks with a dedicated handshake area," Journal of Scheduling, Springer, vol. 25(1), pages 3-34, February.
    14. Zehendner, Elisabeth & Caserta, Marco & Feillet, Dominique & Schwarze, Silvia & Voß, Stefan, 2015. "An improved mathematical formulation for the blocks relocation problem," European Journal of Operational Research, Elsevier, vol. 245(2), pages 415-422.
    15. Nils Boysen & Malte Fliedner & Florian Jaehn & Erwin Pesch, 2013. "A Survey on Container Processing in Railway Yards," Transportation Science, INFORMS, vol. 47(3), pages 312-329, August.
    16. Jonas Ahmt & Jonas Skott Sigtenbjerggaard & Richard Martin Lusby & Jesper Larsen & David Ryan, 2016. "A new approach to the Container Positioning Problem," Flexible Services and Manufacturing Journal, Springer, vol. 28(4), pages 617-643, December.
    17. Nils Boysen & Simon Emde & Malte Fliedner, 2016. "The basic train makeup problem in shunting yards," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 207-233, January.
    18. Gharehgozli, Amir & Yu, Yugang & de Koster, René & Du, Shaofu, 2019. "Sequencing storage and retrieval requests in a container block with multiple open locations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 125(C), pages 261-284.
    19. El Yaagoubi, Amina & Ferjani, Aicha & Essaghir, Yasmina & Sheikhahmadi, Farrokh & Abourraja, Mohamed Nezar & Boukachour, Jaouad & Baron, Marie-Laure & Duvallet, Claude & Khodadad-Saryazdi, Ali, 2022. "A logistic model for a french intermodal rail/road freight transportation system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    20. Basallo-Triana, Mario José & Bravo-Bastidas, Juan José & Vidal-Holguín, Carlos Julio, 2022. "A rail-road transshipment yard picture," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 159(C).

    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:249:y:2016:i:3:p:1074-1081. 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.