An Exact Algorithm for the Two-Dimensional Orthogonal Packing Problem with Unloading Constraints

Jean-François Côté (), Michel Gendreau () and Jean-Yves Potvin ()
Additional contact information
Jean-François Côté: Département des opérations et systèmes de décision and Centre interuniversitaire de recherche sur les réseaux d'entreprise, la logistique et le transport, Université Laval, Québec G1V 0A6, Canada
Michel Gendreau: Département de mathématiques et de génie industriel, École Polytechnique de Montréal, Montréal H3C 3A7, Canada; and Centre interuniversitaire de recherche sur les réseaux d'entreprise, la logistique et le transport, Université de Montréal, Montréal H3C 3J7, Canada
Jean-Yves Potvin: Département d'informatique et de recherche opérationnelle and Centre interuniversitaire de recherche sur les réseaux d'entreprise, la logistique et le transport, Université de Montréal, Montréal H3C 3J7, Canada

Operations Research, 2014, vol. 62, issue 5, 1126-1141

Abstract: This paper describes an exact algorithm for solving a two-dimensional orthogonal packing problem with unloading constraints, which occurs as a subproblem of mixed vehicle routing and loading problems. The packing considered in this work is basically a feasibility problem involving a single bin. The problem is addressed through a decomposition approach wherein a branch-and-cut algorithm is designed for solving a one-dimensional relaxation of the original problem. When an integer solution is found in the branching tree, a subsidiary problem is solved to identify a two-dimensional packing that does not lead to any overlap and satisfies the unloading constraints. Cuts are added when the subsidiary problem proves to be infeasible. Several preprocessing techniques aimed at reducing the size of the solution space and uncovering infeasibility are also described. A numerical comparison with the best known exact method is reported at the end based on benchmark instances.

Keywords: two-dimensional packing; unloading constraints; vehicle routing; branch-and-cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2014.1307 (application/pdf)

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:inm:oropre:v:62:y:2014:i:5:p:1126-1141

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().