A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function

Qian Hu, Wenbin Zhu, Hu Qin and Andrew Lim

European Journal of Operational Research, 2017, vol. 260, issue 1, 70-80

Abstract: The two-dimensional vector packing problem with piecewise linear cost function (2DVPP-PLC) models a practical packing problem faced by many companies that use courier services. We propose a branch-and-price algorithm to solve the 2DVPP-PLC exactly. The column generation procedure is a key component that affects the performance of a branch-and-price algorithm. The pricing problem exhibits an interesting structure that allows us to decompose it into subproblems that form a lattice. We explore dominance relations on the lattice and design an efficient algorithm for the pricing problem. Experimental results show that our branch-and-price algorithm is capable of solving 2DVPP-PLC test instances effectively.

Keywords: Packing; 2D vector packing; Piecewise linear cost function; Branch-and-price; Column generation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716310554
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:260:y:2017:i:1:p:70-80

DOI: 10.1016/j.ejor.2016.12.021

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 ().