WisFaq!

Planning van ritten

Voor een PO heb ik een opdracht over een supermarktketen. Er zijn 19 supermarkten die een bepaald aantal keren per week bevoorraad moeten worden. De onderlinge afstanden en reistijden zijn bekend. Ook de plaats van het distributiecentrum is vastgesteld dmv matrices.

Situatieschets:
Ik weet dat er in totaal 55 grote vrachtwagens moeten rijden. Door een zo goed mogelijk uitgezochte planning en combinatie van ritten kom je op 45 grote en 4 kleine vrachtwagens. Kleine vrachtwagens kunnen maar de helft van een grote vervoeren. Het duurt 2 uur om een grote vrachtwagen te laden, een kleine duurt 1 uur. Met lossen is het hetzelfde verhaal: grote 1 uur, kleine een half uur.
Tot zover de praktische aspecten. Er is ook nog een kostenplaatje. Een chauffeur kost 250 euro per dag ongeacht de vrachtwagen. Een kleine vrachtwagen kost 2000 euro per week, een grote 3500.
Verder is gegeven dat een chauffeur maximaal 8 uur werkt en alleen doordeweeks.

Hoe kan ik een zo goed mogelijke planning maken zodat het aantal te huren vrachtwagens tot een minimum wordt beperkt?
Ik zou ervoor kunnen kiezen om twee keer zoveel vrachtwagens te huren dan dat er chauffeurs zijn. Terwijl de chauffeur zijn eerste rit rijdt wordt de tweede vrachtwagen geladen. Zo kan de chauffeur continu onderweg zijn. Maar uiteraard is dit niet goedkoop.
Bovendien zijn kleine vrachtwagens relatief duurder dan grote. Misschien met half lege vrachtwagens rijden? Aannemend dat de bestemmingen voor kleine wagens niet op de route liggen en het onpraktisch is om dit te combineren.

Hoe los ik dit ingewikkelde probleem op?

Pluseight
4-6-2007

Antwoord

Beste pluseight,

Jouw probleem lijkt een beetje op andere problemen: 'Chinese Postman Problem'.

Maar het is toch ietsje anders.

Klopt de volgende schets?

S: supermarkt
D: distributiecentrum

  S1---S2
    \    /
S3--D---S4
  \  /  \  /
   S5  S6

Maar dan met 19 supermarkten. [er zijn natuurlijk ook wegen tussen supermarkten, soms wel soms niet, hangt af van de situatie].

Waarschijnlijk heb je alle informatie in een matrix staan
    | D  | S1 | S2 | S3 | S4 | S5 | S6 | ...
--------------------------------------------
D   | 0  |     |     |     |      |     |      |
S1 |     | 0  |     |     |      |      |      |
S2 |     |     | 0  |     |      |      |      |
S3 |     |     |     | 0  |      |      |      |
S4 |     | x  |     |     | 0    |      |      |
S5 |     |     |     |     |      | 0   |      |
S6 |     |     |     |     |      |      | 0   |
.   |     |     |     |     |      |      |      |
.   |     |     |     |     |      |      |      |
.   |     |     |     |     |      |      |      |

De 'x' betekent dat de afstand van S4 naar S1 x km is. Je zou kunnen volstaan met een onderdiagonaalsmatrix, maar je kunt hem ook symetrisch maken. (Afstand van S4 naar S1 is even lang als van S1 naar S4. Is dit niet zo, dan vul gewoon een andere afstand in). De '0' is logisch, want er is geen afstand tussen van 'X' naar zichzelf.

Vervolgens, ik heb nog steeds meer informatie nodig. Het vullen van een vrachtauto, kan dat opgevat worden als vullen met een liquide middel als water, of heeft elk pakketje een bepaalde inhoud? [Stel een vrachtauto heeft ladingsruimteafmetingen: a·b·c. Als je er water in doet, dan kun je de complete ruimte benutten, maar met kratten zal het niet precies passen en moet je kijken hoe je het beste moet stapelen.]

Ik denk dat je dit probleem het beste met een LP (Linear Programming Problem) kunt oplossen. Dit is echter niet zo gemakkelijk, maar ik wil je best helpen met het opzetten van het LP. Een LP maakt wel gebruik van 'liquid filling' en houdt geen rekening met stapelen van kratten, het denkt dat de kratten vloeibaar is en overal in de vrachtauto gezet kan worden.

Een LP is een maximaliseringsprobleem. Er zijn gratis programma's te vinden op internet die een LP voor je oplossen als jij hem invult. Ik kan je helpen zo'n LP op te stellen.

Stuur meer informatie naar het onderstaand email-adres en ik zal je proberen te helpen. Natuurlijk zal ik je alleen maar helpen en niet al het werk voor je doen. Het is jouw PO natuurlijk.

Zoals Jadex mij al aanvulde: er is al eerder onderzoek gedaan. Pluis dat eerst eens uit, voordat je zelf teveel doet.

Google lemmata:
Distributieprobleem, noodwesthoek, methode van Vogel, stepping stone methode

Literatuur:
Kwantitatieve toepassingen in de bedrijfskunde. A.Buijs

pd
7-6-2007