IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v11y2023i14p3219-d1199859.html
   My bibliography  Save this article

An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict

Author

Listed:
  • Walaa H. El-Ashmawi

    (Faculty of Computers and Informatics, Suez Canal University, Ismailia 41522, Egypt
    Faculty of Computer Science, Misr International University, Cairo 44971, Egypt
    These authors contributed equally to this work.)

  • Ahmad Salah

    (Faculty of Computers and Informatics, Zagazig University, Sharkia 44519, Egypt
    College of Computing and Information Sciences, University of Technology and Applied Sciences, Ibri P.O. Box 466, Oman
    These authors contributed equally to this work.)

  • Mahmoud Bekhit

    (University of Technology Sydney (UTS), Sydney, NSW 2007, Australia
    Australian Catholic University, Sydney, NSW 2059, Australia
    Kaplan Business School, Sydney, NSW 2000, Australia
    These authors contributed equally to this work.)

  • Guoqing Xiao

    (College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
    The National Supercomputing Center in Changsha, Changsha 410082, China)

  • Khalil Al Ruqeishi

    (Mathematical and Physical Sciences Department, College of Arts and Sciences, University of Nizwa, Nizwa P.O. Box 33, Oman)

  • Ahmed Fathalla

    (Department of Mathematics, Faculty of Science, Suez Canal University, Ismailia 41522, Egypt)

Abstract

The bin packing problem (BPP) is a classic combinatorial optimization problem with several variations. The BPP with conflicts (BPPCs) is not a well-investigated variation. In the BPPC, there are conditions that prevent packing some items together in the same bin. There are very limited efforts utilizing metaheuristic methods to address the BPPC. The current methods only pack the conflict items only and then start a new normal BPP for the non-conflict items; thus, there are two stages to address the BPPC. In this work, an adaption of the jellyfish metaheuristic has been proposed to solve the BPPC in one stage (i.e., packing the conflict and non-conflict items together) by defining the jellyfish operations in the context of the BPPC by proposing two solution representations. These representations frame the BPPC problem on two different levels: item-wise and bin-wise. In the item-wise solution representation, the adapted jellyfish metaheuristic updates the solutions through a set of item swaps without any preference for the bins. In the bin-wise solution representation, the metaheuristic method selects a set of bins, and then it performs the item swaps from these selected bins only. The proposed method was thoroughly benchmarked on a standard dataset and compared against the well-known PSO, Jaya, and heuristics. The obtained results revealed that the proposed methods outperformed the other comparison methods in terms of the number of bins and the average bin utilization. In addition, the proposed method achieved the lowest deviation rate from the lowest bound of the standard dataset relative to the other methods of comparison.

