IDEAS home Printed from https://ideas.repec.org/a/spr/cejnor/v19y2011i3p371-389.html
   My bibliography  Save this article

Constructive heuristics for the canister filling problem

Author

Listed:
  • Gašper Žerovnik
  • Janez Žerovnik

Abstract

The canister filling problem arises when optimizing the spent nuclear fuel repository in hard rock. It is shown the problem is NP-hard. Constructive heuristics followed by remove and reinsert local optimization are considered. Additionally, some theoretical insight on the algorithm operation is provided. Several variants of the algorithm are compared on random and realistic datasets. The obtained results have shown that constructive heuristics give satisfactory results for both random and realistic input data, although there is still some room for improvements. Copyright Springer-Verlag 2011

Suggested Citation

  • Gašper Žerovnik & Janez Žerovnik, 2011. "Constructive heuristics for the canister filling problem," 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. 19(3), pages 371-389, September.
    • Handle: RePEc:spr:cejnor:v:19:y:2011:i:3:p:371-389
    DOI: 10.1007/s10100-010-0164-5
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10100-010-0164-5
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10100-010-0164-5?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. Giorgia Oggioni & Yves Smeers, 2009. "Evaluating the impact of average cost based contracts on the industrial sector in the European emission trading scheme," 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. 17(2), pages 181-217, June.
    2. 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.
    3. Polyakovsky, Sergey & M'Hallah, Rym, 2009. "An agent-based approach to the two-dimensional guillotine bin packing problem," European Journal of Operational Research, Elsevier, vol. 192(3), pages 767-781, February.
    4. Wu, Yong & Li, Wenkai & Goh, Mark & de Souza, Robert, 2010. "Three-dimensional bin packing problem with variable bin height," European Journal of Operational Research, Elsevier, vol. 202(2), pages 347-355, April.
    5. Crainic, Teodor Gabriel & Perboli, Guido & Tadei, Roberto, 2009. "TS2PACK: A two-level tabu search for the three-dimensional bin packing problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 744-760, June.
    6. Kenmochi, Mitsutoshi & Imamichi, Takashi & Nonobe, Koji & Yagiura, Mutsunori & Nagamochi, Hiroshi, 2009. "Exact algorithms for the two-dimensional strip packing problem with and without rotations," European Journal of Operational Research, Elsevier, vol. 198(1), pages 73-83, October.
    7. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    8. OGGIONI, Giorgia & SMEERS, Yves, 2009. "Evaluating the impact of average cost based contracts on the industrial sector in the European emission trading scheme," LIDAM Reprints CORE 2118, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Raphaële Thery & Pascale Zarate, 2009. "Energy planning: a multi-level and multicriteria decision making structure proposal," 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. 17(3), pages 265-274, September.
    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. Tibor Csendes & Janez Povh & Lidija Stirn & Janez Žerovnik, 2011. "Editorial," 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. 19(3), pages 251-252, September.
    2. Andrej Kastrin & Janez Povh & Lidija Zadnik Stirn & Janez Žerovnik, 2021. "Methodologies and applications for resilient global development from the aspect of SDI-SOR special issues of CJOR," 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. 29(3), pages 773-790, September.
    3. Žerovnik Janez, 2015. "Heuristics for NP-hard optimization problems - simpler is better!?," Logistics, Supply Chain, Sustainability and Global Challenges, Sciendo, vol. 6(1), pages 1-10, 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. Castro, Pedro M. & Oliveira, José F., 2011. "Scheduling inspired models for two-dimensional packing problems," European Journal of Operational Research, Elsevier, vol. 215(1), pages 45-56, November.
    2. Leung, Stephen C.H. & Zhang, Defu & Sim, Kwang Mong, 2011. "A two-stage intelligent search algorithm for the two-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 57-69, November.
    3. Andreas Bortfeldt & Sabine Jungmann, 2012. "A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint," Annals of Operations Research, Springer, vol. 196(1), pages 53-71, July.
    4. Gardeyn, Jeroen & Wauters, Tony, 2022. "A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints," European Journal of Operational Research, Elsevier, vol. 301(2), pages 432-444.
    5. de Queiroz, Thiago A. & Miyazawa, Flávio K., 2013. "Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints," International Journal of Production Economics, Elsevier, vol. 145(2), pages 511-530.
    6. Jean-François Côté & Manuel Iori, 2018. "The Meet-in-the-Middle Principle for Cutting and Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 646-661, November.
    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. Setzer, Thomas & Bichler, Martin, 2013. "Using matrix approximation for high-dimensional discrete optimization problems: Server consolidation based on cyclic time-series data," European Journal of Operational Research, Elsevier, vol. 227(1), pages 62-75.
    9. Hawa, Asyl L. & Lewis, Rhyd & Thompson, Jonathan M., 2022. "Exact and approximate methods for the score-constrained packing problem," European Journal of Operational Research, Elsevier, vol. 302(3), pages 847-859.
    10. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2011. "A skyline heuristic for the 2D rectangular packing and strip packing problems," European Journal of Operational Research, Elsevier, vol. 215(2), pages 337-346, December.
    11. Zhu, Wenbin & Huang, Weili & Lim, Andrew, 2012. "A prototype column generation strategy for the multiple container loading problem," European Journal of Operational Research, Elsevier, vol. 223(1), pages 27-39.
    12. 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.
    13. Thiago Queiroz & Flávio Miyazawa, 2014. "Order and static stability into the strip packing problem," Annals of Operations Research, Springer, vol. 223(1), pages 137-154, December.
    14. Gzara, Fatma & Elhedhli, Samir & Yildiz, Burak C., 2020. "The Pallet Loading Problem: Three-dimensional bin packing with practical constraints," European Journal of Operational Research, Elsevier, vol. 287(3), pages 1062-1074.
    15. Braam, Florian & van den Berg, Daan, 2022. "Which rectangle sets have perfect packings?," Operations Research Perspectives, Elsevier, vol. 9(C).
    16. Önder Aşık & Ender Özcan, 2009. "Bidirectional best-fit heuristic for orthogonal rectangular strip packing," Annals of Operations Research, Springer, vol. 172(1), pages 405-427, November.
    17. Tang, Ling & Wang, Haohan & Li, Ling & Yang, Kaitong & Mi, Zhifu, 2020. "Quantitative models in emission trading system research: A literature review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 132(C).
    18. Wei, Lijun & Hu, Qian & Lim, Andrew & Liu, Qiang, 2018. "A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem," European Journal of Operational Research, Elsevier, vol. 270(2), pages 448-474.
    19. Martinez-Sykora, Antonio & Alvarez-Valdes, Ramon & Bennell, Julia & Tamarit, Jose Manuel, 2015. "Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts," Omega, Elsevier, vol. 52(C), pages 15-32.
    20. Francesca Bonenti & Giorgia Oggioni & Elisabetta Allevi & Giacomo Marangoni, 2011. "Evaluating the Impacts of the EU-ETS on Prices, Investments and Profits of the Italian Electricity Market," Working Papers 2011.99, Fondazione Eni Enrico Mattei.

    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:spr:cejnor:v:19:y:2011:i:3:p:371-389. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.