Wiskunde
A-lympiade: Voorronde 1992-1993
Het bevoorraden van filialen
Bij deze opgave hoort een SHELL-kaart.
Inleiding
Een distributiecentrum van een supermarktketen bevoorraadt een aantal filialen
enkele malen per week. Een filiaal moet de bestelling voor een bepaalde
dag al twee dagen eerder doorgeven. De bestelling wordt dan door de orderverzamelaars
op pallets geplaatst en klaargemaakt voor transport.
Voor het transport maakt men gebruik van een aantal transportbedrijven.
De middag van te voren wordt er een aantal vrachtwagens besteld. Er zijn
vrachtwagens met een capaciteit van 20, van 28 en van 40 pallets.
Bepaald wordt dan ook welke filialen tot een rit gecombineerd worden,
en hoeveel ritten een vrachtwagen op een dag maakt.
Verdere Gegevens
We beschikken over een prijzentabel waarin is af te lezen wat het huren
van een bepaald type vrachtwagen kost. De huurprijs is opgebouwd uit drie
delen, een vast bedrag, een bedrag per uur, en een bedrag per afgelegde
kilometer. Per dag kan een vrachtwagen gedurende ongeveer acht uur ingezet
worden.
|
Kosten in guldens |
Type Vrachtwagen |
Aantal Pallets |
per dag |
per uur |
per km |
1 |
20 |
160 |
50 |
0,45 |
2 |
28 |
200 |
50 |
0,50 |
3 |
40 |
240 |
50 |
0,55 |
Het huren van een vrachtauto van type 1 die gedurende zes uur gebruikt
wordt en waarmee 400 kilometer gereden wordt kost dus 160 + 6 * 50 +
400 * 0,45 = 640 gulden.
Het distributiecentrum ligt in Maarheeze, op 1 kilometer van de oprit
naar de A2.
Op een bepaalde maandag moeten vijfentwintig filialen bevoorraad worden.
De filialen en de aantallen af te leveren pallets per filiaal staan in
de volgende tabel.
Aantal pallets per filiaal |
1 |
Bergen op Zoom |
10 |
2 |
Boxtel |
7 |
3 |
Breda |
20 |
4 |
Den Bosch |
18 |
5 |
Deurne |
12 |
6 |
Dongen |
10 |
7 |
Echt |
9 |
8 |
Eindhoven |
21 |
9 |
Geleen |
14 |
10 |
Heerlen |
19 |
11 |
Helmond |
12 |
12 |
Maastricht |
18 |
13 |
Oosterhout |
15 |
14 |
Oss |
17 |
15 |
Roermond |
14 |
16 |
Roozendaal |
11 |
17 |
Sittard |
18 |
18 |
Tilburg |
19 |
19 |
Uden |
14 |
20 |
Valkenswaard |
11 |
21 |
Veghel |
9 |
22 |
Venlo |
16 |
23 |
Venray |
13 |
24 |
Waalwijk |
15 |
25 |
Weert |
14 |
Bij het rijden op snelwegen bedraagt de gemiddelde snelheid 80 kilometer
per uur, op binnenwegen 60 kilometer per uur, en in plaatsen en steden
20 kilometer per uur. Deze snelheden gelden voor alle typen vrachtwagens,
voor beide rijrichtingen en hangen niet af van de belading.
De binnen de gemeente af te leggen afstand naar het filiaal kan gesteld
worden op 2 kilometer met als uitzondering de plaatsen Breda, Eindhoven,
Heerlen, Maastricht, Tilburg en Venlo waar deze afstand ongeveer 4 kilometer
is.
Het laden van de vrachtwagens kost gemiddeld 10 minuten plus 1 minuut
per pallet. Het lossen kost ongeveer 10 minuten plus 2 minuten per pallet.
Opdracht
-
Op de Shell wegenkaart kun je zien wat de hoofdwegen en wat de binnenwegen
zijn. Bepaal met behulp van deze kaart welke verbindingen je toelaat en
wat deze in kilometers en in tijd kosten.
-
Bepaal een goede oplossing voor het bevoorradingsprobleem van deze maandag.
Geef vooral aan hoe je door gericht te zoeken tot deze oplossing gekomen
bent. Het gaat er niet om dat je de goedkoopste oplossing vindt. Veel belangrijker
is dat je een verstandig zoekproces ontwikkelt waarmee je met de hand (dus
zonder computer) een acceptabele oplossing kunt vinden.
Opmerking
Dit type probleem staat bekend als moeilijk. Bij een wat groter aantal
filialen neemt het aantal mogelijke ritten zo sterk toe dat het zelfs met
hulp van de computer niet meer mogelijk is het goedkoopste schema te vinden.
In de praktijk wordt daarom vooral gezocht naar algoritmen die vrij snel
een vrij goede oplossing genereren.