Suggested Citation

  • Walaa H. El-Ashmawi & Ahmad Salah & Mahmoud Bekhit & Guoqing Xiao & Khalil Al Ruqeishi & Ahmed Fathalla, 2023. "An Adaptive Jellyfish Search Algorithm for Packing Items with Conflict," Mathematics, MDPI, vol. 11(14), pages 1-28, July.
  • Handle: RePEc:gam:jmathe:v:11:y:2023:i:14:p:3219-:d:1199859
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/11/14/3219/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/11/14/3219/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Klaus Jansen, 1999. "An Approximation Scheme for Bin Packing with Conflicts," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 363-377, December.
    2. Ruslan Sadykov & François Vanderbeck, 2013. "Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 244-255, May.
    3. Archetti, Claudia & Bianchessi, Nicola & Speranza, M. Grazia, 2014. "Branch-and-cut algorithms for the split delivery vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 685-698.
    4. Fleszar, Krzysztof & Charalambous, Christoforos, 2011. "Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem," European Journal of Operational Research, Elsevier, vol. 210(2), pages 176-184, April.
    5. Chou, Jui-Sheng & Truong, Dinh-Nhat, 2021. "A novel metaheuristic optimizer inspired by behavior of jellyfish in ocean," Applied Mathematics and Computation, Elsevier, vol. 389(C).
    6. Albert E. Fernandes Muritiba & Manuel Iori & Enrico Malaguti & Paolo Toth, 2010. "Algorithms for the Bin Packing Problem with Conflicts," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 401-415, August.
    7. Benjamin Byholm & Ivan Porres, 2018. "Fast algorithms for fragmentable items bin packing," Journal of Heuristics, Springer, vol. 24(5), pages 697-723, October.
    8. Philippe Galinier & Jin-Kao Hao, 1999. "Hybrid Evolutionary Algorithms for Graph Coloring," Journal of Combinatorial Optimization, Springer, vol. 3(4), pages 379-397, December.
    9. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    10. Christos Gogos & Panayiotis Alefragis & Efthymios Housos, 2012. "An improved multi-staged algorithmic process for the solution of the examination timetabling problem," Annals of Operations Research, Springer, vol. 194(1), pages 203-221, April.
    11. Yainier Labrada-Nueva & Martin H. Cruz-Rosales & Juan Manuel Rendón-Mancha & Rafael Rivera-López & Marta Lilia Eraña-Díaz & Marco Antonio Cruz-Chávez, 2021. "Overlap Detection in 2D Amorphous Shapes for Paper Optimization in Digital Printing Presses," Mathematics, MDPI, vol. 9(9), pages 1-22, May.
    12. Ana Moura & Telmo Pinto & Cláudio Alves & José Valério de Carvalho, 2023. "A Matheuristic Approach to the Integration of Three-Dimensional Bin Packing Problem and Vehicle Routing Problem with Simultaneous Delivery and Pickup," Mathematics, MDPI, vol. 11(3), pages 1-16, January.
    Full references (including those not matched with items on IDEAS)

    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. Renatha Capua & Yuri Frota & Luiz Satoru Ochi & Thibaut Vidal, 2018. "A study on exponential-size neighborhoods for the bin packing problem with conflicts," Journal of Heuristics, Springer, vol. 24(4), pages 667-695, August.
    2. Fleszar, Krzysztof, 2022. "A MILP model and two heuristics for the Bin Packing Problem with Conflicts and Item Fragmentation," European Journal of Operational Research, Elsevier, vol. 303(1), pages 37-53.
    3. Lijun Wei & Zhixing Luo, & Roberto Baldacci & Andrew Lim, 2020. "A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 428-443, April.
    4. Ekici, Ali, 2023. "A large neighborhood search algorithm and lower bounds for the variable-Sized bin packing problem with conflicts," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1007-1020.
    5. Borja Ena & Alberto Gomez & Borja Ponte & Paolo Priore & Diego Diaz, 2022. "Homogeneous grouping of non-prime steel products for online auctions: a case study," Annals of Operations Research, Springer, vol. 315(1), pages 591-621, August.
    6. Mathijs Barkel & Maxence Delorme, 2023. "Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 475-494, March.
    7. Orlando Rivera Letelier & François Clautiaux & Ruslan Sadykov, 2022. "Bin Packing Problem with Time Lags," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2249-2270, July.
    8. Luciano Costa & Claudio Contardo & Guy Desaulniers & Julian Yarkony, 2022. "Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1141-1156, March.
    9. Andrea Bettinelli & Valentina Cacchiani & Enrico Malaguti, 2017. "A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 457-473, August.
    10. Maxence Delorme & Manuel Iori, 2020. "Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 101-119, January.
    11. Jiliu Li & Zhixing Luo & Roberto Baldacci & Hu Qin & Zhou Xu, 2023. "A New Exact Algorithm for Single-Commodity Vehicle Routing with Split Pickups and Deliveries," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 31-49, January.
    12. Timo Gschwind & Stefan Irnich, 2014. "Dual Inequalities for Stabilized Column Generation Revisited," Working Papers 1407, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 23 Jul 2014.
    13. Ruslan Sadykov & François Vanderbeck & Artur Pessoa & Issam Tahiri & Eduardo Uchoa, 2019. "Primal Heuristics for Branch and Price: The Assets of Diving Methods," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 251-267, April.
    14. Schepler, Xavier & Rossi, André & Gurevsky, Evgeny & Dolgui, Alexandre, 2022. "Solving robust bin-packing problems with a branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 297(3), pages 831-843.
    15. Hu, Qian & Zhu, Wenbin & Qin, Hu & Lim, Andrew, 2017. "A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function," European Journal of Operational Research, Elsevier, vol. 260(1), pages 70-80.
    16. Saharnaz Mehrani & Carlos Cardonha & David Bergman, 2022. "Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1070-1085, March.
    17. Şuvak, Zeynep & Altınel, İ. Kuban & Aras, Necati, 2020. "Exact solution algorithms for the maximum flow problem with additional conflict constraints," European Journal of Operational Research, Elsevier, vol. 287(2), pages 410-437.
    18. Samir Elhedhli & Lingzi Li & Mariem Gzara & Joe Naoum-Sawaya, 2011. "A Branch-and-Price Algorithm for the Bin Packing Problem with Conflicts," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 404-415, August.
    19. Pereira, Jordi, 2016. "Procedures for the bin packing problem with precedence constraints," European Journal of Operational Research, Elsevier, vol. 250(3), pages 794-806.
    20. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.

    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:gam:jmathe:v:11:y:2023:i:14:p:3219-:d:1199859. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.