IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v48y2012i6p1205-1220.html
   My bibliography  Save this article

The generalized bin packing problem

Author

Listed:
  • Baldi, Mauro Maria
  • Crainic, Teodor Gabriel
  • Perboli, Guido
  • Tadei, Roberto

Abstract

In the Generalized Bin Packing Problem (GBPP), given two sets of compulsory and non-compulsory items characterized by volume and profit and a set of bins with given volume and cost, we want to select the subset of profitable non-compulsory items to be loaded together with the compulsory ones into the appropriate bins in order to minimize the total net cost. Lower and upper bounds to the GBPP are given. The results of extensive computational experiments show that the proposed procedures are efficient and the bounds are tight.

Suggested Citation

  • Baldi, Mauro Maria & Crainic, Teodor Gabriel & Perboli, Guido & Tadei, Roberto, 2012. "The generalized bin packing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(6), pages 1205-1220.
    • Handle: RePEc:eee:transe:v:48:y:2012:i:6:p:1205-1220
    DOI: 10.1016/j.tre.2012.06.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554512000580
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2012.06.005?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. Crainic, Teodor Gabriel & Perboli, Guido & Pezzuto, Miriam & Tadei, Roberto, 2007. "Computing the asymptotic worst-case of bin packing lower bounds," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1295-1303, December.
    2. Shintani, Koichi & Imai, Akio & Nishimura, Etsuko & Papadimitriou, Stratos, 2007. "The container shipping network design problem with empty container repositioning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 43(1), pages 39-59, January.
    3. Alves, Claudio & Valerio de Carvalho, J.M., 2007. "Accelerating column generation for variable sized bin-packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1333-1352, December.
    4. Kang, Jangha & Park, Sungsoo, 2003. "Algorithms for the variable sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 147(2), pages 365-372, June.
    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. John Martinovic & Markus Hähnel & Guntram Scheithauer & Waltenegus Dargie & Andreas Fischer, 2019. "Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation," 4OR, Springer, vol. 17(2), pages 173-200, June.
    2. Novas, Juan M. & Ramello, Juan Ignacio & Rodríguez, María Analía, 2020. "Generalized disjunctive programming models for the truck loading problem: A case study from the non-alcoholic beverages industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    3. Perboli, Guido & Ferrero, Francesco & Musso, Stefano & Vesco, Andrea, 2018. "Business models and tariff simulation in car-sharing services," Transportation Research Part A: Policy and Practice, Elsevier, vol. 115(C), pages 32-48.
    4. Chen, Feng & Wang, Yu, 2020. "Downward compatible loading optimization with inter-set cost in automobile outbound logistics," European Journal of Operational Research, Elsevier, vol. 287(1), pages 106-118.
    5. Roberto Tadei & Guido Perboli & Francesca Perfetti, 2017. "The multi-path Traveling Salesman Problem with stochastic travel costs," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 6(1), pages 3-23, March.
    6. Perboli, Guido & Brotcorne, Luce & Bruni, Maria Elena & Rosano, Mariangela, 2021. "A new model for Last-Mile Delivery and Satellite Depots management: The impact of the on-demand economy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    7. Braune, Roland, 2019. "Lower bounds for a bin packing problem with linear usage cost," European Journal of Operational Research, Elsevier, vol. 274(1), pages 49-64.
    8. Mina Roohnavazfar & Daniele Manerba & Lohic Fotio Tiotsop & Seyed Hamid Reza Pasandideh & Roberto Tadei, 2021. "Stochastic single machine scheduling problem as a multi-stage dynamic random decision process," Computational Management Science, Springer, vol. 18(3), pages 267-297, July.
    9. Ardjmand, Ehsan & Sanei Bajgiran, Omid & Rahman, Shakil & Weckman, Gary R. & Young, William A., 2018. "A multi-objective model for order cartonization and fulfillment center assignment in the e-tail/retail industry," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 16-34.
    10. Perboli, Guido & Tadei, Roberto & Gobbato, Luca, 2014. "The Multi-Handler Knapsack Problem under Uncertainty," European Journal of Operational Research, Elsevier, vol. 236(3), pages 1000-1007.
    11. Yu Fu & Amarnath Banerjee, 2020. "Heuristic/meta-heuristic methods for restricted bin packing problem," Journal of Heuristics, Springer, vol. 26(5), pages 637-662, October.
    12. Pedroso, João Pedro, 2020. "Heuristics for packing semifluids," European Journal of Operational Research, Elsevier, vol. 282(3), pages 823-834.
    13. 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.
    14. Baldi, Mauro M. & Heinicke, Franziska & Simroth, Axel & Tadei, Roberto, 2016. "New heuristics for the Stochastic Tactical Railway Maintenance Problem," Omega, Elsevier, vol. 63(C), pages 94-102.
    15. Baldi, Mauro Maria & Manerba, Daniele & Perboli, Guido & Tadei, Roberto, 2019. "A Generalized Bin Packing Problem for parcel delivery in last-mile logistics," European Journal of Operational Research, Elsevier, vol. 274(3), pages 990-999.
    16. Roohnavazfar, Mina & Manerba, Daniele & De Martin, Juan Carlos & Tadei, Roberto, 2019. "Optimal paths in multi-stage stochastic decision networks," Operations Research Perspectives, Elsevier, vol. 6(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. Leung, Joseph Y.-T. & Li, Chung-Lun, 2008. "An asymptotic approximation scheme for the concave cost bin packing problem," European Journal of Operational Research, Elsevier, vol. 191(2), pages 582-586, December.
    2. Lewis, R. & Song, X. & Dowsland, K. & Thompson, J., 2011. "An investigation into two bin packing problems with ordering and orientation implications," European Journal of Operational Research, Elsevier, vol. 213(1), pages 52-65, August.
    3. Qin, Hu & Zhang, Zizhen & Qi, Zhuxuan & Lim, Andrew, 2014. "The freight consolidation and containerization problem," European Journal of Operational Research, Elsevier, vol. 234(1), pages 37-48.
    4. Mauro Baldi & Teodor Crainic & Guido Perboli & Roberto Tadei, 2014. "Branch-and-price and beam search algorithms for the Variable Cost and Size Bin Packing Problem with optional items," Annals of Operations Research, Springer, vol. 222(1), pages 125-141, November.
    5. Andrea Bettinelli & Alberto Ceselli & Giovanni Righini, 2010. "A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint," Annals of Operations Research, Springer, vol. 179(1), pages 221-241, September.
    6. Qi Zhang & Shixin Liu & Ruiyou Zhang & Shujin Qin, 2021. "Column generation algorithms for mother plate design in steel plants," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(1), pages 127-153, March.
    7. 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.
    8. François Clautiaux & Cláudio Alves & José Valério de Carvalho & Jürgen Rietz, 2011. "New Stabilization Procedures for the Cutting Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 23(4), pages 530-545, November.
    9. Guericke, Stefan & Tierney, Kevin, 2015. "Liner shipping cargo allocation with service levels and speed optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 40-60.
    10. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    11. Leonard Heilig & Stefan Voß, 0. "Information systems in seaports: a categorization and overview," Information Technology and Management, Springer, vol. 0, pages 1-23.
    12. Wang, Shuaian & Meng, Qiang & Liu, Zhiyuan, 2013. "Bunker consumption optimization methods in shipping: A critical review and extensions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 53(C), pages 49-62.
    13. Zheng, Jianfeng & Sun, Zhuo & Zhang, Fangjun, 2016. "Measuring the perceived container leasing prices in liner shipping network design with empty container repositioning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 123-140.
    14. Zhu, Shengda & Fu, Xiaowen & Bell, Michael G.H., 2021. "Container shipping line port choice patterns in East Asia the effects of port affiliation and spatial dependence," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    15. Wang, Hua & Wang, Shuaian & Meng, Qiang, 2014. "Simultaneous optimization of schedule coordination and cargo allocation for liner container shipping networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 261-273.
    16. Bassem Jarboui & Saber Ibrahim & Abdelwaheb Rebai, 2010. "A new destructive bounding scheme for the bin packing problem," Annals of Operations Research, Springer, vol. 179(1), pages 187-202, September.
    17. Zhao, Yiran & Yang, Zhongzhen & Haralambides, Hercules, 2019. "Optimizing the transport of export containers along China's coronary artery: The Yangtze River," Journal of Transport Geography, Elsevier, vol. 77(C), pages 11-25.
    18. Alaa Abdelshafie & May Salah & Tomaž Kramberger & Dejan Dragan, 2022. "Repositioning and Optimal Re-Allocation of Empty Containers: A Review of Methods, Models, and Applications," Sustainability, MDPI, vol. 14(11), pages 1-23, May.
    19. Yang, Dong & Pan, Kai & Wang, Shuaian, 2018. "On service network improvement for shipping lines under the one belt one road initiative of China," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 117(C), pages 82-95.
    20. Leonard Heilig & Stefan Voß, 2017. "Information systems in seaports: a categorization and overview," Information Technology and Management, Springer, vol. 18(3), pages 179-201, September.

    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:transe:v:48:y:2012:i:6:p:1205-1220. 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/wps/find/journaldescription.cws_home/600244/description#description .

    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.