D2: Transportation
Imagine that you have passed all your D2 exams and have got rich. You are now the proud owner of three sweet shops and three warehouses. There has been a run on Twix bars lately and your shops need restocking.
Shop 1 needs 28 boxes of Twix, shop 2 needs 45 boxes and shop 3 needs 37 boxes.
Warehouse A can supply 32 boxes of Twix, warehouse B has 44 boxes ready to ship and warehouse C has 34 boxes.
All seems fine. Except that is costs £1.50 per box to deliver from warehouse A to shop 1 and £2.13 to deliver each box from warehouse A to shop 2 and ... I'll tell you what, I'll put this in a table.
| Shop 1 | Shop 2 | Shop 3 | Supply | |
|---|---|---|---|---|
| Warehouse A | £1.50 | £2.13 | £2.22 | 32 |
| Warehouse B | £1.75 | £2.04 | £2.18 | 44 |
| Warehouse C | £1.88 | £1.98 | £2.46 | 34 |
| Demand | 28 | 45 | 37 |
Now, here's the question... what is the cheapest that we can deliver all the stock to the shops?
North West Method
First we find a solution that works, regardless of cost.. What I mean is that we transport the goods so that all the warehouses are emptied and all the shops are filled.
The method we will use is called the north-west method because we start from the top left (north-west) corner of the table and send all the boxes from Warehouse A first, then move to B, then C. This clip explains what I'm on about.
Now that we've found a possible solution, we check to see whether we can do it cheaper or not. The method is to "pretend" that the costs are split between leaving the warehouses and arriving at the shops. This calls out for a clip...
Degenerate Solutions
If we haven't enough routes to figure out the separate costs, then the solution is degenerate. In this case, we need to "pretend" that we're transporting goods so we can calculate costs - the amount we transport is zero (see clip).
Now that we have figured out the costs that we're paying, we now see whether we're being ripped off or not. Remember that it's the price in the table that we will pay, so if that price is cheaper for a route than we are currently paying then we should use that route.
If we are being ripped off on more than one route, we will use the route that we're being ripped off the most. This will involve redirecting some boxes of Twix and it can become a little complicated. The method we use is called the stepping-stone method.
The Stepping-Stone Method
Basically, we can get a good deal if we use the routes that we're currently being ripped off on. We should try to redirect as much cargo as possible to this route. This is explained in this clip...
Now we find the new charges and see whether we're still being ripped off. If we are then we repeat the process, if not we're finished and can work out the total cost.
Unbalanced Problems
What if...there are more boxes of Twix in the warehouses than the shops need delivering?
Good question... we simply add a "pretend" dummy shop that needs the spare Twixs delivering. The cost for the routes is zero. Then we proceed as before.
This type of situation is called an unbalanced problem.