A comparative review of 3D container loading algorithms

• Author: Kath Dowsland,Tolga Bektaş,Julia A. Bennell,Xiaozhou Zhao
• DOI: http://doi.org/10.1111/itor.12094
• Published date: 01 January 2016
• Date: 01 January 2016

Intl. Trans. in Op. Res. 23 (2016) 287–320

DOI: 10.1111/itor.12094

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

A comparative review of 3D container loading algorithms

Xiaozhou Zhaoa, Julia A. Bennella, Tolga Bektas¸aand Kath Dowslandb

aSouthampton Management School and Centre for OperationalResearch, Management Science and Information Systems

(CORMSIS),University of Southampton, Southampton SO17 1BJ, United Kingdom

bGower Optimal Algorithms, SwanseaSA3 4UH, United Kingdom

E-mail: X.Zhao@soton.ac.uk [Zhao]; J.A.Bennell@soton.ac.uk [Bennell]; T.Bektas@soton.ac.uk [Bektas¸];

k.a.dowsland@btconnect.com [Dowsland]

Received 19 July2013; received in revised form 6 January 2014; accepted 26 March 2014

Abstract

Three-dimensional cutting and packing problems have a range of important applicationsand are of particular

relevance to the transportation of cargo in the form of container loading problems. Recent years have seen a

marked increase in the number of papersexamining a variant of the container loading problem ranging from

largely theoretical to implementations that focus on meeting the many critical real-world constraints. In this

paper,we review the literature focusing on the solution methodologies employed by researchers, with the aim

of providing insight into some of the critical algorithmic design issues. In addition, we provide an extensive

comparison of algorithm performance across the benchmark literature.

Keywords:cutting and packing; container loading; review

1. Introduction

The three-dimensional (3D) packing problem is a natural generalization of the classical one- and

two-dimensional (1D and 2D) problems. The most commonly cited applicationfor such problems is

the transportation of goods that may be packed directly into containers or trucks or first packed on

pallets. With a few exceptions, the literature focuses on items contained within 3D boxes. Even with

this restriction, it is clear that the relevance and scope of application is high. Despite its important

industrial and commercial applications,historically, publications on this problem areaare relatively

few in comparison to its 1D and 2D counterparts. However, recent years have seen rapid growth in

research and publications on this problem, including new research avenues that examine integrating

packing with routing and scheduling.

Arranging boxes into a container, truck, or pallet is one of the more complex packing problems

with respect to real-world constraints. While aiming to produce a packing arrangement that makes

the best use of resources, an underestimate of the number of containers required to transport certain

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

288 X. Zhao et al. / Intl. Trans. in Op. Res. 23 (2016) 287–320

goods may be very costly in terms of delay or carrying extra containers that are underutilized,

resulting in a wasted resource. In addition to the box sizes, there is a host of constraints associated

with weight distribution, stacking, stability, and support thatneed to be respected when determining

the number of containers. Further, clients may constrain consignments to be carried together, or

delivery vehicles need to unload at several locations. Bortfeldt and W¨

ascher (2013) provide a

comprehensive review of such constraints.

The aim of this paper is to reviewthe literature on 3D container loading. Here, the term “container

loading” is used in its broadest sense, in a similar way to Bortfeldt and W¨

ascher (2013), who

recently provideda review that specifically focuses on the inclusion of authors of various constraints

encountered in practice but gives relatively little attention to the solution approaches. Our paper is

a complementary review to that of Bortfeldt and W¨

ascher (2013) in that it focuses on the design

and implementation of solution methodologies for solving these problems. We also provide an

experimental comparison of different algorithms on benchmark data sets to identify the state of

the art in solution methods in the area. In order to contain the size of the review, we have excluded

pallet loading, irregular objects, and do not explicitlyreviewed the open dimension problem though

some papers addressing this problem are mentioned.

The rest of the paper is structured as follows. The next section provides a detailed description of

the problem types reviewed in the paper, following the typology of W¨

ascher et al. (2007). Section

