Static tree breadth

In the first test we use a static breadth. This is done to evaluate the influence of the breadth, both on the solution quality, but also on the time used and how it depends on the reached depth in the tree. The different tested breadths are λ∈ {1,2,5,10,100}. Along with the breadth, we have tried settings to test both accelerated search and not, and if the space choice in the tree search should be made greedy or not. Finally there are 4 different greedy methods, which can be applied in the tree search. This gives a total of 28.000 test runs.

10.2.1.1 Overall performance

In Figure 10.5 the overall results, when a time limit of 10 seconds is applied, are shown. The results cover a very wide aspect of different problem types

-10.2 Tuning tree search 101

Figure 10.5: Aggregated results for the different methods with different breadths.

Time limit: 10 seconds.

problems with between 1 and 50 different customers and 3 and 20 different box types.

The results clearly show that the effect of accelerating the search is negative.

This is sound for all the different greedy methods and applies both when all spaces are tried and when this choice is made greedy. Hence, at least when there is no prior knowledge to the problem, the search should not be accelerated.

Based on the graphs in the figure, it is not possible to say anything about the best setting for the breadth. It does, though, seem as if, a smaller breadth is better when using the greedy space choice whereas a larger breadth is better when trying insertion in all spaces, but the difference is minimal. It is notewor-thy, that if the search is accelerated, it is always better to keep the tree wide.

The generally bad results found with the accelerated search can be explained by the fact that we look in the container for empty spaces. When there are several customers in the problem, focusing only on empty spaces is not enough to guarantee better loads. The big issue when there are several customers is,

whether the placement of a new box makes other boxes infeasible. Hence, the search for spaces alone is not enough to guarantee that the boxes we leave in the solutions are loaded in a good way.

It can also be seen, that whenever method BS is used, it should be done in combination with a tree search setup where the spaces are chosen by the search, and thereby not done greedily by method BS.

However, as seen in Figure 10.6, looking only on the data where one customer is present, the effect of accelerating the search cannot be disregarded. Here it can be seen, that for method ST the accelerated search outperforms the not accelerated version and for method VL the accelerated search is competitive with the not accelerated alternatives. But for both SB and BS, there is no advantage in accelerating the search. The same results are found when 60 seconds are

Figure 10.6: Performance when one customers exists in the problems. Time limit:

10 seconds.

given as time limit and when the breadth is chosen dynamically. This is shown on Figures D.2 and D.3 in Appendix D.

10.2 Tuning tree search 103

Figure 10.7: Aggregated results for the different methods with different breadths.

Time limit: 60 seconds.

In Figure 10.7 the time limit is changed to 60 seconds, but otherwise the same test setup is used as in Figure 10.5. Overall the average volume utilisation have increased. This increase is more profound when the tree search is not accelerated.

As for the 10 second runs, it is seen that when using a greedy insertion the breadth should be smaller than when trying insertion in all spaces.

Based on the 10 and 60 seconds run (Figure 10.5 and 10.7) it can be seen that method SB without acceleration overall outperforms all other greedy methods.

This is the case for all breadths tested. Because of this, only method SB without acceleration, is considered in further tests.

10.2.1.2 Time usage and obtained depths

When the breadth is static, there is no guarantee that all time available will be used trying to find a good solution. Moreover, it is not known how deep in the tree the search will get. If the breadth is chosen too small, the search will terminate early of its time limit. On the other hand if the breadth is chosen too large the search will terminate still being in the top of the search tree. The effect of this will be revealed in this section.

In the following we will use the measurerelative depth, to express the relation between the depth reached when the search terminates and the number of boxes loaded in the best found solution.

In Figure 10.8 the results of the test are shown. On graphs to the left, the part of the used time is shown and on graphs to the right, the relative depth is shown. On the graphs it is seen, that whenever the breadth is small, not all

Figure 10.8: The part of the available time used (left) and the depth obtained (right) with different static breadths. The top graphs show results with a time limit of 10 seconds, and the bottom graphs with a time limit of 60 seconds.

10.2 Tuning tree search 105

the time available is used. However, it is also seen that only when the breadth is small, there is enough time to search to the bottom of the search tree. It is so both when the time limit is 10 seconds and when it is 60 seconds. It is clear that when 60 seconds are available, the tree search reaches further down in the tree. This is easily seen on the graphs showing the relative depth (right), but also on the left graphs, where a much higher percentage of the runs terminate prematurely. From the tests with a time limit of 10 seconds, it is interesting to follow the results obtained with the breadth equal 1. When we look at the left graphs we see that many solutions terminate early of the time limit. On the right graphs, however, it is seen, that even with the smallest possible breadth, we are sometimes unable to reach the bottom of the tree. This is the case, if the number of box types are greater than 3 (BR2-BR7). This indicates, that 10 seconds is very little time, compared to the complexity of the problems.

Furthermore, there is a clear connection between the different data groups and the results. This tells us that, not surprisingly, more time is used, in each node, when more different box types exist in the problems. The same correlation is found with the number of boxes present in the problems.

The overall conclusion of this section is that the breadth should be chosen based on the type of problem that should be solved when a fixed time limit must be kept. This is exactly the purpose of the dynamic breadth.

Even though not all the time is used when the breadth is small, the solutions obtained are competitive with the solutions found by the wider breadths. This was shown in Figure 10.5 and 10.7. This means that good solutions can be obtained when the search gets deeper in the search tree, as well as when the tree is kept wide.