Algorithms for Container Loading Problems

PhD Thesis Proposal 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. They are 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 Multiple 
Container Loading Cost Minimization Problem (MCLCMP).

Since MCLCMP is an extremely hard combinatorial optimization problem, the main 
objective is to develop heuristic algorithms that can find good solutions in 
reasonable time. We will present three algorithms in increasing order of 
sophistication and effectiveness: the Set Cover based Binary Search (SCBS) 
algorithm, the Prototype Column Generation (PCG) algorithm, and the Goal-driven 
Prototype Column Generation (GD-PCG) algorithm.

All three algorithms are based on a set cover formulation for 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 algorithms for the Single Container Loading Problem 
(SCLP), which is well studied and many algorithm exists in the literature. We 
main mainly focuses on how to efficiently use the SCLP algorithms to produce 
candidate loading patterns and find good solutions to the set cover 
formulations.

In practice, it is only possible to consider a limited number of loading 
patterns since deciding whether a set of boxes can be loaded into a container 
is NP-hard. Hence, there is a gap between the optimal solution to the set cover 
problem and the optimal solution to MCLCMP. However, if the set of candidate 
loading patterns is sufficiently large and diverse, good solutions can still be 
found. This is the main premise behind our first algorithm.

Our PCG algorithm combines 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 single container 
loading problem.

The GD-PCG algorithm improves on PCG in three respects. Firstly, the PCG 
algorithm carries out the search in two stages and each stage approaches good 
solutions to MCLCMP in its own dimension, whereas GD-PCG searches in both 
dimensions at the same time. Secondly, we extend the set cover formulation for 
MCLCMP by taking the expected overall volume utilization of the containers in a 
solution into account. Thirdly, once a solution is found, a goal-driven search 
is carried out in the solution neighborhood to improve the solution.

Since MCLCMP can be seen as an extension to the three-dimensional orthogonal 
bin packing problem (3D-BPP), we compared our three algorithms with algorithms 
specifically designed for 3D-BPP on standard benchmark. The computational 
results show that our algorithm produces better solutions.  MCLCMP is a new 
problem, no standard benchmark exists. We created a set of 350 instances with 
known optimal solutions based on the characteristics of common products to 
evaluate the effectiveness of our algorithms. We also created a set of 190 
instances based on real order from one of the project for further references.

Computational experiments on these instances suggest that our PCG algorithm 
that combines the concept of prototyping and column generation is indeed 
effective. With the addition of goal-driven feature, GD-PCG is the best among 
the three algorithms. Many real world applications have natural set cover 
formulations, where the columns in the constraint matrix of the formulation 
have a natural interpretation. It is also often the case that the pricing 
problems for these applications are NP-hard. Our PCG and GD-PCG approaches to 
solving MCLCMP may therefore be usable in such applications after modification, 
or inspire similar approaches within the confines of the problem domain.

Our approaches to MCLCMP are essentially two-level approaches. Therefore, a 
more effective algorithm for the single container loading problem (SCLP) will 
further improve the effectiveness. I will investigate SCLP in detail and try to 
develop new algorithms for SCLP. In addition to directly load products onto the 
floor of a container, it is also common that products are first loaded into 
pallets and pallets of same base area are then loaded into container. This 
scenario can be modeled as 3D-BPP. Therefore, good algorithms for 3D-BPP will 
also be useful. Since 3D-BPP is a special case of MCLCMP, algorithms that 
exploit specific feature of 3D-BPP would be more effective. I will investigate 
3D-BPP in detail and try to develop new algorithms for it.


Date:                   Thursday, 7 June 2012

Time:                   2:00pm - 4:00pm

Venue:                  Room 3501
                         lifts 25/26

Committee Members:      Prof. Siu-Wing Cheng (Supervisor)
                         Prof. Dimitris Papadias (Chairperson)
 			Dr. Ke Yi
 			Dr. Xiangtong Qi (IELM)


**** ALL are Welcome ****