• English
    • العربية
  • العربية
  • Login
  • QU
  • QU Library
  •  Home
  • Communities & Collections
  • Help
    • Item Submission
    • Publisher policies
    • User guides
    • FAQs
  • About QSpace
    • Vision & Mission
View Item 
  •   Qatar University Digital Hub
  • Qatar University Institutional Repository
  • Academic
  • Faculty Contributions
  • College of Engineering
  • Mechanical & Industrial Engineering
  • View Item
  • Qatar University Digital Hub
  • Qatar University Institutional Repository
  • Academic
  • Faculty Contributions
  • College of Engineering
  • Mechanical & Industrial Engineering
  • View Item
  •      
  •  
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Lower and upper bounding procedures for the bin packing problem with concave loading cost

    View/Open
    Publisher version (You have accessOpen AccessIcon)
    Publisher version (Check access options)
    Check access options
    1-s2.0-S0377221723004800-main.pdf (902.2Kb)
    Date
    2024-01-01
    Author
    Haouari, Mohamed
    Mhiri, Mariem
    Metadata
    Show full item record
    Abstract
    We address the one-dimensional bin packing problem with concave loading cost (BPPC), which commonly arises in less-than-truckload shipping services. Our contribution is twofold. First, we propose three lower bounds for this problem. The first one is the optimal solution of the continuous relaxation of the problem for which a closed form is proposed. The second one allows the splitting of items but not the fractioning of bins. The third one is based on a large-scale set partitioning formulation of the problem. In order to circumvent the challenges posed by the non-linearity of the objective function coefficients, we considered the inner-approximation of the concave load cost and derived a relaxed formulation that is solved by column generation. In addition, we propose two subset-sum-based heuristics. The first one is a constructive heuristic while the second one is a local search heuristic that iteratively attempts to improve the current solution by selecting pairs of bins and solving the corresponding subset sum-problem. We show that the worst-case performance of any BPPC heuristic and any concave loading cost function is bounded by 2. We present the results of an extensive computational study that was carried out on large set of benchmark instances. This study provides empirical evidence that the column generation-based lower bound and the local search heuristic consistently exhibit remarkable performance.
    URI
    https://www.sciencedirect.com/science/article/pii/S0377221723004800
    DOI/handle
    http://dx.doi.org/10.1016/j.ejor.2023.06.028
    http://hdl.handle.net/10576/59696
    Collections
    • Mechanical & Industrial Engineering [‎1473‎ items ]

    entitlement


    Qatar University Digital Hub is a digital collection operated and maintained by the Qatar University Library and supported by the ITS department

    Contact Us | Send Feedback
    Contact Us | Send Feedback | QU

     

     

    Home

    Submit your QU affiliated work

    Browse

    All of Digital Hub
      Communities & Collections Publication Date Author Title Subject Type Language Publisher
    This Collection
      Publication Date Author Title Subject Type Language Publisher

    My Account

    Login

    Statistics

    View Usage Statistics

    About QSpace

    Vision & Mission

    Help

    Item Submission Publisher policiesUser guides FAQs

    Qatar University Digital Hub is a digital collection operated and maintained by the Qatar University Library and supported by the ITS department

    Contact Us | Send Feedback
    Contact Us | Send Feedback | QU

     

     

    Video