3D-SCLP

This is the project presented to the Institute of Computing of the University of Campinas in partial fulfillment of the requirements for the degree of Master of Science in Computer Science. I presented it to an evaluation committee on February 19th, 2025. You can watch it in the presentation section.

History

After I graduated in Mechanical Engineering, I started working at JettaCargo with logistic optimizations. It was challenging to work on a topic I had no previous experience. Nevertheless, I did some amazing work that I am very proud of.

However, after some time there, I noticed I had too many gaps in my knowledge. Though I was studying and learning with my colleagues, something was odd. I felt like I was missing something. So, I decided I would look for it. How? I searched the internet for good universities in Brazil on Operations Research and I found Unicamp, more specifically I found the Laboratory of Optimization and Combinatorics (LOCo), a large research group dedicated to solving the problems that I was interested.

I joined Unicamp to pursue a Master's in Computer Science, hoping to fill the gaps in my knowledge. I chose Professor Flávio Keidi Miyazawa to be my supervisor because, among the professors of Unicamp, he was the one most aligned with my research interest: three-dimensional packing problems. Later on, Professor Thiago Alves de Queiroz joined as co-advisor.

Problem Definition

From the beginning, I made it clear I wished to study and solve a three-dimensional single container packing problem, mostly because that was the main problem we solved at JettaCargo. The question was then which practical constraints we would add to the base problem. After extensive research and study, we decided to impose no practical constraint and beat the current state-of-the-art algorithm. We are audacious!

In simple terms, the problem is defined by a set of Items and a Container. Both the items and the container are rectangular cuboids. The items have a quantity (the number of that item that is available for allocating). Furthermore, each item has a set of up to six allowed orientations, meaning one can rotate them when allocating.

Illustration of the 3D-SCLP. Three types of Items are packed inside a Container, generating a Packing. Both the container and the items are rectangular cuboids.

The six possible orientations of an item with length equals 10, width equals 20, and height equals 30, in the order θ_xyz, θ_xzy, θ_yxz, θ_yzx, θ_zxy, and θ_zyx. Each item has its own subset of allowed orientations.

Previous Works

In the last few years, many authors proposed solutions for the 3D-SCLP. Below I listed some of them with their main contributions and also the results reported by the authors. References can be found in the References Section.

During the research, Araya et al. (2017) was the state-of-the-art, obtaining an average volume usage of 95.53% with a time limit of 30 seconds.

PE-08 - Parreño et al. (2008): compare the partition and cover representation for the residual space, they show that the latter yields better results;
FB-10 - Fanslau and Bortfeldt (2010): propose a tree search-based heuristic to solve the problem, that is the basis of all subsequent tree search-based proposals;
GR-12 - Goncalves and Resende (2012): propose successful a Biased Random-Key Genetic Algorithms (BRKGA) for the 3D-SCPL;
ZE-12 - Zhu et al. (2012): simplified and improved the tree search-based heuristic of Fanslau and Bortfeldt (2010);
ZH-12 - Zhang et al. (2012): poposed the use of the contact surface to select blocks;
AR-14 - Araya and Riff (2014): expanded the tree search-based heuristic of Zhu et al. (2012) to a beam search;
RA-16 - Ramos et al. (2016): expanded the BRKGA algorithm of Goncalves and Resende (2012);
AA-17 - Araya et al. (2017): modified the evaluation function of Araya and Riff (2014);

Comparison of the results reported by different heuristics of the literature. The `-p` in the time limit indicates parallel execution.
Heuristic	Volume Usage	Time Limit [s]
PE-08	91.05	100
FB-10	93.88	320
GR-12	94.54	147-p
ZE-12	94.59	500
ZL-12	94.98	500
ZH-12	94.53	600
AR-14	95.40	500
RA-16	94.71	274-p
AA-17	95.53	30

Proposed Heuristic

We reproduced the state-of-the-art with our own code implementation and proposed the following improvements:

Data Structures:

to implement the residual space, the state-of-the-art uses linked lists while we use data structures with contiguous memory layout;
to find the contact area between blocks, the state-of-the-art used the external library Bullet, which relies on collision detection methods, while we used a broad and narrow search technique combined with a contiguous memory storage.

Skip Feature:

we added a mechanism that avoid recomputations.

Volume Loss Estimate:

we used a different function to estimate the amount of volume lost when a block is allocated in an empty space;

Configuration:

both our and the state-of-the-art heuristics require the specification of parameters. To find good values, the state-of-the-art performed a manual search while we used irace for automatic algorithm configuration;

Evaluation Function:

we used a two-stage modification of the fitness function proposed by the state-of-the-art, allowing the heuristic to adapt and change its behavior at different phases of the allocation process;

Results

Average Volume Usage

The heuristic we proposed, with only 5 seconds (5-H), outperformed the state-of-the-art (AA-17) with 30 seconds by 0.11%. With 30 seconds (30-H), it outperformed the state-of-the-art by 0.52%

Comparison of the results obtained with different time limits using state-of-the-art (AA-17) and the proposed heuristic with a time limit of 5 seconds (5-H) and 30 seconds (30-H).
Heuristic	Volume Usage	Time Limit
AA-17	95.53	30
5-H	95.64	5
30-H	96.05	30

Time Equivalence

The figure below presents the time required by state-of-the-art (A) to reach the results of the proposed heuristic (H). The full black line shows the experimental result. Because of its apparent linear behavior, we made a linear curve fit f(t) = α · t to identify the angular coefficient α. The results demonstrate that H performs as well as A with one-sixteenth of the time. In other words, given a time limit T to heuristic H, it would take 16·T for A to reach the same result.

Time required for state-of-the-art (A) to reach the results of the proposed heuristic (H). On the left, the time required by A is limited to 2000 seconds. On the right, the time limit given to H is limited to 10 seconds. In full black line, the experimental data. In gray dashed lines, a curve fit of the function `f(t) = α · t`. The value of `α` is displayed in each graph.

Packings

Some solutions, i.e. packings, are displayed below.

Presentation

Conclusion

Joining LOCo was the right choice. I developed a cool work and I was able to outperform the current state-of-the-art algorithm of the 3D-SCLP. I also came into contact with many different topics, solution techniques, and people, further expanding my knowledge of Algorithms, Combinatorial Optimization, and Operations Research. I am grateful for the supervision of Flávio and Thiago and all the people who were part of my journey.

We made a nice work and obtained very good results! We intend to publish a paper and open-source the code.