An exact algorithm for two-dimensional vector packing problem with volumetric weight and general costs

Ting Wang, Qian Hu and Andrew Lim

European Journal of Operational Research, 2022, vol. 300, issue 1, 20-34

Abstract: The volumetric weight of a package has become an essential factor in calculating the delivery cost of shipments in the international logistics market. In this work, we extend the two-dimensional vector packing problem by considering a more realistic cost structure, which is a general function of volumetric weight. The problem is to pack a set of different items into some identical bins without violating weight limits and volume capacities so that the total delivery cost is minimized. We develop an exact approach based on a branch-and-price algorithm and subset-row inequalities for the problem. To efficiently solve the pricing problem in column generation, a label-setting algorithm with an effective label dominance rule and a bounding procedure is presented. A stronger label dominance rule is derived for the case where the cost function is convex. The computational results show that the exact method is effective in solving the various test instances of the problem. If the volumetric weight is not considered, the exact method can be adapted to solve the two-dimensional vector packing problem with piecewise linear cost function and outperformed the existing exact algorithm by computing 27 optimal solutions for previously open instances.

Keywords: Packing; Two-dimensional vector packing problem; Volumetric weight; General costs; Branch-and-price-and-cut (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721008572
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:300:y:2022:i:1:p:20-34

DOI: 10.1016/j.ejor.2021.10.011

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().