Algorithms for Container Loading Problems

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Algorithms for Container Loading Problems"

By

Mr. Wenbin Zhu


Abstract

The problems examined originate from industrial projects awarded to our 
research team. In one project, our team was contracted by a buying agent for a 
large multi-national retailer to investigate better ways to formulate packing 
plans for the loading of goods into multiple containers. Typically, the goods 
come in the form of 3D rectangular carton boxes, which are to be loaded into 3D 
rectangular containers of various standard sizes. Each type of container has a 
different associated cost of shipping. The task is to select a set of 
containers that can contain all items while minimizing this shipping cost. 
Products are loaded with faces parallel to the faces of the container, often 
known as orthogonal packing in literature. We call this problem the Multiple 
Container Loading Cost Minimization Problem (MCLCMP).

If a set of boxes can be loaded into a container, we call the set of boxes and 
the associated container a loading pattern. MCLCMP can be naturally formulated 
as a set cover (SC) problem, where the set to be covered is the set of all 
boxes and a loading pattern ``covers'' a subset of boxes. We would like to 
select loading patterns (from a set of candidates) to cover all boxes while 
minimizing the total cost of the associated containers. Our approaches to 
MCLCMP are essentially two-level approaches. The burden of finding feasible 
loading patterns is left to the lower level, where efficient algorithms for the 
Single Container Loading Problem (SCLP) are needed. The higher level mainly 
focuses on how to efficiently use the SCLP algorithms to produce candidate 
loading patterns and find good solutions to the set cover formulations.

The first part of my thesis concentrates on developing efficient algorithms for 
the SCLP. Our approach and the best performing approaches in recent literature 
share similar structures and can be broadly classified as block building 
approaches. We propose a conceptual model in to capture the common structure of 
these block building approaches. In this conceptual model, a block building 
approach is dissected into six elements. Three of the six elements define the 
states and transitions in the search space, two are heuristic rules that 
attempt to guide the search to more promising search regions, and the last 
element is the overarching search strategy. By dissecting block building 
approaches into six elements, we can compare and contrast the various choices 
made by existing algorithms for each element through both theoretical 
discussion and computational experiments. This conceptual model not only allows 
us to better understand the impact of various choices for each element, it also 
allows us to identify possible further research directions.

The second part of my thesis concentrates on how to efficiently solve the set 
cover formulation, where the main idea is to combine the strengths of the 
prototyping concept and the column generation technique. The prototyping 
concept is similar to the one used in product design and software engineering. 
Although producing high quality loading patterns is time-consuming (roughly 
equivalent to solving SCLP), reasonable guesses for loading patterns can be 
made quickly. We call such a guess a prototype, and using prototypes instead of 
actual loading patterns will allow us to explore a much larger set of 
candidates in the set cover problem. If the prototypes are close to actual 
feasible loading patterns (in terms of the number of boxes of each type 
loaded), then there is a high probability that we can convert the selected 
prototypes into actual loading patterns. Since a larger set of candidates leads 
to a better optimal solution for the corresponding set cover problem, we are 
more likely to obtain a better solution to MCLCMP. Column generation is a 
standard technique for solving linear programs with a huge number of decision 
variables, where only a small set of columns is initially included and new 
columns are generated as needed by solving a pricing subproblem (in the matrix 
form of the set cover model, a column in the coefficient matrix represents a 
loading pattern). In the case of MCLCMP, the pricing subproblem is essentially 
a variant of the SCLP.

The third part of my thesis proposes a new algorithm for the special case of 
the MCLCMP where all containers are identical and boxes are not rotatable. This 
special case is the well-known 3D bin packing problem (3D-BPP). Our main idea 
is to model a feasible packing inside a bin as three comparability graphs. We 
can then conveniently collate fragmented space in a bin to improve volume 
utilization.

Computational experiments on standard benchmark data suggest that our proposed 
algorithms for the SCLP, MCLCMP and 3D-BPP outperform all prior approaches.


Date:			Wednesday, 12 September 2012

Time:			9:00am - 11:00am

Venue:			Room 3402
 			Lifts 17/18

Chairman:		Prof. Yijing Yan (CHEM)

Committee Members:	Prof. Siu-Wing Cheng (Supervisor)
 			Prof. Dimitris Papadias
 			Prof. Ke Yi
 			Prof. Xiangtong Qi (IELM)
                        Prof. Yanzhi Li (Mgmt. Sci., CityU)


**** ALL are Welcome ****