Chapter 6
Industrial insight
The model presented in Chapter 5 can handle basic constraints, which are nec-essary to include in the CLP, if it should be used in connection with a real world vehicle routing application. When dealing with problems faced by specific com-panies or industries, it must be expected, that the model should be adapted to handle different or further constraints. In this chapter, we will analyse and show the possibilities of incorporating such extensions, in the proposed model.
This is done by modelling two very different problems from companies facing the challenge of single container loading with multi-drop constraints in their everyday business.
6.1 Aarstiderne A/S - Distribution of vegetables
Aarstiderne A/S is a Danish company delivering organic vegetables, fruit and meat to the door step of 35.000 families all over Denmark. The delivery is on a weekly basis and the customers often change their requests. Aarstiderne offer around 30 distinct products with different selections of fresh vegetables, fruit or meat. Additionally, grocery products, such as cereals, wine and beer, are offered. The different products are all packed in boxes, of which there exists 10 different types. The different products are designed to meet the needs of
different sized families. Therefore, typically one or two boxes are demanded by each customer. In a typical packing problem there are between 100 and 200 boxes going to between 70 and 150 different customers.
Aarstiderne A/S both handle the packing of the groceries in the boxes as well as the overall distribution of the boxes. The boxes are distributed to depots around the country, and from each of these depots the boxes are delivered to the customers. It is this last delivery we have focussed on, as this is where the multi-drop constraint becomes most important.
Today, the vehicles are loaded, by the drivers. In the depot, the boxes with the same products are stacked together, see Figure 6.1. This means that the drivers have to walk around collecting the boxes needed on the route, as opposed to a situation, where the boxes are ranked in front of the vehicle slots. As such,
Figure 6.1: The distribution centre in Bjæverskov, Denmark
every driver has his own way of loading the vehicle. However, some common characteristics exist. The loads are to the greatest extent made so that, all the different products are available, at all times on the route. This is the way the multi-drop constraint is handled today. To minimise time used loading the vehicle, most drivers load the same products close together. We have not focused on this point in our model. The extra time used for the driver to pack a vehicle should be compared to the time saved unloading the vehicle on the route. Finally, when the driver drop of boxes at the customers, empty boxes
6.1 Aarstiderne A/S 53
from the last delivery should be picked up. This means that we have a delivery and pick-up system. It is, however, not a strict constraints that all empty boxes must be brought back, and moreover, is it significantly easier to bring back the empty boxes, as they can be placed inside each other, taking up much less room.
Therefore, we have chosen to neglect this issue.
6.1.1 Changes made to the model
The change made to the model is motivated by the fact, that a box only gives support to boxes placed above it, through its four corners. This is because Aarstiderne use open wooden boxes with no lid on. Two different boxes are depicted in Figure 6.2. If two boxes are placed on top of each other and the box on top has smaller base dimension than the one below, it would mean that the box above would not be supported and thereby damage the contents of the box below. Therefore, to require full support, boxes can only be stacked when all four corners of the boxes are resting directly above corners of a box below.
As long as the corners of the box are supported from below, there is no limit on (except for the container size) how many boxes can be stacked on top of each other. If high stacks have no support on the sides from other boxes, extendable poles are put up between the floor and ceiling in the container to make the load stable.
Figure 6.2: A picture of the “basic box” (left) and “fruit box” (right) with the boxes they are packed in.
To make sure that boxes are properly stacked, extra care should be taken when they are inserted on top of other boxes. This changes both the way we manage spaces but also the definition of a valid box placement.
The following procedures are changed:
• A valid box placement
• Update empty spaces:
– Amalgamation – Remove subsets
It is important to notice that when placing a box on the container floor, support is always guaranteed. This means that the following changes only concerns boxes placed on top of other boxes. In the same way a change in the amalgamation rule is only needed above the container floor.
6.1.1.1 A valid box placement
To be able to guarantee that boxes are supported in all four corners when placed, we check at insertion time whether this condition is true. For box iin spaces the check is:
∆ai = ∆xs∧
∆bi = ∆ys∧
∆ci ≤ ∆zs (6.1)
This check is used whenever a box isnotplaced on the floor. The check presumes that all spaces not starting at the floor are sized so that the corners have support.
It should of course still be checked if a placement is multi-drop feasible as defined in Section 5.4.2, page 46.
6.1.1.2 Update empty spaces
Since only boxes stacked directly on top of each other are valid, there is no longer any need to amalgamate empty spaces when the spaces are above the container floor. Therefore, the amalgamation is discarded for the spaces that are not starting on the container floor. Recall that amalgamation is not done on the container floor. This means that whenever working with problems like the ones from Aarstiderne, amalgamation should not be part of the procedures needed to update the empty spaces.