long tree poles. Figure 11.7 (right) shows a selection of these products. The pictures show that it is a key factor to be able to measure the load bearing strength (LBS) of the products. A ton of stone cannot be placed on top of some tiles for the bathroom.
Customer # Dimensions Rotations Weight LBS Description
L×W×H(cm) kg kg/cm2
- - 720×250×280 - 9500* - The truck
1 (Dark blue) 3 240×90×58 0×0×1 777 0.1 Gypsum boards
1 1 360×90×16 0×1×1 193 0.02 Gypsum bars
1 4 100×60×53 1×1×1 3 0.0002 Rockwool
2 (Light blue) 2 100×100×113 0×0×1 900 0.1 Founda. blocks 3 (Turquoise) 1 120×80×70 0×0×1 250 -1 Tiles
4 (Green) 1 420×95×83 0×0×1 1500 0.1 Tree poles
4 1 450×112×65 0×0×1 1500 0.1 Tree poles
4 1 500×85×35 0×1×1 100 0.1 Wood boards
4 1 38×31×29 1×1×1 5 -1 Cardboard box
5 (Yellow) 1 228×60×16 0×1×1 40 0.03 Flooring 6 (Orange) 3 200×120×265 0×0×1 75 -1 Rockwool
*The capacity of the truck
Table 11.7: List of products corresponding to the packing shown on Figure 11.6.
Comparing the solution of Figure 11.6 with the packing list, it can be seen that tiles and some gypsum boards are placed on top of the wood, stone is placed on stone, and rockwool is placed on top of both wood, gypsum and stone. These would all be realistic choices.
The route corresponding to this load can be seen on Figure 11.7 to the left. The route is seen to be run all the way across Northern Sealand. Two customers are
Figure 11.7: To the left, the route corresponding to the Johannes Fog packing shown on Figure 11.6. To the right, some of the products included in the packing.
11.3 Johannes Fog 125
placed by the green mark (Sjællands Odde) on the map. Because of the great distance travelled with this load, the value of packing all the boxes is high.
The test shows, that we are able to solve the problems corresponding to the loads actually driven by Johannes Fog, and within a very short time. This shows that the model is flexible enough to allow realistic loads to be packed.
A concern could be that the model is not strict enough, and it is possible to pack loads that would not be feasible in a real world scenario. To test this, new random problems are generated.
11.3.2 Generated problems - new random consignments
The problems from Johannes Fog were all solved to optimality, without testing the algorithm to a great extend. To put the algorithm to a harder test, new problems have been generated. The new problems have been generated by gathering all the products collected at Johannes Fog, keeping the information of which customer each product belongs to. From this list of about 80 products, random customers have, in groups, been assigned to loads. In this way 9 new problems have been generated, each containing between 4 and 9 customers and the total volume of the boxes is between 28% and 86% of the container volume.
The problems are listed in Appendix C. The sequence of the customers is chosen randomly without considering the actual route. In Table 11.8 the results of a test where the tree search has run for 10 seconds is shown.
Min. Avg. Max. SD.
Volume utilisation 24,16 44,54 61,97 14,47
Time 1,26 6,30 9,57 2,47
Table 11.8: Test results for the nine random consignments. Time limit: 10 seconds.
It is seen that the average volume utilisation is 44,5%, nearly twice as high as for the original problems. However, in none of these problems all boxes are placed. On average, only 63% of the time has been used, indicating that for a very short run, with relatively few boxes, the dynamic breadth does not have enough opportunity to adjust itself.
The test shows, that even for the problems with only around 30% box/container volume ratio, all boxes cannot be placed. This shows that for problems of this type, with many highly odd sized boxes, the volume ratio alone is not a very good indication of how hard a problem is to solve. The characteristics of each box makes a difference. This is because of the very different types of boxes and their ability to carry other boxes.
Figure 11.8: An example one of the generated problems using Johannes Fog products.
Two boxes have not been packed.
In Figure 11.8 an example of a solution to one of the generated problems can be seen. The problem has 4 customers and a total of 25 boxes. The volume utilisation is 34%. In the solution, two boxes have not been packed. In Table C.9 in Appendix C the packing list corresponding to the problem can be seen. The colours blue, turquoise, yellow and red (hidden) on the left figure correspond to customers 1, 2, 3 and 4. The boxes not packed are some 5,4 metres long wooden planks and a heavy sack of concrete. By only looking at Figure 11.8, it could seem, that there is a large area unused on top of the four equally large turquoise boxes, where the concrete could easily be placed. It should be remembered, that those boxes actually represent four sacks of cement mix, and that it is impossible to stack on top of the uneven surface of such sacks. It is easy to see that the long wooden planks, going from one end of the truck to the other, are hard to place without neglecting the sequence constraint.
Figure 11.8 clearly shows, that if the solution should be used for more than a feasibility check, a secondary objective is needed. The rockwool placed last (blue boxes), is just piled up in one end to the full height of the container. To make the load more stable they could just as well have been placed next to each other. The reason why the algorithm stops, is that it does not matter where the boxes are placed, as long as they are inside the container.