IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v50y2015icp43-53.html
   My bibliography  Save this article

The two-dimensional vector packing problem with piecewise linear cost function

Author

Listed:
  • Hu, Qian
  • Lim, Andrew
  • Zhu, Wenbin

Abstract

The two-dimensional vector packing problem with piecewise linear cost function (2DVPP-PLC) is a practical problem faced by a manufacturer of children׳s apparel that ships products using courier service. The manufacturer must ship a number of items using standard-sized cartons, where the cost of a carton quoted by the courier is determined by a piecewise linear function of its weight. The cost function is not necessarily convex or concave. The objective is to pack all given items into a set of cartons such that the total delivery cost is minimized while observing both the weight limit and volume capacity constraints. This problem is commonly faced by many manufacturers that ship products using courier service. We formulate the problem as an integer programming model. Since the 2DVPP-PLC generalizes the classical bin packing problem, it is more complex and challenging. Solving it directly using CPLEX is successful only for small instances. We propose a simple heuristic that is extremely fast and produces high-quality solutions for instances of practical size. We develop an iterative local search algorithm to improve the solution quality further. We generate two categories of test data that can serve as benchmark for future research.

Suggested Citation

  • Hu, Qian & Lim, Andrew & Zhu, Wenbin, 2015. "The two-dimensional vector packing problem with piecewise linear cost function," Omega, Elsevier, vol. 50(C), pages 43-53.
    • Handle: RePEc:eee:jomega:v:50:y:2015:i:c:p:43-53
    DOI: 10.1016/j.omega.2014.07.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048314000814
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2014.07.004?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. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    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. Lap Mui Ann Chan & Ana Muriel & Zuo-Jun Max Shen & David Simchi-Levi & Chung-Piaw Teo, 2002. "Effective Zero-Inventory-Ordering Policies for the Single-Warehouse Multiretailer Problem with Piecewise Linear Cost Structures," Management Science, INFORMS, vol. 48(11), pages 1446-1460, November.
    4. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2013. "A goal-driven approach to the 2D bin packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 224(1), pages 110-121.
    5. Juan Pablo Vielma & Shabbir Ahmed & George Nemhauser, 2010. "Mixed-Integer Models for Nonseparable Piecewise-Linear Optimization: Unifying Framework and Extensions," Operations Research, INFORMS, vol. 58(2), pages 303-315, April.
    6. 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.
    7. Liao, Chung-Shou & Hsu, Chia-Hong, 2013. "New lower bounds for the three-dimensional orthogonal bin packing problem," European Journal of Operational Research, Elsevier, vol. 225(2), pages 244-252.
    8. 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.
    9. Smithin, Tim & Harrison, Paul, 1982. "The third dimension of two-dimensional cutting," Omega, Elsevier, vol. 10(1), pages 81-87.
    10. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2007. "Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs," Operations Research, INFORMS, vol. 55(1), pages 146-157, February.
    11. 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.
    12. 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.
    13. Zhu, Wenbin & Zhang, Zhaoyi & Oon, Wee-Chong & Lim, Andrew, 2012. "Space defragmentation for packing problems," European Journal of Operational Research, Elsevier, vol. 222(3), pages 452-463.
    14. Kameshwaran, S. & Narahari, Y., 2009. "Nonconvex piecewise linear knapsack problems," European Journal of Operational Research, Elsevier, vol. 192(1), pages 56-68, January.
    15. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2003. "A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems," Management Science, INFORMS, vol. 49(9), pages 1268-1273, September.
    16. Lim, A. & Rodrigues, B. & Wang, Y., 2003. "A multi-faced buildup algorithm for three-dimensional packing problems," Omega, Elsevier, vol. 31(6), pages 471-481, December.
    17. Shoshana Anily & Julien Bramel & David Simchi-Levi, 1994. "Worst-Case Analysis of Heuristics for the Bin Packing Problem with General Cost Structures," Operations Research, INFORMS, vol. 42(2), pages 287-298, April.
    18. 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.
    19. Malaguti, Enrico & Medina Durán, Rosa & Toth, Paolo, 2014. "Approaches to real world two-dimensional cutting problems," Omega, Elsevier, vol. 47(C), pages 99-115.
    20. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    21. Che, Chan Hou & Huang, Weili & Lim, Andrew & Zhu, Wenbin, 2011. "The multiple container loading cost minimization problem," European Journal of Operational Research, Elsevier, vol. 214(3), pages 501-511, November.
    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. Hu, Qian & Wei, Lijun & Lim, Andrew, 2018. "The two-dimensional vector packing problem with general costs," Omega, Elsevier, vol. 74(C), pages 59-69.
    2. Alonso, M.T. & Alvarez-Valdes, R. & Iori, M. & Parreño, F. & Tamarit, J.M., 2017. "Mathematical models for multicontainer loading problems," Omega, Elsevier, vol. 66(PA), pages 106-117.
    3. Wei, Lijun & Zhu, Wenbin & Lim, Andrew & Liu, Qiang & Chen, Xin, 2018. "An adaptive selection approach for the 2D rectangle packing area minimization problem," Omega, Elsevier, vol. 80(C), pages 22-30.
    4. Zhi-Hua Hu & Yingxue Zhao & Sha Tao & Zhao-Han Sheng, 2015. "Finished-vehicle transporter routing problem solved by loading pattern discovery," Annals of Operations Research, Springer, vol. 234(1), pages 37-56, November.
    5. Bentao Su & Naiming Xie, 2020. "Single workgroup scheduling problem with variable processing personnel," 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. 28(2), pages 671-684, June.
    6. Wang, Ting & Hu, Qian & Lim, Andrew, 2022. "An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs," European Journal of Operational Research, Elsevier, vol. 300(1), pages 20-34.
    7. 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.

    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. Hu, Qian & Wei, Lijun & Lim, Andrew, 2018. "The two-dimensional vector packing problem with general costs," Omega, Elsevier, vol. 74(C), pages 59-69.
    2. Wei, Lijun & Zhu, Wenbin & Lim, Andrew, 2015. "A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem," European Journal of Operational Research, Elsevier, vol. 241(1), pages 39-49.
    3. 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.
    4. Hadj Salem, Khadija & Silva, Elsa & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry," European Journal of Operational Research, Elsevier, vol. 306(2), pages 549-566.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. Rapine, Christophe & Pedroso, Joao Pedro & Akbalik, Ayse, 2022. "The two-dimensional knapsack problem with splittable items in stacks," Omega, Elsevier, vol. 112(C).
    10. Christensen, Tue R.L. & Labbé, Martine, 2015. "A branch-cut-and-price algorithm for the piecewise linear transportation problem," European Journal of Operational Research, Elsevier, vol. 245(3), pages 645-655.
    11. Russo, Mauro & Sforza, Antonio & Sterle, Claudio, 2013. "An improvement of the knapsack function based algorithm of Gilmore and Gomory for the unconstrained two-dimensional guillotine cutting problem," International Journal of Production Economics, Elsevier, vol. 145(2), pages 451-462.
    12. 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.
    13. 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.
    14. 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.
    15. Igor Kierkosz & Maciej Luczak, 2014. "A hybrid evolutionary algorithm for the two-dimensional packing 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. 22(4), pages 729-753, December.
    16. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    17. Tue R. L. Christensen & Kim Allan Andersen & Andreas Klose, 2013. "Solving the Single-Sink, Fixed-Charge, Multiple-Choice Transportation Problem by Dynamic Programming," Transportation Science, INFORMS, vol. 47(3), pages 428-438, August.
    18. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R, 2017. "On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization," Annals of Operations Research, Springer, vol. 258(2), pages 301-346, November.
    19. Kallrath, Julia & Rebennack, Steffen & Kallrath, Josef & Kusche, Rüdiger, 2014. "Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges," European Journal of Operational Research, Elsevier, vol. 238(1), pages 374-389.
    20. Hinostroza, Ignacio & Pradenas, Lorena & Parada, Víctor, 2013. "Board cutting from logs: Optimal and heuristic approaches for the problem of packing rectangles in a circle," International Journal of Production Economics, Elsevier, vol. 145(2), pages 541-546.

    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:jomega:v:50:y:2015:i:c:p:43-53. 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/375/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.