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

  1. 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.
  2. 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.