Dynamic tree breadth

10.2 Tuning tree search 107

utilisation is above 75% for the short runs and 76,5% for the long runs. When this is compared to the test using static breadth, see Figure 10.5 and 10.7, it can be seen that the dynamic breadth performs better then the static, no matter which static breadth is used. Figure 10.9 shows, that the best setting for the breadth weight factor ψis either -1 or 0. This means that the breadth of the tree in the top should be kept relatively narrow. Moreover, it is seen that a greedy space choice is better than trying insertion in all spaces. This indicate that the faster greedy space choice in quality is close enough to trying all spaces. In Figure 10.10 results are shown when the data groups are varied.

Figure 10.10: Performance dependencies on data groups, the number of customers and the breadth weight factorψ. Time limit: 60 seconds.

The left graph shows the average achieved volume utilisation, when one customer exists in the problems. The right graph shows the average volume utilisation, when 50 customers are present in the problems. Both graphs are based on results obtained with a time limit on 60 seconds. Graphs showing results for the remaining customers and with a 10 seconds time limit, can be seen in Appendix D, Figure D.5 and D.6.

On the graphs it is seen, that when the number of customers is low (here 1) there is no big difference between the different choices of ψ. However, when many customers exist, ψ should not be chosen to large. This will be analysed further in the next section.

10.2.2.2 Time usage and obtained depths

Even though the dynamic breadth seeks to use all the time given, it is not always possible. This is because the calculated breadth is only based on an estimate of the actual time it would take to complete the search with the given breath. In some cases, this will lead to too few solutions and the algorithm will terminate prematurely. Because of this, it is interesting to find out how large a part of the available time is used and how deep the search gets into the tree, when the dynamic breadth is used. The results are found in Figure 10.11. From the

Figure 10.11: The part of the available time used (left) and the depth obtained (right) with dynamic breadth and different breadth weight factors. The top graphs are based on 10 seconds runs and the bottom ones are based on 60 seconds runs.

graphs on the left in the figure, it is seen that almost all the available time is used. Only for the fast runs with low breadth weight factor and few different box types, this is not the case.

Just as for the static breadths, it is seen on the top right graph that when the time limit is 10 seconds, we are generally not able to get to the bottom of the search tree. Here the results forψ=−1 andψ= 0 looks very much alike. This

10.2 Tuning tree search 109

is because the only breadths found is either 1 or 2, as these are the smallest valid choices ofλ. In this case the obtained depths should be close to the results found for the static breadth with λ= 1 andλ= 2, which is also the case. By choosingψ= 2 it is clear that we do not get very deep in the search tree, both when the time limit is 10 seconds and when it is 60 seconds.

When 60 seconds is used and many different box types exist (BR6 and BR7), we are not able to get to the bottom of the search tree. This, again, is because the breadth cannot be chosen small enough. The overall conclusions on this test is, that 10 seconds is simply not enough time to search to the bottom of the search tree, when more than 3 box types exist in the problem. The dynamic breadth, however, is able to choose breadths which utilise all the time available, and whenever possible also gets to the bottom of the search tree. The later is seen on the bottom graphs. This, of course, depends on the choice ofψ.

From Figure 10.9 it was found, that the best choice for ψ is either -1 or 0.

In combination with Figure 10.11 this shows, that overall it is better to get rather deep in the search tree, than seek thoroughly in the top nodes of the tree. The results for ψ = −1 and ψ = 0 from Figure 10.9 does not deviate much. Marginally better results are, however, obtained with ψ = 0, which is therefore chosen. This means that the breadth should be kept relatively unchanged throughout the search.

The test shows that whether the time is spent in top of the tree or further down, becomes increasingly important when considering more customers. When there are just one or two customers, greedy solutions found in the top are typically pretty good, but when considering many customer this is not the case. Instead time should be spent going faster down the tree, so that boxes placed later also will be explicitly placed by the tree.

10.2.2.3 Chosen breadths

When the dynamic breadth is used, it is interesting what breadths are actually chosen. Since the breadth can change in every iteration, no single measure can be given describing the size of the breadth. We have chosen to report the average-, start- and end breadths as well as the overall average breadth used throughout a run. This should give a good indication of whether the breadth is adjusted reasonably compared to the time limits.

In Figure 10.12 the results are shown. The different data groups are shown on the horizontal axis and the average start and end breadths and the overall average breadths are shown on the vertical axis. The top graphs show the average start breadth, the middle graphs show the overall average breadth and the bottom graphs show the average end breadths.

Graphs to the left indicate runs with 10 seconds used and graphs to the right indicate that 60 seconds have been used.

On the top two graphs in Figure 10.12 the start breadth are shown. These relate to each other exactly as expected, meaning that a higher choice of ψ yields larger start breadths. This is independent of the data groups. It is also seen that different start breadths are chosen depending on the different data groups and on the available time. On the middle graphs the overall average breadth is shown. Here, the exact opposite relation between the breadth weight factors are present. The result should be seen in combination with the bottom graphs showing that the end breadth becomes much larger, when the start breadth is small. This is a natural development as less time is used in the beginning when the start breadth is small, which means that more time is available later in the search tree and a wider search can be performed. The figures show that the adjustments of the breadth made with the dynamic breadth strategy, depends of the problem size and the number of box types. It is also seen that ψ is effective in controlling whether time should be used in the top or bottom of the tree.

From all six graphs in Figure 10.12 it is clear, that many different breadth have been chosen. This choice is seen to depend on both the data group, the time available and the choice of ψ. A single value for λ - as chosen by the static breadth - will never be able to describe this diversity.

10.2 Tuning tree search 111

Figure 10.12: Start, average and end breadth when 10 or 60 seconds are used.

Method SB, not accelerated and greedy space choice.