Back to search

University of Waterloo

Models and Solution Methods for the Pallet Loading Problem

Abstract

dc:description.abstract

The three-dimensional bin packing problem (3DBPP) seeks to find the minimum number of bins to pack a finite number of rectangular boxes. It has a wide array of applications, ranging from airline cargo transportation to warehousing. Its practical extension, the distributor's pallet loading problem (DPLP), requires the pallets to be stable, packable, and adhering to several industry requirements such as packing sequences and weight limits. Despite being studied extensively in the optimization literature, the 3DBPP is still one of the most difficult problems to solve. Currently, medium to large size instances are only solved heuristically and remain out of reach of exact methods. This also applies to the DPLP, as the addition of practical constraints further complicates the proposed models. A recent survey identified the scarcity of exact solution methods that are capable of handling practical versions of the problem and the lack of a realistic benchmark data set as major research gaps. In this thesis, firstly, we propose a novel formulation and an exact solution approach based on column generation for the 3DBPP, where the pricing subproblem is a two-dimensional layer generation problem. Layers are highly desirable in practical packings as they are easily packable and can accommodate important practical constraints such as item support, family groupings, isle friendliness, and load bearing. Being key to the success of the column generation approach, the pricing subproblem is solved optimally as well as heuristically, and is enhanced using item grouping, item replacement, layer reorganization, and layer spacing. We also embed the column generation approach within a branch-and-price framework. We conduct extensive computational experiments and compare against existing approaches. The proposed approach outperforms the best performing algorithm in the literature \boldred{in most instances} and succeeds to solve practical size instances in very reasonable computational times. Secondly, we extend the column generation scheme to incorporate practical constraints set by the warehousing industry. We introduce a nonlinear layer spacing model to improve the stability of the planned pallets, which we then reformulate as an SOCP. In order to calculate the weight distribution within pallets, we introduce a new graph representation for placed items. Finally, we propose construction and improvement heuristics to tackle each practical constraint, such as vertical support, different item shapes, planogram sequencing, load bearing, and weight limits. We conduct extensive computational experiments to demonstrate the good performance of the proposed methodology, and provide results for future benchmarking. To the best of our knowledge, this is the first approach to fully solve the DPLP. Computational experiments show that the proposed approach succeeds in solving industry size instances in record computational times and achieves high quality solutions that account for all practical constraints. Finally, we propose realistic benchmark instances by designing and training an instance generator using industry data. We apply clustering and curve fitting techniques to 342 industry instances with 166,406 items to obtain the distributions for item volumes, dimensions, and frequencies. We separate the instances into several classes and categories using $k$-clustering and generate multiple instances with different sizes. We, then, extend the generator to incorporate practical features such as weight, load capacity, shape, planogram sequencing, and reduced edge support.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yildiz, Burak Can
Advisors dc:contributor.advisor
  • Elhedhli, Samir
  • Gzara, Fatma

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/13243

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Yildiz, Burak Can. Models and Solution Methods for the Pallet Loading Problem. University of Waterloo, 2018. http://hdl.handle.net/10012/13243