3 briefly discusses the constraints met in practice. Sections 4 and 5 discuss specific aspects of

the solution approaches, these are the placement heuristics (how a layout is constructed) and the

improvement heuristics (how to search for better solutions), respectively. Section 6 presents the

research that examines the use of exact methods. Section 7 gives an overview of how the literature

is split between different problem variants. Experimental results, along with benchmark data sets,

are analyzed in section 8. Conclusions are given in Section 9.

2. Problem variants

According to W¨

ascher et al. (2007), cutting and packing problems can be groupedby dimensionality,

assortment of large items, assortment of small items, and the objective. Here we are only concerned

with 3D items that are cuboid. We will call the large items as containers and the small items as boxes.

Boxes may be “identical, weakly heterogeneous” (many boxes but a few box types) or “strongly

heterogeneous” (few boxes and many box types). If there is more than one container, these can be

identical, weakly or strongly heterogeneous. They provide the following problem typology.

If the objective is one of “input minimization,” then the aim is to pack all the boxes in as few

containers as possible. Combining the classes of large and small item assortments gives six unique

problems as follows:

rSingle stock-size cutting stock problem (SSSCSP) if the containers are identical and boxes are

weakly heterogeneous.

rSingle bin-size bin packing problem (SBSBPP) if the containers are identical and the boxes are

strongly heterogeneous.

rMultiple stock-size cutting stock problem (MSSCSP) if the containers and the boxes are weakly

heterogeneous.

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies

X. Zhao et al. / Intl. Trans. in Op. Res. 23 (2016) 287–320 289

rMultiple bin-size bin packing problem (MBSBPP) if the containers are weakly heterogeneous

and boxes are strongly heterogeneous.

rResidual cutting stock problem (RCSP) if the containers are strongly heterogeneous and boxes

are weakly heterogeneous.

rResidual bin packing problem(RBPP) if the containers and the boxes are strongly heterogeneous.

If the objective is one of “output maximization,” then the aim is to pack a subset of boxes that

give the highest value to a fixed set of containers. Here there may be a single container or multiple

containers. Seven unique problems can be defined as follows:

rIdentical item packing problem (IIPP) if there is a single container and the boxes are identical.

rSingle large object placement problem (SLOPP) if there is single container and weakly heteroge-

neous boxes.

rSingle knapsack problem (SKP) if there is a single container and the boxes are strongly heteroge-

neous.

rMultiple identical large object placement problem (MILOPP) if there are multiple identical

containers and weakly heterogeneous boxes.

rMultiple heterogeneous large object placement problem (MHLOPP) if the containers are weakly

or strongly heterogeneous and weakly heterogeneous boxes.

rMultiple identical knapsack problem (MIKP) if there are multiple identical containers and

strongly heterogeneous boxes.

rMultiple heterogeneous knapsack problem (MHKP) if the containers are weakly or strongly

heterogeneous and strongly heterogeneous boxes.

All the above problems assume that the containers have fixed dimensions. There is one further

case where two dimensions are fixed and one, either the length or height, is variable. Clearly, this

is a single container input minimization problem, defined by W¨

ascher et al. (2007) as the open

dimension problem. We do not explicitly review this problem type here, some example papers are

Allen et al. (2011), Bortfeldt and Mack (2007), Faina (2000), Fujiyoshiet al. (2009), He et al. (2012),

Lai et al. (1998), Li and Cheng (1992), Miyazawa and Wakabayashi (1997, 1999), and Yeung and

Tang (2005).

3. Problem constraints

There are three basic constraints that are fundamental to the problem and observed by all research

papers. These are stated as follows:

rBoxes may only be placed with their edges parallel to the walls of the container.

rAll boxes must be placed within the container.

rBoxes may not intersect each other.

In many cases only solutions that result in the entire base of the box being fully supported are

acceptable, others allow a small amount of overhang. In cases where the centre of gravity of a box

must be supported, it is assumed to be at the same position as its geometrical centre.

C

2014 The Authors.

International Transactionsin Operational Research C

2014 International Federation of OperationalResearch Societies