Packing Shoes Efficiently

SAVANA SPECIALIZES IN THE PRODUCTION OF CHILDREN’S FOOTWEAR, using top quality materials, such as leather, latex, wool, etc. Savana is always searching to improve its processes as they were aware of some of the inefficiencies in their packaging process. With this concern, they asked us to improve the packaging process during a European Study Group with Industry that took place Oporto, Portugal. These are week-long workshops, where in the first day the industry partners present their problems. The academic partners form several groups, one for each problem, and they work all week in these problems. On the last day, the academic partners present their conclusions and suggestions. Later, a report is written and sent to the respective industry partner.

THE PACKAGING PROCESS

Savana produces children’s shoes in EU sizes ranging from 18 to 40. When a new line of footwear is introduced, the appropriate box size is selected manually from a limited choice. Boxes of the same size are used for footwear of various types and sizes. The footwear ordered by each customer is then packed into one or several large cardboard boxes, and these cardboard boxes are size customized for each set of shoe boxes to pack. The cardboard boxes will henceforth be referred to as containers. Different shoe sizes and models can be packed into each container to be delivered to a single customer. The shoe boxes are packed with the label facing up for easy inspection (See Figure 1). The goal of the company is to pack the full order while minimizing the number of containers and, as the containers are not fixed size, also minimizing their volume.

FIGURE 1 A CARDBOARD CONTAINER CONTAINING THE SHOE BOXES

Due to the frequent introduction of new models in the production environment, the manual selection of the box sizes is frequently a time-consuming task. Furthermore, empty space in the containers, mainly in those with different shoe box sizes, was common to find. For example, Figure 1 shows a container containing nine shoe boxes. However, some visible empty spaces could possibly be eliminated.

In this context, Savana wished to improve the packing process by eliminating manual box selection; reducing the choice of boxes and minimizing the empty space in a cardboard box; and automating the container design and zsubsequent packing of the individual boxes in each client’s order.

Therefore, Savana was facing two difficulties:

1. Assigning pairs of shoes to the appropriate shoe box;

2. Assigning shoe boxes to the appropriate container.

In this sense, the entire problem was split into two main packing stages. In the first stage, there is a box selection process in which the most suitable box is selected for each pair of shoes (size) with the constraints that shoe boxes cannot be too tight or too loose. As a goal, the number of selected box types should be kept to a minimum, since similar boxes are easier to pack. This resembles an assignment problem, where we minimize the number of different boxes used. This is a 0–1 linear programming model applied to every new type of shoe entering production.

The second stage deals with the packing process of the shoe boxes into one or more containers. The novelty of this problem lies in the fact that the shoe boxes are packed into several containers and each container has three open dimensions, which increases the difficulties. In this stage, we proposed a step-by-step procedure to reduce the inherent difficulties of dealing with the problem as a whole.

ASSIGNING SHOES TO BOXES

Pairs of shoes are appropriately arranged in the boxes as in Figure 2, and the boots are arranged as shown in Figure 3. Figures 2 and 3 show how a pair of shoes or boots should be placed in a shoe box. The red numbers are the size of the box and the shoe size.

FIGURE 2 SHOE BOX WITH A PAIR OF SHOES

FIGURE 3 SHOE BOX WITH A PAIR OF BOOTS

The box size should be chosen so that there is not too much empty space inside the box (see Figure 4) and, at the same time, there is no deformation of the footwear due to lack of space, as illustrated in Figure 5.

FIGURE 4 TOO LOOSE SHOE BOX

FIGURE 5 TOO TIGHT SHOE BOX

Every time Savana had a new model to produce, they would produce one pair of every size for this model, stop the production, and choose the appropriate shoe boxes manually for each size. We proposed a mathematical program to decide which shoe boxes should pack each model/size of footwear before production starts. This can be done in advance, because for each new model, Savana must produce a test model/size. With this test model, the measures of other sizes can be estimated and the appropriate shoe box chosen. In addition, the mathematical program minimizes the variety of different shoe boxes, which simplifies the packing of shoe boxes into containers.

PACKAGING SHOE BOXES INTO SEVERAL CONTAINERS

Shoe boxes are packaged into several customized containers made of cardboard, as seen in Figure 1. Due to customer’s restrictions on container sizes, the manufacturer usually packs no more than 20 boxes (or 10 boxes, in the case of larger boxes used for boots) in each container. The packing process of an even number of equal shoe boxes was already carried out efficiently by the company. But often the shoe boxes are not equal. For example, to pack 14 shoe boxes, they would make a container large enough to fit 14 shoe boxes, as if all boxes were equal and occupying the space needed for the largest one. Thus, they could pack orders as in Figure 6, with shoe boxes spread all over, which does not please their customers. For some reason, they also utilised tight cardboard containers that would deform the shoe boxes, see Figure 7.

