Modelleren C Appels Christian Vleugels
Sander Verkerk
Richard Both
15 juni 2010
Inhoudsopgave 1 Inleiding
2
2 Probleembeschrijving
2
3 Data
3
4 Aanpak
4
5 Deterministische aanpak 5.1 Populariteit van producten . . . . . . . . . 5.2 Verbanden tussen aanvoer en afvoer . . . . 5.3 Beste bingrootte per product . . . . . . . . 5.4 Meerdere optimale bingroottes per product 5.5 Minimaal benodigde ruimte . . . . . . . . . 5.6 Maximaal benodigde ruimte . . . . . . . . . 5.7 Oppervlakte bepalen . . . . . . . . . . . . .
. . . . . . .
4 4 5 6 7 8 9 10
6 Stochastische aanpak 6.1 Productanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Dataset genereren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Voorbeeld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12 12 13 15
7 Resultaten 7.1 Deterministische aanpak: Bins van 1 . . . . . . . . . . . . . . . . . . . . . . . 7.2 Deterministische aanpak: Grotere bins . . . . . . . . . . . . . . . . . . . . . . 7.3 Stochastische aanpak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16 16 19 20
8 Conclusie
21
9 Bronvermelding
21
1
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
1
Inleiding
Iedereen loopt wel eens tegen een ruimteprobleem aan, soms zonder dat je je er in eerste instantie van bewust bent. Stel dat je net een nieuwe kast hebt gekocht bij IKEA. De kast bestaat uit twee zijsteunen en een aantal planken die op elke gewenste hoogte in de kast geplaatst kunnen worden. Een mogelijkheid is dat je de planken op gelijke afstand van elkaar in de kast plaatst, maar is dit wel de beste oplossing? Je kiest ervoor om dit te doen en op het moment dat de kast gevuld is merk je dat je ruimte te kort komt voor je spullen. Je nieuwste bordspel past er niet meer in. Aan de andere kant heb je ook ’loze’ ruimte die niet gevuld is, maar daar past dat spel niet meer bij. Als je de indeling van de planken aanpast, bestaat er dan een oplossing zodat w´el al je spullen in de kast passen? In dit project zullen we gaan kijken hoe we grote aantallen appels kunnen opslaan in een distributiecentrum. Net als bij het kastenprobleem lopen we hier tegen een ruimtegebrek aan dat we mogelijk op kunnen lossen met een andere indeling. Allereerst zal er een beschrijving van het probleem gegeven worden. Hierna zal er een aanpak voor het probleem gegeven worden en daarna zal worden toegelicht wat er tot nu toe onderzocht is. Vervolgens worden de behaalde resultaten weergegeven en de conclusies worden toegelicht. Ook zal er een schatting worden gegeven van de benodigde ruimte die voor de gegeven data nodig is.
2
Probleembeschrijving
Een bedrijf runt een distributiecentrum met een groot aantal verschillende soorten appels. Een distributiecentrum is een grote hal waar producten volgens een aanvoerproces binnenkomen en er volgens een bestelpatroon weer uitgaan. In dit verslag wordt er dan ook gesproken over de aanvoer en de afvoer. Volgens de huidige indeling blijkt het distributiecentrum te klein om alle aanvoer op te slaan. Omdat uitbreiding erg kostbaar is, komt het bedrijf met de volgende hoofdvraag. Wat is de meest ruimte-optimale binindeling van het distributiecentrum, zodanig dat men alle producten kwijt kan gegeven het aan- en afvoerproces? Er zal zo worden uitgelegd wat er precies wordt bedoeld met een bin. Een antwoord op de hoofdvraag kan gevonden worden door naar een aantal deelvragen te kijken: 1. In hoeverre is er sprake van snellopende (populaire) producten? 2. Hoe verhouden de aankomst- en vertrekprocessen van elk product zich ten opzichte van elkaar? 3. In wat voor bin kan een bepaald product het beste worden geplaatst? 4. Wat is de minimale ruimte die benodigd is om de producten kwijt te kunnen? 5. In welke ordegrootte zal de maximaal benodigde ruimte moeten liggen? 6. Hoe kunnen we uit een binindeling de benodigde ruimte bepalen? De aan- en afvoer over een bepaalde periode uit het verleden zijn bekend. Aan de hand van deze gegevens zal er een indeling gemaakt moeten worden. De aan- en afvoer van producten 2
wordt gegeven in aantal pallets. Een pallet hoeft niet helemaal vol te staan, men gaat uit van positief, ree¨el aantal pallets. De pallets worden in het magazijn vervolgens opgeslagen in bins. Een bin is opslagruimte waarvan de grootte van tevoren is bepaald. Het is een verzameling palletplaatsen bij elkaar. De grootte van een bin is een natuurlijk getal en kan vari¨eren van grootte 1 tot grootte 5. Een product dat op een bepaalde dag binnenkomt, wordt opgeslagen in ´e´en of meerdere bins. In deze bins mogen geen andere producten opgeslagen worden zolang er nog producten liggen. Hierbij geldt ´e´en uitzondering: twee dezelfde producten die op dezelfde dag binnenkomen mogen wel bij elkaar in dezelfde bin gestopt worden, in alle andere gevallen dienen we gebruik te maken van een lege bin. Voor de afvoer van de producten geldt het FIFO principe (First-In = First-Out). Dit houdt in dat de producten die het langste in het magazijn aanwezig zijn als eerste moeten worden geleverd. Aanvoer die bestaat uit meer dan ´e´en pallet mag onbeperkt worden opgesplitst in kleinere hoeveelheden. Daarnaast dient het magazijn zowel een ingang als een uitgang te bevatten. Voor elke bin dient tevens een ruimte aanwezig te zijn zodat een vorkheftruck ruimte heeft om de producten te verplaatsen. Wij zullen ons probleem beperken tot het geval van vierkante pallets met een vaste grootte.
3
Data
De aanvoer en de afvoer is bekend over een periode van 100 dagen. Elke dag wordt gewerkt van ongeveer 6 uur ’s ochtends tot 8 uur ’s avonds. De data is opgesplitst in een aanvoerbestand en een afvoerbestand. Beide bestanden hebben een gelijkwaardige opbouw met de volgende gegevens: • Tijdstip van levering/bestelling (in seconden vanaf dag 1, 0:00) • Tijdstip van levering/bestelling (werkelijke tijd, in minuten) • ProductID/artikelnummer van het product dat wordt geleverd of besteld(7 cijferige productcode) • De grootte van de levering/bestelling in pallets (positief reel getal) Het magazijn heeft daarnaast de volgende eigenschappen: • Elke pallet heeft een grootte van 1 bij 1 meter. • V´o´or elke bin is een ruimte van 2 vierkante meter nodig om producten te kunnen verplaatsen. • Elk gangpad dient een breedte te hebben van minimaal 4 meter. • De grootte van een bin kan vari¨eren van 1 tot en met 5 pallets. De aanvoer is gegeven in een txt-file en bestaat uit 22430 leveringen. De afvoer is ook gegeven in een txt-file en bestaat uit 39964 bestellingen. Merk op dat in de data de tijd gewoon doorloopt op het momenten dat er niet wordt gewerkt (vanaf 8 uur ’s avonds tot 6 uur ’s ochtends op de volgende dag). In onze berekeningen zullen wij hier rekening mee houden.
3
4
Aanpak
We zullen het probleem van twee kanten benaderen. We beginnen met een deterministische aanpak. Gegeven een dataset zullen we een oplossing bieden voor het probleem. Daarnaast zullen we het probleem stochastisch benaderen. Bij deze aanpak zullen we de dataset ’extrapoleren’ en kijken wat voor gevolgen dit heeft op het uiteindelijke resultaat. Wij zullen voor beide gevallen een zo optimaal mogelijke oplossing moeten bepalen. Eerst zullen we een oplossing gaan zoeken door alleen gebruik te maken van bins ter grootte ´e´en. Hiermee bepalen we dan een onder- en bovengrens voor de ruimte die wij met grotere bins nog nauwkeuriger willen krijgen. Zo kunnen we bekijken of het gebruiken van grotere bins wel nut blijkt te hebben.
5
Deterministische aanpak
Van het probleem is veel data gegeven, hieruit vallen verschillende dingen af te lezen. We zullen deze onderdelen volgens de deelvragen behandelen.
5.1
Populariteit van producten
Deelvraag 1 heeft betrekking op de populariteit van de producten. Om de populariteit van producten vast te stellen zullen we hier kijken naar de gemiddelden en standaardafwijkingen. Later zullen we (bij de stochastische aanpak) ook gebruik maken van het aantal bestellingen per product. Om het gemiddelde en de standaardafwijking te bepalen, kijken we naar de aanvoer en afvoer per product. We selecteren daartoe steeds alle data van ´e´en product. Dit doen we door de aan- en afvoer bij elkaar te voegen tot ´e´en groot databestand. Dit bestand wordt dan gesorteerd op productnummer. Zo kan er per product het gemiddelde aantal pallets dat per levering aankomt en het aantal pallets dat per order wordt uitgevoerd berekend worden. Dit gemiddelde wordt berekend door van de aanvoer alle pallet-groottes bij elkaar op te tellen en te delen door het aantal aankomsten van dat product. Het gemiddelde voor de afvoer wordt analoog berekend. Voor de standaardafwijking van de pallet-grootte wordt de volgende formule gebruikt (de steekproefstandaardafwijking): v u n u 1 X s=t (xi − µ)2 (1) n−1 i=1
In deze formule staat n voor het aantal leveringen/orders van dat product, xi voor de grootte in het aantal pallets dat per levering wordt aangevoerd of het aantal pallets dat per order wordt uitgevoerd. De µ in de formule is het gemiddelde aantal pallets dat per levering wordt aangevoerd of het aantal pallets dat per order wordt uitgevoerd. Uit deze berekeningen volgen dus vier parameters: de gemiddelde grootte en de standaardafwijking van een pallet die aankomt en de gemiddelde grootte en standaardafwijking van een pallet die wordt uitgevoerd. Dit levert ons de volgende grafiek.
4
Figuur 1: Een weergave van de gemiddelde en standaardafwijking van de aanvoer en afvoer per product.
Veruit de meeste producten staan linksonder in de grafiek, deze producten hebben een laag gemiddelde en daarom een lage populariteit. Een aantal producten met een veel hogere populariteit springen er wel duidelijk uit. Merk hierbij op dat er bij de aanvoer een (lineair) verband bestaat tussen het gemiddelde en variantie van een product. Voor de afvoer bestaat er geen duidelijk verband, wel valt op dat bij veruit de meeste producten sprake is van hele kleine uitvoer met daarbij vaak ook een kleine variantie.
5.2
Verbanden tussen aanvoer en afvoer
Om de verbanden tussen de aan- en afvoer verder te bestuderen (deelvraag 2), hebben we ook de aan- en afvoer tegen elkaar uitgezet. We krijgen voor de gemiddeldes de volgende grafiek.
5
Figuur 2: Gemiddelde van de aanvoer (horizontale as) ten opzichte van het gemiddelde van de afvoer (verticale as).
Bij dit plaatje valt het op een groot deel van de producten op de diagonaal ligt waarbij de gemiddeldes van de aan- en afvoer ongeveer even groot zijn. Hieruit kunnen we concluderen dat producten met een kleine resp. grote aanvoer vaak ook in een kleine resp. grote bin gestopt zullen worden. Boven deze diagonaal zijn nauwelijks producten aanwezig, dus de producten worden over het algemeen in iets grotere hoeveelheden aangevoerd als afgevoerd.
5.3
Beste bingrootte per product
We zullen nu verder gaan met het bepalen van de beste bingrootte per product (deelvraag 3). Bij deze aanpak gaan we er vanuit dat we elk product in ´e´en soort bins gaan stoppen. Deze aanname zal het probleem drastisch beperken, maar nog steeds tot betrouwbare resultaten leiden. Om het meest gunstige aantal bins te bepalen voeren we een simulatie uit aan de hand van de data. We bekijken voor elk product hoeveel bins van 1 tot en met 5 er nodig zullen zijn om alles te kunnen verwerken. We zullen voor dit proces een voorbeeld geven. Stel dat we een product X hebben met de volgende aanvoer en afvoer. Tijdstip Soort Grootte 1 Aanvoer 2.5 2 Afvoer 1.5 3 Aanvoer 3.1 Tabel 1: Aanvoer en afvoer van een fictief product X In het geval dat we alleen bins ter grootte 1 willen gebruiken volstaan we met 5 bins, want 2 leveringen van hetzelfde product mogen niet in dezelfde bin worden geplaatst. In het geval 6
dat we alleen bins ter grootte 2 of 3 gebruiken hebben we 3 bins nodig. In het geval van bins ter grootte 4 of 5 hebben we aan 2 bins genoeg. Nu moeten we bepalen welk van de 5 bins gezien de benodigde ruimte optimaal is. Hiervoor hebben we van elke bin het effectieve gebruik bepaald. Bij elke bin hebben we een gangpad nodig van 2 meter breed, ongeacht de bingrootte die we gebruiken. Voor een bin ter grootte 1 betekent dit dat maar 13 van de ruimte effectief gebruikt wordt. Zetten wel al deze fracties in een tabel, dan krijgen we de volgende resultaten. Bingrootte 1 2 3 4 5 Effectief gebruik 13 12 35 23 57 Tabel 2: Fracties van het magazijn die effectief worden gebruikt We moeten nu bepalen welk van de 5 bins het beste presteert voor dit product. Dit doen we door totale aantal bins te delen door de factor die aangeeft hoeveel ruimte er effectief wordt gebruikt. Dit levert voor het voorbeeld de volgende resultaten. Bingrootte Benodigde oppervlakte
1∗5 1 3
1 = 15
2∗3 1 2
2 = 12
3∗3 3 5
3 = 15
4∗2 2 3
4 = 12
5∗2 5 7
5 = 14
Tabel 3: Voorbeeld van een berekening om de optimale bingrootte te bepalen In dit geval zijn bins ter grootte 2 en 4 dus het meest effectief. Wij zullen in dit geval voor het kleinste getal kiezen, aangezien kleinere bins makkelijker te gebruiken zijn voor andere producten.
5.4
Meerdere optimale bingroottes per product
´ en bingrootte per product zal niet leiden tot de meest optimale oplossing, in de praktijk E´ blijkt dit echter wel al een aanzienlijke verbetering te geven t.o.v. het gebruik van bins ter grootte 1. Het is ’dom’ om een product dat slechts twee aanvoergroottes heeft, bijvoorbeeld 0.8 en 4.9 pallets, steeds in dezelfde bingrootte te stoppen. Waarschijnlijk is het hier beter om te kiezen voor een opsplitsing: als er een aanvoer volgt ter grootte 0.8, stop hem dan in bins ter grootte 1. Volgt er een aanvoer ter grootte 4.9, stop hem dan in bins ter grootte 5. Om te kijken in hoeverre deze aanpassing invloed zal hebben op onze dataset hebben we eerst geanalyseerd hoeveel van de 198 producten er zijn met precies 2 aanvoergroottes. We kregen daarbij de volgende tabel. Aantal verschillende aanvoergroottes Aantal producten met deze aanvoergroote 1 53 2 108 3 18 4 17 5 2 Tabel 4: Aantal verschillende aanvoergroottes van elk product. Een soortgelijk verband was helaas niet terug te vinden in de afvoer. Hierbij vari¨eerden de afvoergroottes tussen 1 en 40 verschillende afvoeren per product. Omdat de aanvoergrootte 7
erg deterministisch is, hebben we de simulatie verder uitgebreid voor producten met precies 2 verschillende aanvoergroottes. We voeren de simulatie op soortgelijke wijze uit als bij de vorige paragraaf, alleen kijken we nu nu eerst naar de aanvoergrootte voordat we een aanvoer in een bepaalde bin plaatsen. In dit geval zullen we dus 25 (52 ) simulaties per product moeten uitvoeren in plaats van 5, wat binnen afzienbare tijd gebeurd. De methode geeft dus een aanscherping van de optimale binindeling waarbij per product een optimale bingrootte wordt gekozen. We hebben dit principe niet herhaald voor meer dan 2 verschillende aanvoergroottes, omdat wij verwachten dat de aanvoer van deze producten op langere termijn nog meer zal vari¨eren. Bovendien neemt de tijd om de simulatie te doorlopen kwadratisch toe en zullen de effecten kleiner worden vanwege het kleinere aantal producten waar dit op van toepassing is.
5.5
Minimaal benodigde ruimte
Naast de analyse per product is ook de volledige dataset onderzocht. Aan de hand van de data kunnen we een ondergrens en een bovengrens bepalen voor het aantal bins dat gedurende de 100 dagen nodig is in het magazijn. We zullen twee bovengrenzen en twee ondergrenzen bepalen zodat we een idee krijgen van het totale aantal bins in het magazijn. We beginnen met het bepalen van een ondergrens (deelvraag 4). De eerste ondergrens die we zullen bepalen is de beginsituatie. De geleverde dataset begint halverwege een proces en vertelt niets over de producten die op dat moment in het magazijn aanwezig zijn. Aan de hand van een bestand waar we de aanvoer en afvoer samen hebben gevoegd kunnen we bepalen welke producten een tekort hebben en dit tekort kunnen we gebruiken als beginsituatie. Dit tekort defini¨eren we als volgt: Zij N het totaal aantal producten, xi,Aan (t) de totale hoeveelheid pallets dat van product i is aangevoerd tot tijdstip t en xi,Af (t) de totale hoeveelheid pallets dat van product i is afgevoerd tot tijdstip t. We defini¨eren Yi dan als het aantal pallets dat we gedurende deze 100 dagen tekort komen van product i met: Yi = min{0, xi,Aan (t) − xi,Af (t)} t
(2)
De totale beginopstelling is dan de som over de absolute waarden van deze tekorten: Beginopstelling =
N X
| Yi |
(3)
i=1
Indien er nergens een tekort optreedt voor een product zal 0 pallets als beginopstelling worden gekozen. We geven ter illustratie nog een klein (fictief) voorbeeldje met 2 artikelen. Tijdstip 1 2 3 4 Tabel 5: Aanvoer
Soort Artikel Grootte Afvoer 1 1.8 Aanvoer 2 0.5 Afvoer 2 2.0 Aanvoer 1 3.0 en afvoer van twee fictieve producten
Hierbij is de minimale waarde die voor product 1 wordt bereikt -1.8 en voor product 2 is de minimale waarde -1.5. We nemen daarom als beginsituatie voor product 1 en 2 respectievelijk 8
1.8 en 1.5. Bij dit proces moet verder worden opgemerkt dat er in de beginsituatie geen rekening wordt gehouden met het FIFO principe. Hier kunnen we ook geen rekening mee houden, omdat wij geen informatie beschikken over hoe de aanwezige producten zijn aangevoerd. De beginopstelling is geen goede ondergrens, daarom bepalen we nog een betere ondergrens. We maken gebruik van de beginopstelling die we eerder bepaald hebben. Er wordt nu niet meer gekeken naar de aan- en afvoer per product, maar alleen naar de tijd. Er wordt op elk tijdstip gekeken hoe groot het totale aantal pallets is dat in het magazijn ligt. Nadat het hele bestand doorlopen is wordt, van deze aantallen pallets het maximum gekozen, zeg dat dit het geval is op tijdstip tmax . Defini¨eer het aantal pallets dat van product i aanwezig is op tijdstip tmax als xi (tmax ). Het totaal aantal pallets wordt naar boven afgerond omdat het aantal bins altijd geheel moet zijn. We krijgen nu als ondergrens: N X Ondergrens 1 = d xi (tmax )e
(4)
i=1
Deze ondergrens is echter nog steeds niet goed genoeg, daarom wordt er nog een ondergrens bepaald. We weten inmiddels dat op tmax het maximale aantal pallets aanwezig is. We zullen nu het hele aan- en afvoerproces gaan simuleren tot het tijdstip tmax is bereikt. Op dit moment weten we precies hoeveel bins er minimaal nodig zullen zijn van elk product en we ronden deze resultaten naar boven af. Door te sommeren over het totale aantal producten krijgen nu als betere ondergrens: Ondergrens 2 =
N X dxi (tmax )e
(5)
i=1
5.6
Maximaal benodigde ruimte
Om een beter beeld te krijgen van het aantal bins in het magazijn worden er ook twee bovengrenzen bepaald. De eerste bovengrens bepalen we door de producten afzonderlijk te bekijken. We doorlopen voor elk product het hele aan- en afvoerproces aan de hand van de tijd. Hierbij zullen we ook rekening houden met het FIFO principe. Hieruit bepalen we een tijdstip t voor elk product waarbij het maximale aantal bins in het magazijn nodig is voor dit product. We sommeren hierna over de producten, zodat we de eerste bovengrens krijgen. Zij xi (t) weer het aantal pallets dat van product i aanwezig is in het magazijn, dan volgt voor de bovengrens: Bovengrens 1 =
N X dmax{xi (t)}e i=1
t
(6)
Ter verduidelijking zullen we ook hiervan een voorbeeld geven. We gebruiken weer de gegevens uit Tabel 4. Hierbij hebben we eerder als beginsituatie voor product 1 en 2 respectievelijk 1.8 en 1.5 bepaald. In de beginsituatie zijn voor elk product dus 2 bins nodig. We houden nu voor elk product bij wat de maxima zijn na iedere aanvoer (na iedere afvoer worden de maxima nooit groter, om rekentijd te besparen kijken we hier dan ook niet naar). Dit levert ons de volgende resultaten op.
9
Tijdstip 0 1 2 3 4
Soort Artikel Grootte Bins product 1 Bins product 2 Beginsituatie 2 2 Afvoer 1 1.8 Aanvoer 2 0.5 0 3 Afvoer 2 2.0 Aanvoer 1 3.0 3 0 Tabel 6: Aanvoer en afvoer van twee fictieve producten
Merk op dat na tijdstip 2 precies 2.0 pallets van product 2 aanwezig zijn. Omdat het twee verschillende leveringen betreft mogen deze producten niet bij elkaar staan en wordt het binaantal dus 3. In dit voorbeeld vinden we als maxima voor de producten respectievelijk 3 en 3 bins. Als bovengrens nemen we nu 3 + 3 = 6 bins. Deze bovengrens is natuurlijk een veel te grote bovengrens, aangezien niet alle maxima van het aantal bins op hetzelfde tijdstip aanwezig zijn. Daarom wordt er nog een bovengrens bepaald. Bij de vorige bovengrens hielden we van elk product afzonderlijk bij hoeveel bins er voor dit product nodig waren, nu houden we van alle producten tegelijk bij hoeveel bins er nodig zijn. Na elke aanvoer tellen we nu de aantallen bins van alle producten op en hiervoor zoeken we het tijdstip t waarbij dit aantal maximaal is. Dit komt neer op het volgende resultaat: n X Bovengrens 2 = max dxi (t)e t
(7)
i=1
Toepassen van dit resultaat op Tabel 6 levert ons het volgende resultaat op. Tijdstip 0 2 4
Bins product 1 Bins product 2 Som van het aantal bins 2 2 4 0 3 3 3 0 3 Tabel 7: Totaal aantal aanwezige bins in het magazijn
Het maximale aantal aanwezige bins is in dit geval dus 4. Dit is een aanzienlijke verbetering ten opzichte van de eerste bovengrens. Voor al deze bovengrenzen moet nog een punt worden opgemerkt. We hebben bij deze berekeningen nog geen rekening gehouden met de uitzondering dat twee leveringen van ´e´en product die op dezelfde dag worden geleverd w´el bij elkaar gezet mogen worden. Deze bovengrens kunnen wij in de toekomst daarom nog iets nauwkeuriger maken.
5.7
Oppervlakte bepalen
We hebben nu voor een gegeven dataset bepaald hoeveel bins we nodig denken te hebben. We willen nu nog weten welke oppervlakte we nodig hebben om alles in het magazijn kwijt te kunnen (deelvraag 6). Dit komt neer op het bepalen van een functie f (x1 , x2 , x3 , x4 , x5 ) waarbij xi het aantal benodigde bins is ter grootte i. Het resultaat van de functie zal de totale benodigde oppervlakte zijn.
10
We kunnen voor de totale oppervlakte een redelijke benadering geven. Voor elke bin weten we wat de benodigde oppervlakte is: de grootte van de bin zelf in vierkante meters plus 2 vierkante meter aanvoer. De oppervlakte die we hiermee krijgen is een ondergrens, want de kans is groot dat we de bins niet netjes verdeeld krijgen over de gangen. Vanwege de onregelmatigheden die hierbij optreden zal het magazijn net iets groter worden. Dit levert ons de volgende formule op als ondergrens voor de oppervlakte in vierkante meters: f (x1 , x2 , x3 , x4 , x5 ) = x1 ∗ 3 + x2 ∗ 4 + x3 ∗ 5 + x4 ∗ 6 + x5 ∗ 7 Naast deze ondergrens kunnen we ook de totale oppervlakte benaderen. De bins kunnen we allemaal in gangen plaatsen, hierbij hebben we dan ook een middengang nodig om te zorgen dat alle bins in het magazijn bereikbaar blijven. De oppervlakte van de middengang kunnen we nu bepalen door simpelweg het totale aantal bins te tellen. De lengte van het gangpad is sterk afhankelijk van de breedte van het magazijn, we zullen de functie hiervoor aan moeten passen in f (x1 , x2 , x3 , x4 , x5 , n) waarbij n een gegeven breedte van het magazijn is. Omdat het gangpad 4 meter breed dient te zijn, kunnen we de lengte hiervan bepalen met de volgende formule: f (x1 , x2 , x3 , x4 , x5 , n) = f (x1 , x2 , x3 , x4 , x5 ) + d
f (x1 , x2 , x3 , x4 , x5 ) e∗4 n−4
,x3 ,x4 ,x5 ) naar boven af, zodat we op een rechthoekig magazijn uitHierbij ronden we f (x1 ,x2n−4 komen. Merk op dat dit slechts een benadering is, want onregelmatigheden in de gangen zijn niet meegenomen. Toepassen in de praktijk leert echter dat deze formule met het slim plaatsen van bins een goede benadering zal geven.
Nu is het natuurlijk de vraag: Hoe kunnen we bins slim in het magazijn plaatsen. Hiervoor hebben we een aantal trucs die in de praktijk toegepast kunnen worden. We zullen ze kort toelichten met behulp van een afbeelding.
Figuur 3: Een aantal trucs om bins op een slimme manier te plaatsen in een magazijn
In Schema 1 proberen we het gangpad optimaal te benutten door deze te verplaatsen naar de zijkant van het magazijn. Op deze manier wordt het gangpad ook benut als aanvoerpad voor de bins, zodat er maar eenmaal ruimte verloren gaat. In Schema 2 gebruiken we het gangpad dubbel door bins aan het einde van de gang tegen de zijwand aan te plaatsen. Door 11
deze hoeken ontstaat enige loze ruimte, maar deze loze ruimte kost minder dan de ruimte die gewonnen wordt aan de vermindering van gangpad. Het laatste schema laat zien hoe verschillende groottes van bins in een gangpad optimaal gecombineerd kunnen worden. Door deze combinaties van bins kan het magazijn een zeer regelmatige vorm krijgen met gangen van gelijke breedte. Door een magazijn te cre¨eren met het toepassen van deze trucs kan de benodigde oppervlakte flink worden beperkt.
6
Stochastische aanpak
We zullen nu op een meer stochastische manier gaan onderzoeken wat de optimale indeling is voor een aantal producten. We zullen dit doen aan de hand van de simulatie die bij de gegeven dataset gebruikt is. We gebruiken de gegeven data om een nieuwe dataset te genereren. Vervolgens zullen wij voor deze nieuwe dataset een optimale binindeling proberen te vinden.
6.1
Productanalyse
Dankzij de deterministische aanpak weten we nu in grote lijnen wat voor producten er in het magazijn liggen. We willen nu verder gaan onderzoeken (zie deelvraag 3) wat voor bingrootte er het beste bij elk product gebruikt kan worden. Aan de hand van de data hebben we al bepaald wat gegeven de volledige dataset de beste bingrootte is om voor een product te gebruiken. Wij willen dit proces nu nog verder vereenvoudigen. In plaats van een volledige simulatie willen wij voor een bepaald product direct kunnen zeggen wat voor bingrootte hier het beste voor te gebruiken is. We willen dit achterhalen aan de hand van het gemiddelde en standaardafwijking van de aanvoer en afvoer van een product. Hiervoor hebben wij twee vuistregels bedacht. De eerste vuistregel gaat alleen uit van het gemiddelde. Door te kijken hoe groot het gemiddelde van de aanvoer is, bepalen we in welke bin een product geplaatst moet worden. Betere resultaten dan de eerdere simulatie zal dit niet opleveren, maar het uitvoeren van deze vuistregel is wel eenvoudiger. We gebruiken voor deze vuistregel de volgende tabel. Gemiddelde aanvoergrootte µx Bingrootte 0 < µx ≤ 1 1 1 < µx ≤ 2 2 2 < µx ≤ 4 3 4 < µx ≤ 6 4 6 < µx 5 Tabel 7: Vuistregel aan de hand van het gemiddelde. Daarnaast hebben we een tweede vuistregel bedacht waarbij we ook rekening houden met de variantie. Deze vuistregel hebben we getekend in de onderstaande grafiek, waarbij we gebruik hebben gemaakt van de eerdere deterministische simulatie.
12
Figuur 4: De tweede vuistregel, de horizontale as geeft het gemiddelde van de aanvoer aan en de verticale as de standaardafwijking. Voor elk punt wordt een optimale bingrootte gekozen.
Bij deze vuistregel hebben we ervoor gekozen om een ellipsvormen te nemen bij het verdelen van de vlakken in de grafiek. Of dit de meest optimale vorm is kunnen wij niet zeggen, omdat wij hiervoor onvoldoende gegevens hebben. Wat we w´el weten is dat de verdeling op de lijn µ = 2 ∗ σ bijna optimaal is.
6.2
Dataset genereren
We willen ook zelf een dataset genereren om te zien in hoeverre grotere bins ook in de toekomst nut zullen hebben, dit doen we door gebruik te maken van het gemiddelde en standaardafwijking van de aanvoer en afvoer van alle producten. Verder speelt ook de tijd een rol. Hiervan kan ook het gemiddelde en de variantie van de tussenaankomst- en tussenafvoertijd berekend worden. Het gemiddelde van de tussenaankomsttijd wordt berekend door alle tijden tussen twee opeenvolgende aankomsten van ´e´en product bij elkaar op te tellen en te delen door het aantal aankomsten minus 1 (dat is dus het aantal tussenaankomsttijden). De variantie hiervan wordt ook weer met formule (1) berekend. Nu het gemiddelde en de variantie van het aantal pallets dat aankomt en wordt afgevoerd bekend is en ook het gemiddelde en de variantie van de tussenaankomst- en tussenafvoertijden berekend is, kunnen deze parameters gebruikt worden om een aan- en afvoerproces van verschillende producten te genereren. Omdat we de gemiddelden en de varianties van alle producten weten, ligt het voor de hand om de data aan de hand van een normale verdeling te genereren. Helaas levert een trekking uit een normale verdeling waarden op uit de gehele re¨eele rechte, terwijl wij juist niet-negatieve waarden voor de palletgroottes willen genereren. 13
In plaats daarvan maken we gebruik van de volgende verdelingen: • Exponenti¨ele verdeling Deze verdeling geeft voor een stochast X alleen positieve waarden. De verdeling heeft de volgende kansdichtheid: ½ λe−λx x ≥ 0; f (x; λ) = (8) 0 x < 0. • Hyperexponenti¨ele verdeling Deze verdeling is een ’mix’ van meerdere exponenti¨ele verdelingen, in ons geval gaan we uit van twee exponenti¨ele verdelingen. Als een stochastische variabele X hyperexponentie¨el verdeeld is, dan volgt dat X met kans p1 exponenti¨eel verdeeld met parameter λ1 en met kans p2 = 1 − p1 exponenti¨eel verdeeld met λ2 . • Erlang verdeling Deze verdeling heeft twee parameters: λ en k. De verdeling is de som van k identieke, onafhankelijke exponenti¨ele verdelingen met gemiddelde λ1 . In ons probleem komt het voor dat een stochastische variabele X een mix is van twee Erlang-verdelingen. X is dan met kans p1 Erlang verdeeld met parameters λ en k − 1 en met kans p2 = 1 − p1 Erlang verdeeld met parameters λ en k. Om erachter te komen uit welke verdeling we moeten trekken, kijken we naar de variatieco¨effici¨ent. Deze waarde is een maat voor de spreiding van een stochastische variabele X en wordt gedefinieerd door: p V ar(x) σx = (9) Cx = µx µx Hierin komen ook het gemiddelde µx en de variantie σx2 in voor die we uit de gegeven dataset hebben berekend. We berekenen voor ieder product de variatieco¨effieci¨ent van de aanvoergrootte, afvoergrootte, tussenaanvoertijd en tussenafvoertijd. Kenmerkend voor de exponenti¨ele verdeling is een variatieco¨effici¨ent met waarde 1. De verwachtingswaarde en variantie van de exponenti¨ele verdeling zijn respectievelijk λ1 en λ12 . Dit levert voor Cx dan: q
1 λ2 1 λ
=1
Trekken uit een Exponenti¨ele verdeling kan door de volgende formule te gebruiken: 1 X = − ln(U ) λ
(10)
Waarbij U een willekeurig getal is tussen 0 en 1. Als de variatieco¨effici¨ent Cx kleiner is dan 1, moet er getrokken worden uit de Erlangverdeling. De parameters van de mix van twee Erlang-verdelingen kunnen op de volgende manier berekend worden: p1 =
p 1 (kCx2 − k(1 + Cx2 ) − k 2 Cx2 ) 2 1 + Cx 14
p2 = 1 − p1 k − p1 λ= µx De variabele k wordt gehaald uit de volgende ongelijkheden: 1 1 ≤ Cx2 ≤ k k−1 Met kans p1 wordt uit een Erlang-verdeling getrokken met parameters k en λ en met kans p2 uit een Erlang verdeling met parameters k − 1 en λ. Als de variatieco¨effici¨ent groter is dan 1, moet er uit een Hyperexponenti¨ele verdeling worden getrokken. De parameters van de Hyperexponenti¨ele verdeling kunnen op de volgende manier worden berekend: s 1 Cx2 − 1 p1 = (1 + ) 2 Cx2 + 1 p2 = 1 − p1 2p1 λ1 = µx 2p2 λ2 = µx Met kans p1 wordt uit een Exponenti¨ele verdeling getrokken met parameter λ1 en met kans p2 uit een Exponenti¨ele verdeling met parameter λ2 . Om een nieuwe dataset te genereren moeten we voor ieder product een lijst van aanvoergroottes, afvoergroottes, tussenaanvoertijden en tussenafvoertijden genereren. We splitsen dit op de volgende manier op: Voor product 1 genereren we een aantal aanvoergroottes met tussenaanvoertijden totdat de som van de tussenaanvoertijden groter wordt dan 100 dagen. Daarna generegen we voor product 1 hetzelfde, alleen voor de afvoer. Als we hiermee klaar zijn, gaan we door met de overige producten, totdat we alle 198 producten gehad hebben.
6.3
Voorbeeld
We willen graag van product 1 een aanvoergrootte genereren. We weten van product 1 dat de aanvoer gemiddeld met 0,5 pallets aankomt en met een variantie van 0,25. We berekenen de variatieco¨effici¨ent en komen uit op: √ 0, 25 0, 5 = =1 0, 5 0, 5 Deze waarden is gelijk aan 1, dus moeten we gaan trekken uit een Exponenti¨ele verdeling waarbij we λ gelijk nemen aan µx = 0, 5. Het trekken uit een Exponenti¨ele verdeling is makkelijk, er kan gebruik worden gemaakt van formule (10). We trekken eerst een willekeurig getal tussen 0 en 1, bijvoorbeeld 0,731. Als we deze waarde voor U invullen en voor λ 0,5 invullen in (10) krijgen we: X=−
1 ln(0, 731) = 0, 626684 0, 5
Voor product 1 wordt de volgende aanvoergrootte dus 0,626684. 15
7
Resultaten
We zullen bij de resultaten weer een opsplitsing maken in twee delen: eerst kijken we naar de resultaten van het deterministische deel en vervolgens naar de resultaten van het stochastische deel. Binnen het deterministische deel zullen bij bovendien nog een opsplitsing maken tussen het onderzoek met bins ter grootte 1 en grotere bins. Voor ons onderzoek hebben we een programma geschreven in zowel de talen Java als Free Pascal. Deze keuze is bewust gemaakt omdat binnen het projectgroepje de ervaring met deze programmeertalen verdeeld lag.
7.1
Deterministische aanpak: Bins van 1
Eerst wordt de data uit de aan- en afvoer samengevoegd tot ´e´en tekstbestand. Omdat vooraf het aantal producten dat zich in de data bevindt niet bekend was, hebben wij eerst dit aantal bepaald. Het blijkt dat er 198 verschillende producten aanwezig zijn. Controle op de aparte aan- en uitvoerbestanden geeft aan dat er zowel in de aanvoer als in de afvoer 198 producten aanwezig zijn (wat een logisch resultaat is). Vervolgens hebben we de beginopstelling bepaald. De totale bingrootte van de beginsituatie in het magazijn is 432 bins. Hierbij is rekening gehouden met de verschillende producten door eerst de aantallen per product omhoog af te ronden en vervolgens pas op te tellen. Met andere woorden, als er alleen maar bins ter grootte ´e´en aanwezig zijn, dat moeten er minstens 432 bins in het magazijn klaarstaan. Zoals beschreven worden hierna ook de twee ondergrenzen bepaald. Het blijkt dat die ondergrenzen respectievelijk 622 en 694 bins bedragen. Verder berekent het programma wat het maximum aantal pallets per product is over de hele periode van 100 dagen. Door deze aantallen bij elkaar op te tellen krijgen we de eerste bovengrens. Deze bovengrens heeft een totale grootte van 1534 bins. Hierna simuleren wij het hele proces en houden wij op elk tijdstip het aantal benodigde bins ter grootte 1 bij. We hebben hiervan het aantal bins tegen de tijd uiteengezet in de volgende grafiek over een periode van ongeveer 24 dagen.
16
Figuur 5: Een plot van het aantal benodigde bins t.o.v. de tijd. De zwarte lijn geeft de grootste waarde en dus de bovengrens aan. Elke stip geeft een tijdstip aan waar producten zijn aangevoerd. Na elke aanvoer zijn alle aanwezige bins omhoog afgerond en vervolgens bij elkaar opgeteld.
Bij deze grafiek moet worden opgemerkt dat de schommelingen, die zich elke twee dagen herhalen, zeer opvallend zijn. Dit laat zien dat er de om de dag relatief veel aanvoer is, en de andere dagen relatief veel afvoer. De nauwkeurigere tweede bovengrens kunnen wij ook uit de grafiek aflezen en bedraagt 805 bins. Met de laatst bepaalde bovengrens kunnen we een magazijn cre¨eren waarin alle bestellingen verwerkt kunnen worden. Voor dit magazijn hebben we wel een aanname over de breedte moeten maken, we gaan daarbij uit van een breedte van 46 meter (dit blijkt een mooi vierkant magazijn op te leveren). Volgens de technieken zoals beschreven in sectie 5.7 hebben we het volgende magazijn samengesteld (zie figuur 6).
17
Figuur 6: Een mogelijk magazijn voor 805 bins ter grootte 1 van 46 bij 54 meter.
Met het programma worden verder de gemiddeldes en de varianties berekend. Ook zorgt dit programma voor een afvoer, die gebruikt kan worden om in Excel enkele grafieken te laten tekenen.
18
In de volgende tabel zijn het aantal bestellingen, het gemiddelde en de variantie van het aantal pallets te vinden voor zowel de aanvoer als de afvoer. Er is gekozen om alleen de informatie van de eerste 10 producten weer te geven, aangezien de tabel voor alle 198 producten ongeveer 4 pagina’s in beslag neemt. ProductID 3005501 3005510 3005512 3005520 3005521 3005710 3005801 7600101 7600401 7601801
7.2
Aanvoer Afvoer # Bestellingen Gemiddelde σ # Bestellingen Gemiddelde 72 0.5916 0.2979 997 0.0425 100 0.0528 0.0437 99 0.0533 67 1.3636 0.0 67 1.3636 100 0.0575 0.0017 100 0.0575 23 0.015 0.0 23 0.015 298 1.3889 0.1724 298 1.3889 130 5.778 2.8777 298 2.5 99 1.1602 0.58 611 0.1863 99 8.9519 4.4759 368 2.3965 132 2.0524 1.0301 462 0.5867 Tabel 8: Gemiddelde en Variantie eerste 10 producten
σ 0.0231 0.0437 0.0 0.0017 0.0 0.1724 0.3103 0.2725 3.0493 0.7136
Deterministische aanpak: Grotere bins
Nu wij een aantal boven en ondergrenzen hebben bepaald voor de data, hebben wij ook onderzocht wat het effect van het gebruik van grotere bins is. We zullen in plaats van in bins de aantallen vanaf nu vergelijking in oppervlakten zoals aangegeven met de formule f (x1 , x2 , x3 , x4 , x5 ) in sectie 5.7. Voor het resultaat van 805 bins geeft dit als oppervlakte 2415 vierkante meter. We hebben eerst een optimale bin per product toegepast zoals in sectie 5.3 beschreven. Dit leverde direct al een aanzienlijke verbetering op in de totale oppervlakte van het magazijn, namelijk 2066 vierkante meter. Toepassen van de methode zoals beschreven in sectie 5.4 levert nog verdere verbetering op en geeft 1967 vierkante meter. Hierbij hoort een indeling van 199 bins ter grootte 1, 77 bins ter grootte 2, 85 bins ter grootte 3, 49 bins ter grootte 4 en 49 bins ter grootte 5. Ook hiervoor hebben we een magazijn getekend met een breedte van 46 meter. De benodigde hoogte bleek nu echter nog maar 44 meter te zijn! Een besparing van ruim 18 procent in de ruimte.
19
Figuur 7: Een mogelijk magazijn van 46 bij 44 meter voor de optimale binindeling met in totaal 459 bins.
7.3
Stochastische aanpak
Nu de methoden en vuistregels bekend zijn en resultaten hebben opgeleverd voor de gekregen data, hebben we de twee nieuwe datasets gegenereerd aan de hand van de gemiddelden en varianties van de gekregen dataset. Op deze twee gegenereerde datasets zullen wij ons programma en methoden testen om te zien wat voor de nieuwe datasets de beste oplossingen zijn. Ook willen we graag uitrekenen hoeveel de besparing is bij het gebruik van meerdere 20
bingroottes ten opzichte van alles in bins ter grootte 1. De eerste dataset bestaat uit 22563 keer een aanvoer en 40368 keer een afvoer. Voor deze set is de beginopstelling 2713 bins. De tweede gegenereerde dataset bestaat uit 22710 keer een aanvoer en 39922 keer een afvoer. Voor deze tweede set is de beginopstelling 2759 bins. Op beiden sets laten we onze methoden los en daaruit volgen de volgende resultaten: Methode
Oppervlakte gekregen dataset 2415 2162 2174 2041
Oppervlakte gegenereerde dataset 1 12633 10541 10462 10374
Oppervlakte gegenereerde dataset 2 13059 10959 10964 10706
Bins van grootte 1 Vuistregel 1 Vuistregel 2 1 Optimale bingrootte Meerdere optimale 1967 10374* 10706* bingroottes Besparing t.o.v. 18,55% 17,88% 18,02% Bins ter grootte 1 Tabel 9: Totaal aantal aanwezige bins in het magazijn
In deze tabel zijn ook de resultaten vermeldt van de dataset die we van de opdrachtgever ontvangen hebben. Bij beide gegenereerde datasets is de oplossing van 1 optimale bingrootte en meerdere optimale bingroottes hetzelfde (zie *-teken in tabel 9). Dit komt omdat de methode van Meerdere optimale bingroottes in de aanvoer zoekt naar producten die slechts in twee verschillende aanvoergroottes aankomen. In de gekregen dataset van de opdrachtgever kwam dit bij ongeveer honderd producten voor, maar in onze twee nieuwe datasets komt dit vanwege onze stochastische benadering helemaal niet voor. Vandaar dat de twee oplossingen hetzelfde zijn.
8
Conclusie
De hoofdvraag van ons probleem was als volgt ’Wat is de meest ruimte-optimale binindeling van het distributiecentrum, zodanig dat men alle producten kwijt kan gegeven het aan- en afvoerproces?’. Wij hebben voor onze dataset reeds een optimale binindeling gegeven bij de resultaten. Het meest opvallende resultaat is dat het gebruik van bins daadwerkelijk nut blijkt te hebben, met een besparing van ongeveer 18 procent op de totale magazijnruimte.
9
Bronvermelding • H. C. Thijms Stochastic Modelling and Analysis, 1986.
21
