It should be able to handle them, as well as more complex problems. The time limit used is also a consideration. As said we have set the time limit to 60 seconds, while this vary much between other authors. Bischoff and Ratcliff [3]
use a single construction method, while the results by Bortfeld et al. [5] and Eley [10] are obtained, using a time limit of 10 minutes. In Bortfeldt and Gehrings genetic algorithm [4] a time limit of 500 seconds is used. Moura and Oliveira reports that average solutions times are under 64 seconds, when they perform 200 iterations of their GRASP approach [24]. The solution times reported by Lim and Zhang [20], spans between 1 and 4600 seconds.
Our results are not fully competitive with the the newest methods developed to solve these academic problem instances. However, within a reasonable time limit we still obtain an average volume utilisation above 90%.
Many authors have also reported results for either a relaxed stability measure or no assurance of stability at all. This generally allows for larger volume utili-sation. A hybrid parallel method developed by Mack et al. [21] reports average volume utilisations around 93,8% obtained within 10 minutes. A GRASP ap-proach by Parre˜no et al. [26] also gives volume utilisation around 94%. We have chosen not to focus on tests within this area, even though reducing the demand for support for the boxes is possible, in our implementation.
11.2 Aarstiderne 119
On average only 26% of the container is filled, and the problem taking up most space fills half of the container. An example of a packing is seen in Figure 11.2.
This problem consists of 152 boxes going to 108 customers. The same packing is shown on the two figures, but from different angles. The colours on the left figure indicate the sequence on the boxes, blue colours indicate low sequence and red colours high. The colours on the right figure indicate the different box types, the blue boxes are standard boxes with fruit and vegetables, the red boxes are specialities like meat, fish or beer.
Figure 11.2: An example of an Aarstiderne packing (optimal solution).
The picture of the packing shows a half filled container, the volume utilisation is only 37%. The boxes are stacked according to the specified rules for Aarstiderne, therefore it is seen that only boxes with the same base area are stacked. The effect of the sequence constraint, is easily seen by the bands of changing colours on the left figure. The packing has many stacks that do not expand to the top of the container. It is easy to see, that the boxes with specialities are hard to place. There are only few of them that are alike, which in combination with the sequence constraint, means that they cannot be stacked.
Figure 11.3: On the left, the route corresponding to the Aarstiderne packing shown on Figure 11.2. On the right a truck packed with groceries, ready to leave the depot.
On Figure 11.3 to the left, the route corresponding to the packing seen on Figure 11.2 is shown. The route is seen to be in the area around Horsens.
As all the data used corresponds to routes actually driven, the test shows that Aarstiderne has a very low volume utilisation on their loads. The reason for this could be, that other constraints than the capacity are binding, when looking on the combined problem of vehicle routing and container loading. This could for instance be the maximal allowed driving time for the driver.
On Figure 11.3 to the right, a loaded Aarstiderne truck, ready to deliver gro-ceries, can be seen. It is seen on the picture that the limits concerning stacking is reasonable, it is also seen that the truck is not heavily loaded - which the test has shown, is the general case.
The results clearly show, that the trucks are overdimensioned, compared to the loads driven and a suggestion could be, to use smaller trucks to deliver the goods.
11.2 Aarstiderne 121
11.2.2 Generated problems - smaller container
The test on the original data from Aarstiderne did not really give an opportunity to show the performance of our algorithm. The problems were to easy. Because of this, we have chosen to generate some new problems based on the original Aarstiderne data. To make the problems harder the container is reduced in size. Three new settings have been tested, where the size of the container is reduced between 35% and 55%. Figure 11.4 shows the results, with a time limit of 10 seconds. The horizontal axis shows the ratio between the volume of the
Figure 11.4: The connection between volume utilisation and ratio of boxes packed.
Aarstiderne data. Time limit: 10 seconds.
boxes and the container in a problem. On the plot, the dots are connected two and two, so that for a chosen box/container volume ratio, a pair of black and red dots corresponds to the solution to one problem. The black dot shows the volume utilisation of the solution, the red shows the percentage of the volume of the boxes packed. This means that if the red dot is at 100%, the solution is optimal. The graph shows that as long as the boxes fill less than 70% of the container, an optimal solution is always found. For a ratio above 70% the volume utilisation flattens out, and the highest volume utilisation is around 80%. At the same time the percentage of packed boxes falls. Optimal solutions are not found when the ratio is above 80%, and cannot be guaranteed when the ratio is between 70% and 80%. When the total volume of the boxes is the
same as the container volume (the ratio is 1) only about 70% of the boxes are contained in the solution.
Figure 11.4 shows, that for the Aarstiderne data, the box/container ratio should be above 70% for the problems not to be trivial. When the ratio is higher we cannot guarantee optimality in all cases, but some problems are solvable. A volume utilisation above 80% is, however, rarely seen.
That problems with a box/container ratio up to 70% and many customers are solved to optimality, are explained by the OR-Library test, Figure 11.1. As the box types of Aarstiderne are not that diverse, the multi-drop constraint is not limiting the solution space much. This allows high volume utilisations even for problems with many customers.
On Figure 11.5 the same consignment as on Figure 11.2 can be seen, but the container has been reduced in size. This is done by lowering the container roof from 190cmto 90cm, a reduction of 53%. The solution shown is optimal and has a volume utilisation of 78%. It was found within 10 seconds. Compared to Figure 11.2, the boxes are placed with greater care. More stacks are filled to the roof. As the problem no longer is easy the algorithm is forced to make more clever choices.
Figure 11.5: An example of an Aarstiderne packing, where the container room has been reduced with 53% (optimal solution).