FIGURE 6 TOO LARGE CARDBOARD CONTAINER

FIGURE 7 TOO TIGHT CARDBOARD CONTAINER

Despite the problem being easy to understand, and we can make use of a mathematical program, this is too large to be solved as a whole. Thus, we proposed a three-step technique.

The three steps are:

1. determine the number of containers to be used;

2. distribute the boxes within the containers;

3. calculate the sizes of the containers.

Step 1: Determine the number of containers

The determination of the number of containers was straightforward at Savana. They assumed that each container packages 20 boxes (for shoes) or 10 boxes (for boots), and then given an order, they decide the number of containers. Our first approach, during the meeting, followed these ideas. However, later, we argued that the threshold of 20 should be dropped and the number of shoe boxes could vary from container to container. Depending on the size of shoe boxes, the container may carry between a minimum of 10 and a maximum of 50 boxes.

Step 2: Distribute the boxes amongst the containers

The distribution of the boxes among the containers for a given order to a single customer was determined by ordering the shoe boxes by size. As boxes are easier to pack when they are similar, this is a good strategy.

We proposed a mathematical program to deal with the first two steps at the same time, which improved the process. We allowed the number of shoe boxes per container to not be fixed, but decided depending on a specific customer’s order. In the operational research literature this is called a bin-packing problem and can be solved using a mathematical program. This decides the number of containers and distributes the shoe boxes amongst the containers, where the goal is to minimize the number of containers. With this approach, the total number of containers used in a single order can be reduced.

Step 3: Calculate the sizes of the containers

In this step, the size of the containers and the exact position of each shoe box is determined. This process was done manually by the company, but their idea was to start to do it automatically. In this sense, it is important to precisely determine the size of each container and the exact position and orientation of each shoe box in it.

it is important to precisely determine the size of each container and the exact position and orientation of each shoe box in it.

In this step, we assumed that we know the number of containers and which shoe boxes are to be placed in each container. For this, we proposed another mathematical program whose goal is to minimize the volume of each container. This must be solved for each container.

The placement of shoe boxes into a container and the size of the containers must obey some constraints imposed by customers. They require that shoe boxes must be facing up for label inspection and can rotate. They are also preferably packed in one level for easy inspection. As a result of customer requirements, the size of the containers must satisfy the following constraints: (1) the longest edge cannot exceed 80cm; (2) the other two edges cannot exceed 60cm and (3) twice the width plus height added to the length cannot exceed 300cm. These impositions ensure that the container cannot be too large, and will not be too heavy.

CONCLUSIONS

Our work indicated how the overall packing process can be automatized and sped up. The process of assigning shoes to boxes is simple and can be implemented in a computer system. It gives a realistic estimate of the shoe box to be used for each size of a new model. This process only uses the measurements obtained from a test model/size.

The proposed process automatically determines the containers’ sizes and a near optimal arrangement of the individual shoe boxes inside containers and reduces the empty space inside containers.

When the number of boxes was larger than 13, the shoe manufacturer was packing shoe boxes on two levels. The manufacturer believed that it would be the only way to pack such a number of boxes without surpassing the container dimensions imposed by its clients. However, our work showed that using one level is often the best packing solution.

The implementation of the mathematical programming model proposed offers considerable time and cost savings.

The implementation of the mathematical programming model proposed offers considerable time and cost savings. Savana collaborator: ‘The implementation as a computer-program of the algorithm proposed to deal with decisions – how many containers are required to pack a customer's order and how to distribute the shoe boxes among the containers – has led to a significant reduction in time consumption of my work. I am very satisfied and I believe that the implementation of the proposed model will help the company save both time and money.’

Additional information

Notes on contributors

Manuel V.C. Vieira

Manuel V.C. Vieira is Assistant Professor at NOVA University of Lisbon and member of the research centers CMA-UNL (Portugal) and GERAD (Canada). He obtained his PhD on Optimization from TUDelft. His scientific interests are optimization problems with applications in industry, with publications on facility layout and container loading problems.

Flora Ferreira

Flora Ferreira is a researcher at the Centre of Mathematics at the University of Minho, Portugal. She received her Ph.D. in Mathematics from the University of Minho in 2014. Her research focus is on mathematical modeling, data analysis, and machine learning which is strongly driven by practical questions and multidisciplinary collaborations.