UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2008 – 2009
EEN GEÏNTEGREERDE OPLOSSINGSAANPAK VOOR ORDER-PICKING IN MAGAZIJNBEHEER
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur
Peter Louis onder leiding van Prof. Dr. Birger Raa
UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2008 – 2009
EEN GEÏNTEGREERDE OPLOSSINGSAANPAK VOOR ORDER-PICKING IN MAGAZIJNBEHEER
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur
Peter Louis onder leiding van Prof. Dr. Birger Raa
Vertrouwelijkheidclausule Permission Ondergetekende verklaart dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding. Peter Louis
Woord vooraf De masterproef is het sluitstuk van mijn studie Handelsingenieur, optie operationeel management. In deze masterproef wordt het orderpikken in magazijnen bestudeerd en wordt getracht dit proces verder te optimaliseren met behulp van wetenschappelijke methodes. De inhoud van de masterproef sluit bijgevolg perfect aan bij de gekozen afstudeerrichting. De combinatie van een literatuurstudie en een eigen experiment, toegepast op een concreet bedrijfseconomisch proces sprak mij zeer aan. Daarenboven is het optimaliseren van dit proces ook economisch relevant. Graag wil ik Prof. Dr. Birger Raa en Thomas Vanhove bedanken, bij hen kon ik steeds terecht met vragen over de programmeercode. Daarnaast ben ik ook Sabine Louis dankbaar voor het ter beschikking stellen van studiemateriaal. Ten slotte wil ik ook mijn ouders danken voor de kansen en steun die ik van hen heb gekregen.
I
Inhoudstafel 1.
Inleiding
1
2.
Situering van orderpikken in de supply chain
3
3.
Belang van orderpikken in magazijnbeheer
4
3.1. Een efficiënte supply chain
4
3.2. Kostprijs
5
3.3. Besluit
6
4.
Beslissingen in magazijnbeheer
7
4.1. Strategisch
7
4.2. Tactisch
8
4.3. Operationeel
8
4.4. Besluit
9
5.
Orderpikken: een combinatorisch probleem
10
5.1. Inleiding
10
5.2. TSP en Steiner TSP
10
5.3. BPP
11
5.4. VRP
11
5.5. Optimaliseren van reistijd of reisafstand?
13
5.6. Heuristiek of exact algoritme?
14
5.7. Besluit
15
6.
Batching- , routering- en sorteringstrategieën in de wetenschappelijke literatuur
6.1. Routering
16 16
6.1.1. Inleiding
16
6.1.2. Exacte algoritmes
17
6.1.3. Heuristieken
17
6.1.3.1. Heuristieken in magazijnen bestaande uit één blok
18
6.1.3.2. Heuristieken in magazijnen bestaande uit meerdere blokken
18
6.1.4. Brede langsgangen
22
6.1.5. Besluit
23
6.2. Batching
24
6.2.1. Inleiding
24
6.2.2. Exacte algoritmes
25
6.2.3. Metaheuristieken
26
II
6.2.4. Proximity batching 6.2.4.1. Data mining / Clusteranalyse
28
6.2.4.2. Seed algoritmen
29
6.2.4.3. Savings algoritmen
30
6.2.5. Time window batching
32
6.2.6. Besluit
33
6.3. Sorteren
36
6.3.1. Inleiding
36
6.3.2. Sort-while pick vs. pick-and-sort
36
6.3.3. De invloed van het batchingproces op het sorteerproces
37
6.3.4. Order-to-lane algoritmen
38
6.3.4.1. Heuristieken
39
6.3.4.2. Exact algoritme
40
6.3.5. Besluit 7.
28
40
Eigen empirisch onderzoek
7.1. Algoritmen
42 42
7.1.1. Routering
42
7.1.1.1. S-shape
42
7.1.1.2. Kortste pad routering
42
7.1.2. Samenvoegingprocedure
43
7.1.2.1. S1
43
7.1.2.2. INS
44
7.1.3. Batching
45
7.1.3.1. Seed algoritme
45
7.1.3.1.1 FCFS
45
7.1.3.1.2 SNPA – SNAPA
45
A. SNSA – SNASA
46
B. SNA – SNAA
46
7.1.3.1.3 SNB – SNAB
46
7.1.3.2. Savings algoritme
46
7.1.3.3. Gready Heuristieken
47
A. Ordersplitsing is niet toegelaten
47
B.
48
Ordersplitsing is toegelaten
7.1.4. Verbeteringsalgoritmen
48
III
7.1.4.1. Swap items
48
7.1.4.2. Swap orders
49
7.1.5. Geïntegreerde methodes
51
7.2. Algemene assumpties en lay-out van het magazijn
52
7.3. Aantal herhalingen
53
7.4. Definitie reisafstand en benuttinggraad
54
7.4.1. Reisafstand
54
7.4.2. Benuttinggraad
54
7.5. Programmeercode
54
7.6. Experiment 1
55
7.6.1. Onderzoeksvragen
55
7.6.2. Onafhankelijke variabelen
55
7.6.3. Afhankelijke variabelen
56
7.6.4. Resultaten
56
7.6.4.1. Statistische test
56
7.6.4.2. Bespreking resultaten
58
7.6.4.2.1 Benuttinggraden
58
A. Beste methode
58
B. Invloed van de lay-out
59
C. Invloed van de capaciteit
61
7.6.4.2.2 Reisafstanden
62
A. Beste methode
62
B. Invloed van de verbeteringsheuristiek
64
C. Invloed van de lay-out
65
D. Invloed van de capaciteit
68
7.7. Experiment 2
70
7.7.1. Onderzoeksvragen
70
7.7.2. Onafhankelijke variabelen
70
7.7.3. Afhankelijke variabelen
72
7.7.4. Resultaten
72
7.7.4.1. Statistische test
72
7.7.4.2. Bespreking resultaten
72
A. Invloed van de vaste kost op de reisafstand
72
B. Invloed van de vaste kost op de totale kost
73
IV
7.8. Experiment 3
74
7.8.1. Onderzoeksvragen
74
7.8.2. Onafhankelijke variabelen
74
7.8.3. Afhankelijke variabelen
74
7.8.4. Resultaten
76
7.8.4.1. Statische test
76
7.8.4.2. Bespreking resultaten
76
A. Reisafstand en benuttinggraad
76
B. Invloed van ordersplitsing op het sorteren
77
7.9. Besluit 8.
Algemeen besluit
78 80
8.1. Samenvatting en conclusies
80
8.2. Beperking van het onderzoek
83
8.3. Richtlijnen voor verder onderzoek
83
V
Lijst van tabellen 7.1 Overzicht van de geïntegreerde methodes
51
7.2 Vaste parameters experimenten
53
7.3 Variabele parameters experiment 1
55
7.4 Betrouwbaarheidsintervallen voor de gemiddelde benuttinggraad
59
7.5 Benuttinggraad in functie van de lay-out van het magazijn
59
7.6 Benuttinggraad in functie van de capaciteit
61
7.7 Betrouwbaarheidsintervallen voor de gemiddelde reisafstand
63
7.8 Gemiddelde procentuele afwijking ten opzichte van de kortste reisafstand
64
7.9 Gemiddelde procentuele winst in reisafstand door toepassing van het verbeteringsalgoritme
64
7.10 Gemiddelde reisafstand in functie van de capaciteit
69
7.11 Gemiddelde procentuele afwijking ten opzichte van de beste reisafstand in functie van de capaciteit
69
7.12 Variabele parameters experiment 2
71
7.13 Vaste kosten experiment 2
71
7.14 Gemiddelde benuttinggraad en reisafstand per methode voor experiment 2
72
7.15 Aantal keer dat de methode de laagste totale kost opleverde (%)
73
7.16 Variabele parameters experiment 3
74
7.17 Gemiddelde benuttinggraad en reisafstand per methode voor experiment 3
76
7.18 Gemiddeld aantal orders per batch en SR per methode in functie van de capaciteit
77
VI
Lijst van figuren 3.1 De kosten van magazijnbeheer opgesplitst naar activiteit
6
3.2 Opsplitsing van de tijd besteed aan orderpikken
6
5.1 Schematische voorstelling van het magazijn als een netwerk van knooppunten
11
6.1 Literatuuroverzicht van de batchingalgoritmen
35
7.1 Procedure voor S1
44
7.2 Procedure voor INS
45
7.3 Procedure voor G1 en G2
47
7.4 Procedure voor SI
49
7.5 Procedure voor SO
50
7.6 Gemiddelde benuttinggraad in functie van het aantal langsgangen (a)
60
7.7 Gemiddelde benuttinggraad in functie van het aantal blokken (a)
60
7.8 Gemiddelde benuttinggraad in functie van het aantal langsgangen (b)
61
7.9 Gemiddelde benuttinggraad in functie van het aantal blokken (b)
61
7.10 Gemiddelde reisafstand per methode
63
7.11 Gemiddelde reisafstand in functie van de lay-out van het magazijn
66
7.12 Gemiddelde reisafstand per methode in functie van het aantal blokken
67
7.13 Gemiddelde reisafstand per methode in functie van het aantal langsgangen
68
7.14 Gemiddelde reisafstand per methode in functie van de capaciteit
70
VII
1. Inleiding Excellent logistiek beheer is cruciaal om 24u per dag, 7 dagen op 7 aan de vraag te kunnen voldoen. De supply chain moet echter niet enkel responsief zijn maar ook kostenefficiënt. Een belangrijke kostenpost is orderpikken, deze activiteit neemt ongeveer 50% van de kosten in magazijnen voor zijn rekening (Tompkins, 2003 en Aminoff et al., 2002).
In deze masterproef zal onderzocht worden hoe de efficiëntie van het orderpikproces kan geoptimaliseerd worden in een picker-to-part magazijn bestaande uit één of meerdere blokken. Meer specifiek worden de mogelijkheden onderzocht om deze efficiëntieverhoging te bereiken via een integratie van de operationele processen gerelateerd aan het orderpikken. Gu, Goetschalckx en McGinnis (2007) en Van Landeghem (2007) onderscheiden als gerelateerde processen: batching, routering en sortering. We zullen ons hoofdzakelijk richten op de keuze van de batchgrootte, het batching- en het routeringalgoritme. Bestaande oplossingsmethoden worden eerst bestudeerd via een literatuuronderzoek en vervolgens gesimuleerd en vergeleken met nieuwe geïntegreerde methoden door middel van twee experimenten. Om ook het sorteerproces in beschouwing te nemen zullen de gevolgen van de gekozen batchingmethode op de sorteerkosten besproken worden. Ten slotte wordt in een derde experiment een aanzet gegeven om met de sorteerkosten rekening te houden tijdens het batchen en routeren. In dit laatste experiment worden ook de potentiële voordelen van ordersplitsing geëvalueerd. De keuze van het order-to-lane toewijzingsalgoritme als operationele beslissing zal slechts kort aan bod komen en wordt enkel besproken in de literatuurstudie.
Integratie van de processen gerelateerd aan het orderpikken (batchen, routeren en sorteren) betekent enerzijds dat wordt gestreefd naar een globaal optimum in plaats van elk proces lokaal te optimaliseren. Anderzijds kan integratie van het batchen en routeren ook betekenen dat deze processen niet sequentieel worden uitgevoerd maar dat reeds tijdens het batchen een route wordt geconstrueerd. In deze masterproef worden methodes voorgesteld die aan beide definities van integratie voldoen.
Bij de bespreking van de literatuur inzake batching, routering en sortering zal gewezen worden op de significante en relevante invloed van factoren zoals het opslagbeleid en de lay-out van het magazijn. We willen er echter op wijzen dat de focus in deze masterproef ligt op de integratie van de operationele processen gerelateerd aan het orderpikken zoals beschreven in Gu et al. (2007). Er zal
1
in de literatuurstudie dus geen apart hoofdstuk gewijd worden aan het bespreken van de vraagstukken inzake opslagbeleid of lay-out.
Deze masterproef is als volgt gestructureerd. In deel 2 en 3 zal het orderpikproces gesitueerd worden in de supply chain en het economisch belang ervan toegelicht. Deel 4 zal vervolgens dieper ingaan op de verschillende beslissingen die moeten genomen worden in magazijnbeheer. In dit deel wordt aangegeven welke processen later in detail zullen besproken worden. Vervolgens wordt in deel 5 het batching- en routeringvraagstuk beschreven als een combinatorisch optimalisatievraagstuk. In deel 6 wordt de literatuur inzake routering, batching en sortering in detail bestudeerd. De uitgevoerde experimenten worden besproken in deel 7. Ten slotte volgt in deel 8 een algemeen besluit.
2
2. Situering van orderpikken in de supply chain Orderpikken is de activiteit waarbij men goederen uit opslaglocaties haalt als reactie op de vraag van een klant (De Koster, Le-Duc en Roodbergen, 2007). Met andere woorden: het verzamelen van orders in magazijnen. Deze activiteit behoort tot het studiedomein van magazijnbeheer, welke op zijn beurt een onderdeel is van logistiek en supply chain management. Orderpikken wordt ook vaak ingedeeld in de categorie ‘materials handling’, een activiteit binnen magazijnbeheer. Om de context waarin orderpikken plaatsvindt te verduidelijken wordt in dit deel kort een omschrijving gegeven van bovenstaande begrippen. Supply chain management is het beheer van materiaal-, geld- en informatiestromen, zowel intern als tussen verkopers, productie- of assemblagebedrijven en distributiecentra (Thomas en Griffin, 1996). Logistiek is nauw verwant met Supply chain management en sommige auteurs gebruiken deze termen dan ook door elkaar. Waters (2003) definieert Logistiek als een functie die verantwoordelijk is voor het transport en opslag van de producten tussen de leveranciers en klanten, voor de verplaatsing van de materialen van de leveranciers naar de organisatie, naar operaties binnen de organisatie en naar klanten. Volgens Chen, Huang, Chen en Wu (2005) zijn in Logistiek de te onderscheiden activiteiten: transport, voorraadbeheer, orderafhandeling en magazijnbeheer. Waters (2003) vindt het belangrijk om geen arbitraire grenzen te trekken tussen de verschillende functies, ze moeten namelijk samenwerken om een efficiënte stroom van materialen te verkrijgen. Logistiek management en supply chain management refereren volgens hem dan ook naar dezelfde functie waarbij het uiteindelijke doel moet zijn om een zo hoog mogelijke klantentevredenheid te bereiken. Magazijnbeheer kan men omschrijven als het geheel van activiteiten binnen een magazijn die gerelateerd zijn aan de beweging van de goederen binnen het magazijn (Chen en Wu, 2005). De traditionele of primaire activiteiten binnen magazijnbeheer zijn volgens hen het ontvangen en opslaan
van
de
goederen,
orderpikken,
sorteren
en
verzenden.
Daarnaast
speelt
informatietechnologie een belangrijke ondersteunende rol. Deze zorgt er voor aan de andere activiteiten binnen het magazijn efficiënt kunnen worden uitgevoerd. Materials handling ten slotte gaat over de verplaatsing van materialen of producten over korte afstanden in een magazijn, productiehal of tussen deze gebouwen en transporteurs (Coyle, Bardi en Langley, 2003).
3
3. Belang van orderpikken in magazijnbeheer 3.1 Een efficiënte supply chain Waar in het verleden de nadruk lag op het in voorraad houden van grondstoffen, work-in-process en afgewerkte producten is de rol van magazijnbeheer nu meer en meer strategisch: kortere cyclustijden, lagere voorraadniveaus en betere klantenservice zijn de nieuwe objectieven (Coyle, Bardi en Langley, 2003 en Rouwenhorst et al., 2000). Ook Aminoff et al. (2002) merken op dat de lat voor logistieke activiteiten in de supply chain alsmaar hoger ligt: lotgroottes worden kleiner, nieuwe IT systemen ontwikkeld en meer en meer waardecreërende activiteiten aangeboden. Daarenboven is levering binnen de 24 uur geen uitzondering meer. Dat logistiek rekening moet houden met de klant weet ook Novich (1990): grofweg 50% van de klachten zijn volgens hem te wijten aan slecht logistiek beheer. Tegenwoordig is ook de postponement strategy, waarbij halfafgewerkte producten of modules in voorraad worden gehouden en de uiteindelijke afwerking of aanpassing wordt uitgesteld tot op het allerlaatste moment, zeer populair. Deze strategie wordt onder meer toegepast om grote voorraden van licht variërende eindproducten te vermijden, maar ook om de trend te kunnen volgen naar meer gepersonaliseerde orders. Men evolueert in de richting van mass customization: de mogelijkheid voor een bedrijf om een groot aantal producten op maat te maken en deze te leveren tegen een prijs, die deze van de traditionele massaproductie evenaart. Dit veronderstelt echter een flexibele supply chain waarbij er een vlotte doorstroming is van producten, materialen en informatie (Waters, 2003 en Rouwenhorst et al., 2000). Bowersox, Closs en Cooper (2002) (in: Theys en Herroelen, 2005) schrijven dat magazijnbeheer op dit moment slechts een strategische waarde bezit als zij bepaalde voordelen kan bieden. Zij onderscheiden economische en servicegerelateerde voordelen. Economische voordelen bestaan onder meer uit consolidatie, opsplitsen van bulk in kleinere hoeveelheden, sorteren, voorraadvorming en de eerder genoemde postponement strategie. Servicegerelateerde voordelen dragen bij tot een verhoogde dienstverlening, bijvoorbeeld het aanbieden van een uitgebreid productassortiment op één plaats, ook wel een ‘one-stop-shop‘ genoemd. De stijgende concurrentie en globalisatie verplicht daarenboven bedrijven om snel te reageren op de vraag van de klant. Om competitief te blijven moeten diezelfde bedrijven tezelfdertijd de operationele kosten verminderen. De klant wordt dus aan de ene kant veeleisender terwijl aan de andere kant de kosten onder controle moeten blijven (Thomas en Griffin, 1996). Om die reden is het
4
uiterst belangrijk te weten wat de klant echt wil en wat hij waardeert. Een essentieel element is de doorlooptijd van een order, dit is de tijd tussen het bestellen van producten en de levering bij de klant (Waters, 2003). Het efficiënt pikken van orders kan een middel zijn om deze doorlooptijd te verminderen. 3.2 Kostprijs Al deze logistieke eisen hebben ook hun kostprijs. Delaney (2000) (in: Jane en Laih, 2005) concludeerde dat logistieke kosten 10,9% van het bruto nationaal product van de VS uitmaken, waarvan 8% van dat bedrag zou besteed worden aan magazijnbeheer. Ballou (1992) (in: Apte en Viswanathan, 2000) berekende dan weer dat voor veel producten in de VS het aandeel van de logistieke kosten in de kost van het product tot 30% kan oplopen. Ook Waters (2003) weet dat kosten met betrekking tot logistiek 15 tot 20% van de omzet van een bedrijf kunnen bedragen waarbij de helft wordt besteed aan transport en de andere helft aan magazijnbeheer. Een meer recente studie van ELA/AT Kearny (2004) (in: De Koster et al., 2007) concludeerde dat magazijnbeheer goed is voor 20% van de totale logistieke kosten van de onderzochte bedrijven. De kost van magazijnbeheer kan dus hoog oplopen. Volgens Aminoff et al. (2002) tellen arbeidskosten mee voor 40% van de totale kost van magazijnbeheer. Aangezien orderpikken een arbeidsintensieve activiteit is, is het niet verwonderlijk dat het aandeel van orderpikken in deze kost zeer hoog zal zijn. Zo berekende Coyle et al. (2003) dat de kost van orderpikken 65% van de totale operationele kosten in een magazijn bedraagt. Volgens Aminoff et al. (2002) zouden pikactiviteiten verantwoordelijk zijn voor 24% van de tijd besteed aan activiteiten in het magazijn. Drury (1988) (in: Gademann en Van De Velde, 2005). meende zelfs dat 60% van het werk in een magazijn bestaat uit het verzamelen van orders. Om de productiviteit van warehousing activiteiten op te drijven stellen zij dus beide dat pikmethodes de nodige aandacht moeten krijgen. Wanneer het pikken op een efficiënte manier tot stand komt kan dit daarenboven de doorstroming van de producten versnellen (Chen et al., 2005). Ook Le-Duc en De Koster (2007) menen dat flexibel en productief pikken cruciaal is om aan de huidige klanteneisen te voldoen. Aangezien orderpikken frequent plaatsvindt kan een kleine verbetering reeds aanzienlijke besparingen opleveren (Chen et al., 2005) Tompkins et al. (2003) berekenen ten slotte dat de pikker 50% van zijn tijd besteedt aan het lopen van de ene opslaglocatie naar de andere. Deze tijd duidt men aan met de term reistijd en de afgelegde afstand is bijgevolg de reisafstand. Het lijkt dus meer dan logisch dat men om de pikkosten te drukken, de reistijd en -afstand tot een minimum beperkt. 5
3.3 Besluit In dit deel toonden we aan dat excellent logistiek beheer cruciaal is om 24u per dag, 7 dagen op 7 aan de enorme verscheidenheid in de vraag te kunnen voldoen. De supply chain moet daarnaast niet enkel responsief zijn maar ook kostenefficiënt. Aangezien magazijnbeheer een groot deel van de logistieke kosten voor zijn rekening neemt (ELA/AT Kearny, 2004 in: De Koster et al., 2007) is het aan te raden de processen in het magazijn zo efficiënt mogelijk uit te voeren, zonder aan kwaliteit in te boeten. Een belangrijke kostenpost is orderpikken (figuur 3.1), dat of zeer arbeids- of zeer kapitaalintensief (AS/RS) is. In een picker-to-part systeem spendeert de pikker gemiddeld 50% van zijn tijd aan de verplaatsing van en naar de opslaglocaties (figuur 3.2). Het herleiden van de reistijd voor de pikker tot het absolute minimum kan dus een grote impact hebben op de arbeidskosten en verdient daarom onze aandacht. Daarenboven creëert deze reistijd geen waarde voor de klant en moet zij, redenerend vanuit de lean manufacturing principes, sowieso tot een minimum worden beperkt.
receiving
shipping 17%
andere setup 5% 10%
storage 16% reistijd 50%
14% picking 53%
Figuur 3.1 De kosten van magazijnbeheer opgesplitst naar activiteit. Op basis van Tompkins (2003) en Aminoff et al. (2002)
piktijd 15%
zoektijd 20%
Figuur 3.2 Opsplitsing van de tijd besteed aan orderpikken. Op basis van Tompkins (2003).
6
4. Beslissingen in magazijnbeheer In een studie over het ontwerp van magazijnen merken Rouwenhorst et al. (2000) op dat de efficiëntie van een supply chain afhankelijk is van de efficiëntie van de verschillende punten in de keten (bijvoorbeeld de efficiëntie van magazijnen). In de studie gaat men er van uit dat de exploitatiekosten van het magazijn in hoge mate worden vastgelegd tijdens de ontwerpfase. Met andere woorden: beslissingen genomen tijdens deze fase determineren de werkingskosten in de toekomst. De auteurs ontwerpen vervolgens een leidraad voor toekomstige wetenschappers en managers in de vorm van een hiërarchische structuur voor het nemen van beslissingen in de ontwerpfase. De indeling in een strategisch, tactisch en operationeel niveau weerspiegelt de tijdshorizon van de beslissingen. Daarenboven leggen beslissingen op een hoger niveau beperkingen op aan deze op een lager niveau. Aangezien bij het ontwerp van een magazijn vele beslissingen onderling afhankelijk zijn, worden in de ideale ontwerpmethode gerelateerde problemen op hetzelfde niveau samengenomen in clusters. De auteurs definiëren beslissingen als coherent (of gerelateerd) wanneer een sequentiële optimalisatie niet kan garanderen dat een globale optimale oplossing wordt gevonden. Idealiter moet men oplossingen zoeken door de verschillende gerelateerde deelproblemen tegelijkertijd te optimaliseren. Op die manier streeft men namelijk een globaal optimum na. Naast de drie niveaus, bekijken Rouwenhorst et al. (2000) de beslissingen in het magazijn vanuit drie verschillende invalshoeken: processen, middelen en organisatie. Zo is het routeringvraagstuk bijvoorbeeld een organisatorische beslissing op operationeel niveau behorende bij het orderpikproces. De beslissing over het aantal laad- en losplaatsen voor vrachtwagens is dan weer een tactische beslissing omtrent de middelen behorende bij de processen ‘receiving’ en ‘shipping’. In wat volgt beschrijven we kort elk van de 3 niveaus en worden beslissingen aangeduid die horen bij het orderpikproces. 4.1 Strategisch Strategische beslissingen hebben een impact op lange termijn en impliceren meestal grote investeringen. Twee categorieën kunnen onderscheiden worden. In de eerste plaats moet men het procesverloop bepalen: welke activiteiten en processen zullen in het magazijn uitgevoerd worden? De beslissing of men al dan niet batches zal vormen tijdens het orderpikken is een voorbeeld van een strategisch organisatorische beslissing omdat dit meteen ook de beslissing omtrent het sorteersysteem beïnvloedt. Ten tweede moet men beslissen welk type magazijn men wil ontwerpen. Hierbij wordt zowel rekening gehouden met technische als economische overwegingen.
7
4.2 Tactisch Tactische beslissingen worden genomen binnen de beperkingen opgelegd door het strategisch niveau. Deze beslissingen leggen op middellange termijn de organisatie van het magazijn en de middelen vast en hebben een significante impact op de kost en efficiëntie van de operaties. Het nemen van tactische beslissingen vergt dus een zeker engagement. Een typische beslissing in deze categorie is de lay-out van het magazijn (Waters, 2003). Verder zijn ook de grootte en de hoeveelheid van de middelen belangrijke tactische beslissingen. Op dit niveau situeert zich ook de beslissing omtrent de batchgrootte. Deze beslissing is volgens Rouwenhorst et al. (2000) geclusterd met het dimensioneren van de pikzones, het aanvul- en opslagbeleid. 4.3 Operationeel Operationele beslissingen zijn korte termijn beslissingen. De voor ons relevante organisatorische beslissingen zijn het vormen van batches, het routeren van de pikker en het toewijzen van de pikkers aan pikopdrachten. De auteurs geven geen voorbeelden van clusters (van beslissingen behorend tot verschillende processen) op dit niveau omdat ze menen dat beslissingen hier vaker onafhankelijk van elkaar kunnen worden genomen, de relaties tussen de beslissingen zijn namelijk al in acht genomen op het strategische en tactische niveau. Dit betekent echter niet dat beslissingen behorende tot hetzelfde proces niet geïntegreerd moeten worden De indeling van beslissingen inzake magazijnbeheer van Gu et al. (2007) sluit nauw aan bij deze van Rouwenhorst et al. (2000). Gu et al. (2007) onderscheiden op het hoogste niveau magazijnontwerp en magazijnprocessen. De laatste categorie is op zijn beurt onderverdeeld in vier deelprocessen: ontvangen, opslag, orderpikken en verzenden. De operationele beslissingen gerelateerd aan het orderpikken zijn batchen (toewijzing van de orders aan de batches en bepalen van de batchgrootte), routeren (bepalen van de exacte route en van de volgorde van de rondes) en sorteren (toewijzen van items/orders aan sorteerlanen). Ook in Van Landeghem (2007) vinden we sorteren, routeren en batchen terug bij de operationele beslissingen gerelateerd aan het orderpikken. In deze masterproef zal getracht worden de verschillende operationele deelproblemen gerelateerd aan het orderpikken zoveel mogelijk te integreren met als doel een globaal optimum te bereiken.
8
4.4 Besluit In dit deel werden beslissingen in magazijnen onderverdeeld in 3 niveaus (strategisch, tactisch en operationeel) op basis van de relevante tijdshorizon en de grootte van de investeringen. Beslissingen op een hoger niveau leggen de krijtlijnen voor het lager niveau vast. Ook beslissingen op hetzelfde niveau mogen niet onafhankelijk van elkaar worden genomen. Integratie van de verschillende deelproblemen bij het optimaliseren is volgens Rouwenhorst et al. (2000) aangewezen om een globaal optimum te bekomen. In deze masterproef ligt de focus op het operationeel niveau zoals gedefinieerd door Gu et al. (2007) en meerbepaald de integratie van de batching- en routeringbeslissing bij het orderpikken. In mindere mate zal ook het sorteerproces bestudeerd worden.
9
5. Orderpikken: een combinatorisch probleem
5.1 Inleiding Het opstellen van een route voor de pikker is een toepassing van het travelling salesman problem (TSP) of handelsreizigersprobleem. Het integreren van het routeringprobleem en het batchingprobleem lijkt dan weer sterk op het vehicle routing problem (VRP). Daarnaast zijn er ook gelijkenissen te vinden met het bin-packing problem (BPP). Deze drie combinatorische optimalisatievraagstukken, enkele varianten en hun link met het routering- en batchingprobleem worden hieronder toegelicht. 5.2 TSP en Steiner TSP Het TSP is reeds veelvuldig bestudeerd in operations research. Een handelsreiziger moet de kortste rondreis bepalen tussen de verschillende steden die hij moet bezoeken. Een probleem met N steden, telt (N-1)! mogelijke oplossingen. Indien het probleem een symmetrisch handelsreizigersprobleem betreft (de afstand van locatie i tot locatie j is dezelfde als deze van locatie j naar locatie i) dan is het aantal verschillende rondreizen ½(n-1)!. We kunnen k! benaderen door de formule van Stirling: k
𝑘! ≈ 2πk ( )k , voor k voldoende groot. e
De term
k (e )k
verklaart de explosieve stijging van het aantal mogelijke combinaties (Tijms, 2008).
Door het enorme aantal mogelijke combinaties is dit probleem dus moeilijk optimaal op te lossen in beperkte tijd voor een realistische situatie met een groot aantal locaties. De analogie met het routeringprobleem van de orderpikker is vanzelfsprekend: we moeten de kortste route bepalen voor de pikker die een aantal opslaglocaties moet bezoeken en waarbij hij zal starten en eindigen aan een depot (Gelders en Heeremans, 1994). Men kan het routeringprobleem bij orderpikken in een rechthoekig magazijn bestaande uit meerdere evenwijdige gangen omvormen van een klassiek TSP naar een Steiner TSP. Het magazijn kan schematisch worden voorgesteld door een netwerk van knooppunten (figuur 5.1). De verzameling S die de kruispunten van de langsgangen met de dwarsgangen bevat bestaat uit p elementen, met p = aantal langsgangen × aantal dwarsgangen. Bij het verzamelen van de orders hoeven de orderpikkers deze Steiner knooppunten (witte punten op de figuur) niet te bezoeken maar mogen zij dat wel, en zelfs meer dan één maal. De zwarte punten moeten daarentegen minstens één maal bezocht worden, zij stellen de locaties voor waar zich de gevraagde items bevinden. De verzameling R = 1, 2, 3, … , n + {0}, waarbij n het aantal op te halen items is en het element 0 de depot voorstelt. Men kan nu het magazijn voorstellen door een graaf G = (N,A) waarbij 10
N = S ∪ R en A de verzameling pijlen voorstelt. Een TSP waarbij sommige punten niet moeten bezocht worden en andere punten zeker één maal bezocht moeten worden noemt men een Steiner TSP (Theys et al., 2007 en De Koster, Le-Duc en Roodbergen, 2007).
Figuur 5.1 Schematische voorstelling van het magazijn als een netwerk van knooppunten. (De Koster et al., 2007) 5.3 BPP In het klassieke BPP moet een voertuig een aantal objecten van verschillende inhoud ophalen op diverse plaatsen. Het voertuig dat slechts een beperkte capaciteit heeft, vertrekt telkens aan de depot en komt na de rit terug aan op datzelfde depot. Het is de bedoeling het aantal ritten van het voertuig te minimaliseren of de werklast tussen de gevormde rondritten/voertuigen te balanceren. In de context van orderpikken is de capaciteit van het voertuig vergelijkbaar met de capaciteit van de pikker en de inhoud van een object is vergelijkbaar met het volume (of gewicht, aantal items,…) van een order. De inhoud van een order is op zijn beurt afhankelijk van het volume of gewicht van de items behorende tot dat order. Toegepast op orderpikken zal men dus de orders zo toewijzen aan de batches opdat het aantal batches geminimaliseerd of de werklast gebalanceerd wordt en de capaciteit van de pikker niet wordt overschreden (Won en Olafsson, 2005). 5.4 VRP In het klassieke TSP zal één handelsreiziger N steden bezoeken. Wanneer er nu meer dan één handelsreiziger werkzaam is in dit gebied kunnen we het TSP uitbreiden. Stel dat het bedrijf over m handelsreizigers beschikt en dat elke locatie door juist één handelsreiziger moet bezocht worden, dan duiden we dit probleem aan als een m-TSP. Elke handelsreiziger zal zowel starten als eindigen aan de centrale locatie. In dit nieuwe probleem moeten enerzijds de steden toegewezen worden aan de handelsreizigers en anderzijds moet voor elke handelsreiziger een route bepaald worden. Een VRP is nu een m-TSP waarbij een locatie een bepaalde vraag heeft en aan elke handelsreiziger of voertuig slechts een beperkte vraag kan worden toegewezen omwille van capaciteitsrestricties. 11
Het optimalisatiecriterium in een VRP is het minimaliseren van de totale afgelegde afstand of de daaraan gekoppelde totale reistijd. Daarnaast neemt men ook vaak het minimaliseren van het aantal voertuigen en dus ook het minimaliseren van het aantal routes (indien elk voertuig slechts één route aflegt) als criterium, net zoals in het BPP (Bräysy, 2001). Men kan in het VRP ook eisen dat de reistijd per voertuig een gegeven waarde niet mag overschrijden (Tijms, 2008). Dit is belangrijk indien de producten moeten gehaald of geleverd worden binnen een bepaald tijdsvenster. Men spreekt in de literatuur van het ‘VRP with Time Windows’ (VRPTW). De tijdsvensters kunnen hard of zacht zijn. In de harde variant mag de handelsreiziger of het voertuig zijn activiteit op de plaats van de bestemming helemaal niet uitvoeren voor of na een bepaald tijdstip. In de zachte variant daarentegen mag men dit wel, maar er zal een bepaalde ‘penalty kost’ aangerekend worden (Bräysy, 2001). De verschillende routes van de voertuigen zijn analoog aan de verschillende routes die de orderpikker(s) moet(en) afleggen. Elke gevormde batch zal overeenkomen met één route. De route wordt bepaald door de inhoud (de gevraagde producten of items) van de orders aanwezig in een batch. Elk item of product heeft namelijk zijn specifieke opslaglocatie. Soms kan het echter gebeuren dat hetzelfde type item zich op verschillende opslaglocaties bevindt. Het spreekt voor zich dat in dit laatste geval het probleem nog complexer wordt. We kunnen zowel de totale afgelegde afstand minimaliseren over alle batches heen (m-TSP criterium) en/of proberen het aantal gevormde batches te minimaliseren (BPP criterium) en daarenboven zou men kunnen eisen dat het pikken van de individuele batches moet gebeuren binnen een bepaalde tijd of tussen welbepaalde tijdstippen (tijdsvenster criterium). Gu et al. (2007) wijzen op de gelijkenis met het pick-up and delivery VRP of het dial-a-ride probleem. De combinatie van het VRP en het pickup and delivery problem wordt het general vehicle routing problem (GVRP) genoemd. Goel en Gruhn (2008) beschrijven dit probleem. Hun ‘transportation requests’ bevatten een aantal te bezoeken locaties, dit komt overeen met het concept van orders en opslaglocaties. Transportation requests worden toegewezen aan voertuigen en bijgevolg gebatched. Het grote verschil met het pikprobleem en de probleemstelling van Goel en Gruhn (2008) is dat bij de laatste de volgorde van de opslaglocaties vastligt. Voertuig i zal dus niet eerst locatie j in order 1 mogen bezoeken en daarna locatie j-1 van hetzelfde order. Wel mag voertuig i eerst locatie j van order 1, vervolgens een locatie van order 2 en daarna locatie j+1 van order 2 bezoeken. Dus elke mogelijke volgorde van locaties is mogelijk zolang maar voldaan is aan de ‘precedence constraints’ binnen een order en aan de ‘grouping constraint’. De grouping constraint betekent dat een order in zijn geheel moet worden opgehaald binnen dezelfde route en dus niet mag worden opgesplitst over
12
verschillende rondes. In tegenstelling tot de precendence constraints vindt men de grouping constraint bijna altijd terug bij de omschrijving van het pikprobleem. Echter, bij het routeren van orderpikkers kunnen er in bepaalde gevallen ook precendence constraints voorkomen. Een voorbeeld hiervan is dat eerst de zwaarste of grootste items moeten gepikt worden omdat stapelen anders niet lukt. In de wetenschappelijke literatuur inzake routering en batching worden deze beperkingen zelden in het model opgenomen. Bozer en Kile (2007) zien het pikprobleem als een geclusterd TSP met speciale eigenschappen door de ladderstructuur. Indien orders niet gesplitst mogen worden is er namelijk, naast de beperking van de capaciteit, ook nog eens de beperking van de integriteit (‘grouping constraint’), i.e. al de verschillende items van een order moeten aan dezelfde batch toegewezen zijn en dus in dezelfde route worden gepikt. Zij denken dat het praktisch niet haalbaar is het batchingprobleem op te lossen via de traditionele methoden ontwikkeld voor het TSP of VRP. Goel en Gruhn (2008) wijzen daarbij op het ontbreken van een betrouwbaar ‘closeness concept’ voor het multiple pick-up probleem, dit in tegenstelling tot het klassieke VRP waar het makkelijker is om een de nabijheid van de verschillende ‘orders’ ten opzichte van elkaar te bepalen. Een order bestaat in het klassieke VRP namelijk slechts uit één locatie. Zoals aangehaald door Bozer en Kile (2007) en Goel en Gruhn (2008) zal een heuristiek slechts goed kunnen batchen wanneer zij de afstand of nabijheid tussen verschillende orders correct kan inschatten. De grote moeilijkheid is dat een order bestaat uit meerdere items, die zich verspreid over het magazijn kunnen bevinden, en dat deze items in dezelfde ronde moeten gepikt worden. Men kan dus niet eenvoudigweg de locatie van order i vergelijken met de locatie van order j, want er bestaat geen eenduidig antwoord op de vraag wat de locatie van een order is. Verschillende methodes werden reeds ontwikkeld om de afstand tussen orders in te schatten. De literatuur inzake batchingalgoritmen wordt in hoofdstuk 6.2 besproken. 5.5 Optimaliseren van reistijd of reisafstand? De verwachte tijd nodig voor het pikken van items kan volgens Frazelle (1989) (In: Caron, Marchet en Perego, 1998) opgesplitst worden in reistijd, procestijd en administratieve tijd. Ten eerste is er de tijd nodig om zich te verplaatsen van de ene locatie naar de andere. Dit is de reistijd. De procestijd omvat het zoeken naar de exacte opslaglocatie, het verwijderen van de items uit de opslaglocatie en het documenteren of bevestigen van de pikactiviteit. De administratieve tijd (in het begin of op het einde van de route) omvat bijvoorbeeld het ophalen van het gepaste materieel of de piklijst.
13
De meeste publicaties bestuderen enkel de variaties in reistijd of reisafstand en beschouwen de procestijd en administratieve tijd als gegeven of constant. De reistijd kan men via een lineaire transformatie berekenen uit de afgelegd reisafstand, indien men een constante snelheid van de pikker of van het voertuig verondersteld. Men verwaarloost dan ook de tijd om te versnellen en af te remmen. In dat geval doet het er dus eigenlijk niet echt toe welk criterium (reistijd of reisafstand) men gebruikt. In het grootste deel van de experimenten vergelijkt men de afstanden bekomen door toepassing van verschillende algoritmen. In andere onderzoeken is de reistijd als resultaat gegeven maar is die simpelweg een lineaire transformatie van de reisafstand. In onze eigen experimenten (deel 7) zal altijd de reisafstand berekend worden. Experiment 2 zal daarnaast ook rekening houden met de administratieve tijd in de vorm van een vaste kost per gevormde batch. 5.6 Heuristiek of exact algoritme? Om een combinatorisch probleem op te lossen kan men genoegen nemen met de toepassing van een heuristiek. Deze benadert de optimale oplossing en kan bij toeval ook de optimale oplossing vinden. We geven enkele redenen waarom heuristieken in praktijk vaker gebruikt worden in plaats van exacte algoritmes. In het algemeen kunnen we zeggen dat managers een afweging moeten maken tussen de besparingen in reistijd door implementatie van het optimaal algoritme en het gebruiksgemak van een heuristiek (Petersen, 1997). Orderpikken is een operationeel planningprobleem, wat inhoudt dat men frequent en snel oplossingen moet kunnen genereren. Een heuristiek zal minder rekentijd vergen dan het vinden van de optimale oplossing (Won en Olafsson, 2005). Daarenboven is de rekentijd bij een heuristiek voorspelbaar terwijl de rekentijd in het geval van een exact algoritme meestal niet te voorspellen valt (Roodbergen en De Koster, 2001a). Men moet er ook rekening mee houden dat de optimale algoritmes niet door iedereen bekend zijn. Daarenboven verschilt de lay-out van het magazijn of de samenstelling van de orderlijst in realiteit vaak van het eenvoudige theoretische model (1 of 2 blokken en parallelle gangen / een beperkte orderlijst) waardoor de efficiënte exacte algoritmes niet meer toepasbaar zijn (De Koster et al., 2007, De Koster en Van der Poort, 1998). Ook moet het praktisch mogelijk zijn het algoritme te implementeren in de warehouse management software. Omdat er extra kosten aan het implementeren van een optimaal algoritme verbonden zijn en de winst a priori niet bekend is, neemt men vaak een terughoudende houding aan en blijft men bij de oude methode (De Koster en Van der Poort, 1998). Dit laatste argument geldt natuurlijk ook voor de implementatie van nieuw heuristische oplossingmethoden.
14
Het optimaal algoritme heeft daarenboven het nadeel complex en niet transparant te zijn wat aversie tegen het gebruik er van met zich meebrengt (De Koster en Van der Poort, 1998). Een zeer belangrijk minpunt is dus dat in het geval van het routeringvraagstuk, optimale routes in praktijk niet logisch kunnen lijken voor de pikker waardoor de kans bestaat dat hij zal afwijken van de opgestelde routing, wat op zijn beurt zal leiden tot inefficiënties (Gademann en Van de Velde, 2005). Routes gevormd via dezelfde heuristiek lijken meestal op elkaar, wat het voor de pikker eenvoudig en herkenbaar maakt (Petersen, 1997). Dit argument is niet echt van toepassing op batchingalgoritmen maar des te meer op routeringalgoritmen. Verder houdt het exacte algoritme geen rekening met congestie in de gangen. Een aangepaste Sshape routeringheuristiek zal bijvoorbeeld een zekere mate van congestie kunnen vermijden door eenrichtingsverkeer op te leggen (De Koster et al., 2007). Ten slotte verkiezen sommige warehouse managers de pikefficiëntie te verhogen door orders goed te batchen in plaats van de routeringmethoden aan te pakken, er worden geen middelen toegewezen aan de implementatie van een exact routeringalgoritme (De Koster en Van der Poort, 1998). Deze laatste redenering lijkt ons zeker fout, de routeringheuristiek en het batchingalgoritme kunnen namelijk niet onafhankelijk van elkaar gezien worden. Om tot een globaal optimum te komen moeten beiden in beschouwing worden genomen (zie 4.4). 5.7 Besluit In dit deel werd de combinatie van het batching- en routeringprobleem beschreven als een variant op het klassieke VRP. In principe kan men dus proberen om het pikprobleem op te lossen via een oplossingsmethode ontwikkeld voor het VRP. Dit is echter niet vanzelfsprekend door de aanwezigheid van een ‘grouping constraint’, deze restrictie houdt in dat orders niet mogen gespreid worden over meerdere batches. Het toevoegen van een order aan een batch impliceert namelijk het toevoegen van elk item van dat order aan die batch, waarbij elk item zich op een andere locatie kan bevinden. Een grote uitdaging is dus het identificeren van een gepaste ‘closeness measure’ om de afstand of nabijheid tussen orders onderling te meten. Omdat zowel het routeringprobleem als het batchingprobleem afzonderlijk NP-hard zijn zal men in praktijk vaak gebruik maken van heuristieken. Deze hebben enerzijds het nadeel een langere route te genereren maar zijn anderzijds makkelijker aan te leren aan de orderpikkers.
15
6. Batching- , routering- en sorteringstrategieën in de wetenschappelijke literatuur Vele onderzoekers hebben reeds algoritmen voorgesteld om het batching- en routeringprobleem op te lossen. In dit deel worden de bestaande exacte algoritmes en heuristieken besproken. Daarnaast wordt ook de invloed van deze batchingalgoritmes op het sorteerproces onderzocht. In bijlage 1 vindt de lezer de begrippen terug die zullen gebruikt worden met betrekking tot de lay-out van het magazijn. 6.1 Routering
6.1.1
Inleiding
Het doel van de routeringmethoden is het bepalen van de optimale pikvolgorde en het vastleggen van de wijze waarop van de ene naar de andere opslaglocatie wordt gereisd: de routering moet de order pikker zo efficiënt mogelijk door het magazijn gidsen. Als input voor het bepalen van een efficiënte route zijn een verzameling van gevraagde items en hun respectievelijke opslaglocaties gegeven. Daarnaast speelt ook de door het bedrijf gekozen oplossingsmethode een rol: zal men gebruik maken van routeringheuristieken of verkiest men altijd een optimale oplossing. Verder kunnen ook praktische restricties de route beïnvloeden: zware items die niet bovenop lichte items kunnen gestapeld worden, gevaar op congestie in de gangen,… . Bij het vergelijken van de verschillende routeringheuristieken veronderstellen de meeste auteurs dat de batches, dit zijn verzamelingen van items of orders die in dezelfde route moeten worden gepikt, vooraf zijn gevormd. Nadien zal men dan voor iedere batch afzonderlijk de route bepalen. Dit is dus een sequentieel beslissingsproces. In de literatuur zijn reeds veel oplossingenmethoden voorgesteld voor het routeringvraagstuk. In dit hoofdstuk geven we een overzicht van deze oplossingsmethoden. Vooraf moet opgemerkt worden dat een uitgebreide studie van de routeringmethoden slechts zinvol is indien men minstens 3 verschillende opslaglocaties moet bezoeken. Het geval waarbij slechts één opslaglocatie moet bezocht worden is namelijk makkelijk op te lossen want de kortste route is in dat geval de kortste route van de depot naar de opslaglocatie en terug. Ook indien twee opslaglocaties worden bezocht is de oplossingmethode triviaal. Men bepaalt dan de kortste route van de depot naar de eerste opslaglocatie, vervolgens loopt men via de kortste weg naar de tweede opslaglocatie, om in laatste instantie via de kortste weg terug te keren naar de depot. Welke opslaglocatie eerst wordt bezocht doet er niet toe (Theys en Herroelen, 2005). De methode voor het bepalen van dit kortste pad is terug te vinden in bijlage 2.
16
6.1.2
Exacte algoritmes
In deel 5 werd het routeringvraagstuk beschreven in termen van een TSP en Steiner TSP. Ratliff en Rosenthal (1983) beschrijven een algoritme gebaseerd op dynamisch programmeren dat dit Steiner TSP in een redelijke tijd kan oplossen voor een magazijn bestaande uit één blok en een centraal gelegen depot. De rekentijd is lineair in functie van het aantal langsgangen en te bezoeken locaties. De Koster en Van Der Poort (1998) breiden het optimaal algoritme van Ratliff en Rosenthal (1983) uit naar een magazijn met een gedecentraliseerde depot. Dit betekent dat de orderpikker zijn items mag afzetten aan de kop van iedere langsgang. Het voordeel van gedecentraliseerde depositie is dat bepaalde duurdere voertuigen continu kunnen gebruikt worden in de langsgangen. Sneller en eventueel goedkoper materieel (zoals een transportband) transporteert daarna de items naar de plaats van bestemming. In het onderzoek vergelijkt men de optimale methode met de S-shape heuristiek, en dit voor drie soorten magazijnen. Ze vinden een reductie van de reistijd van 7% tot 34% indien men de optimale methode gebruikt. De reductie hangt vooral af van de lay-out en de werking van het magazijn. Roodbergen en De Koster (2001b) ontwerpen een exact algoritme, gebaseerd op dynamisch programmeren, voor een magazijn met drie dwarsgangen. Eén vooraan, achteraan en tussenin. Deze laatste dwarsgang noemt men de middengang, ook al hoeft deze niet altijd exact in het midden van het magazijn ingeplant te zijn. In praktische toepassingen duurt het slechts een fractie van een seconde om via dit algoritme de optimale oplossing te berekenen. In de studie vergelijken de auteurs de reistijden in een magazijn met en zonder middengang. Verder laten ze de grootte van het magazijn en de piklijst (lijst met te pikken items) variëren. Belangrijk is dat ze de middengang laten samenvallen met het geografische midden van het magazijn. Zij argumenteren dat het in bepaalde situaties beter kan zijn om de middengang meer naar het einde toe van het magazijn in te planten maar dat dit om flexibiliteitredenen beter niet wordt gedaan. Wanneer bijvoorbeeld de locatie van de depot wijzigt, dan kan het voordeel van de naar achter geplaatste middengang omslaan in een nadeel. De optimale locatie van de middengang zal daarenboven ook vaak in de buurt van het exacte midden liggen. Zij besluiten dat vooral in grote magazijnen de toevoeging van een middengang relevante winst in reistijd kan opleveren. 6.1.3
Heuristieken
Omdat efficiënte exacte algoritmes niet voorhanden zijn in complexere magazijnen of omwille van praktische redenen (zie 5.6) hebben meerdere onderzoekers heuristieken ontwikkeld om het routeringprobleem specifiek voor het orderpikken op te lossen. De vroegste literatuur beschrijft 17
heuristieken voor magazijnen bestaande uit één blok, nadien breidde men de bestaande heuristieken uit en creëerde men nieuwe heuristieken voor magazijnen bestaande uit meerdere blokken. 6.1.3.1 Heuristieken in magazijnen bestaande uit één blok In Hall (1993) wordt de largest gap heuristiek geïntroduceerd. De ‘largest gap’ komt overeen met dat gedeelte van de subgang dat niet zal doorlopen worden. De pikker zal tot aan de largest gap lopen langs ‘onder’ en dan terugkeren om vervolgens langs ‘boven’ de rest van de producten in de gang te pikken. Voor het bepalen van de largest gap moet men de afstanden berekenen tussen de aanliggende dwarsgangen (de ‘onderste’ en ‘bovenste’ dwarsgang) en de dichtstbijzijnde opslaglocaties (die moeten bezocht worden) in de subgang. Vervolgens berekent men ook de afstand tussen elke twee opeenvolgende opslaglocaties die moeten bezocht worden in de subgang. De largest gap komt dan overeen met de afstand die het grootst was. Na een vergelijkende studie van de midpoint, largest gap en traversal (= S-shape) heuristiek besluiten zij dat de traversal heuristiek beter presteert als de pikdensiteit (gemiddeld aantal te pikken items per langsgang) groter is dan 3,9. Wanneer de pikdensiteit laag is zal de largest gap strategie beter presteren. Daarnaast stellen zij ook vast dat de largest gap heuristiek altijd even goed of beter scoort dan midpoint. Het enige voordeel van deze laatste heuristiek is dus dat hij makkelijk te implementeren is. Het optimaal algoritme blijkt een combinatie van de traversal en largest gap heuristiek. Verder geeft Hall (1993) een wiskundig model om de verwachte reistijd te berekenen. Ten slotte onderzoeken zij de invloed van de lay-out van het magazijn op de verwachte reisafstand, waarbij de magazijnoppervlakte gelijk blijft. Een breder magazijn resulteerde in kortere routes dan een magazijn waar breedte en lengte ongeveer gelijk zijn (Hall, 1993 in: Petersen, 1997; Caron, Marchet en Perego, 2000; Ho en Tseng , 2006). Petersen (1997) onderzoekt vervolgens de prestatie van 5 heuristieken: S-shape, return, midpoint, largest gap, composite (geïntroduceerd door Petersen (1995) en de optimale oplossing ( berekend via het algoritme van Ratliff en Rosenthal (1983)) in een magazijn met twee dwarsgangen en een random storage omgeving. De onderzoekers variëren daarnaast de grootte van de piklijst, de dimensie van het magazijn en de locatie van de depot. Bij het wijzigen van de dimensie verandert men de verhouding van de lengte ten opzichte van de breedte van het magazijn. Belangrijk is dat het aantal opslaglocaties constant wordt gehouden (in tegenstelling tot het experiment van Hall (1993)). Via een experimentele opzet worden zowel de prestaties van de verschillende routeringstrategieën als de invloed van de dimensies van het magazijn en de locatie van de depot op de reisafstand onderzocht. Men besluit dat de beste heuristiek 5% slechter presteert dan het optimale algoritme. 18
De beste heuristieken zijn composite en de largest gap. De return methode presteert dan weer het slechtst. Belangrijk is ook dat alle heuristieken beter scoren in een langwerpig magazijn. Hwang, Oh en Lee (2004) tonen dit ook aan voor andere routeringstrategieën. De bevindingen zijn duidelijk in tegenspraak met Hall (1993) die stelde dat een breder magazijn betere resultaten oplevert. Dit verschil komt omdat in het experiment van Hall (1993) in een breed magazijn minder opslaglocaties zijn dan in een diep, de magazijnoppervlakte wordt namelijk constant gehouden en niet het aantal opslaglocaties. Daarenboven resulteerde de centrale depot (i.p.v. in de hoek) in kortere afstanden ten voordele van meerdere langsgangen. Daarnaast speelt ook het (on)even zijn van het aantal langsgangen een rol. Bij een oneven aantal langsgangen zijn de S-shape en de composite heuristiek in het nadeel: er is namelijk veel kans dat men bij deze heuristieken op het einde van de route nabij de achterste dwarsgang van het magazijn belandt, men moet dan nog eens vanaf de laatste opslaglocatie door de laatste langsgang terugkeren om via de voorste dwarsgang de depot te bereiken. De S-shape heuristiek wordt dan weer positief beïnvloed door een grote piklijst. Uit het onderzoek blijkt dat de composite heuristiek het meest aangewezen is voor een piklijst van 25-45 items terwijl de largest gap heuristiek aan te raden is voor kleinere aantallen (5-25). Dit komt dan wel weer overeen met Hall (1993). Ten slotte speelt de locatie van de depot een significante, maar niet echte relevante rol. De routes waarbij de depot in het midden van de eerste dwarsgang is gelokaliseerd zijn gemiddeld 0,9% korter dan deze met een depot in de hoek. Dit verschil wordt groter bij een breder magazijn en kleiner bij grotere piklijst. Makris en Giakoumakis (2003) stellen een k-interchange of k-verwissel heuristiek voor als oplossing voor
het
routeringvraagstuk
in
een
magazijn
met
2
dwarsgangen.
Dit
is
een
routeverbeteringsmethode gebaseerd op de k-opt methodologie van Lin en Kernighan (1973). In de eerste stap wordt een voorlopige route samengesteld. In het voor ons onderzoek relevante magazijn bepalen de auteurs de initiële volgorde via een eenvoudige enumeratiemethode. Men verhoogt in elke stap de y coördinaat en het gangnummer, beginnend bij de eerste gang links. Nadien past men de routeverbeteringsheuristiek toe: in elke stap verwisselt men het ide punt met kde punt, zodat vier nieuwe verbindingen verschijnen, terwijl er vier oude verdwijnen. Wanneer de wijziging leidt tot een kortere route, dan behoudt men deze oplossing. Voorwaarden zijn dat: i − k > 1, i en k ad random worden gekozen en n > i, k > 1. De eigenlijke routering gebeurt via het kortste pad principe: men bepaalt het kortste pad tussen twee opeenvolgende te bezoeken locaties, zoals gegeven in de pikvolgorde, en reist telkens via deze weg. Het bepalen van dit kortste pad is vrij eenvoudig (zie Bijlage 2). Als men tot een goede oplossing wil komen moet men de verbeteringsprocedure een aantal maal herhalen. De auteurs geven een formule voor het minimale aantal herhalingen m nodig om slechts een bepaald percentage van het optimale resultaat af te wijken. De rekentijd in elke stap 19
is onafhankelijk van het aantal items n, m is daarentegen wel afhankelijk van n. De auteurs stellen vast dat in 7 van de 11 gevallen de k-interchange heuristiek beter presteert dan de S-shape. Ook is er een kleinere spreiding rond het optimum in het geval van een k-interchange heuristiek (4,47% 19,2%) ten opzichte van S-shape (7,3% - 34,2%). De auteurs besluiten dat de toepassing van de kinterchange methode in praktijk minstens even goed is als de S-shape. Zij vermelden ook drie voordelen van de heuristiek. Ten eerste kan deze toegepast worden onafhankelijk van de lay-out, de geometrische vorm en de functie van het magazijn. Ten tweede is de procedure redelijk simpel en ten derde moet men weinig assumpties maken. In Hwang, Oh en Lee (2004) worden de prestaties van de return, traversal en midpoint heuristiek onderzocht onder een cube-per-order (COI) gebaseerd opslagbeleid en een depot centraal vooraan. De COI is de verhouding van het ruimtegebruik van een item ten opzichte van de orderfrequentie. Orders met een lage COI worden zo dicht mogelijk bij de depot of in makkelijk bereikbare opslaglocaties geplaatst. Op basis van de COI kan men vervolgens een ABC curve opstellen, deze wordt bekomen door de items te rangschikken volgens oplopende COI. De ABC curve F(x) staat dan voor dat gemiddeld percentage van de piklijst dat een deel x van de capaciteit in het magazijn voor zijn rekening neemt. Analytisch ziet dit er zo uit: F x =
1+b x b+x
met F x ≥ 0, 0 ≤ x ≤ 1, b ≥ 0, b + x ≠ 0.
B is de scheefheidsfactor, hoe groter b hoe minder scheef de verdeling (Caron, Marchet en Perego, 2000). Hwang, Oh en Lee (2004) variëren in hun studie de scheefheid van de ABC curve, de dimensie van het magazijn en de grootte van de piklijst. Men kan het COI gebaseerd opslagbeleid op verschillende manieren implementeren, waarbij de beste manier afhankelijk is van de gekozen routeringstrategie. De auteurs combineren traversal met within-aisle, return met across-aisle en midpoint met perimeter. Bij within-aisle worden de langsgangen het dichtst bij de depot eerst opgevuld met items met een lage COI. Wanneer minder langsgangen moeten bezocht worden zal een traversal strategie daar namelijk van profiteren. Across-aisle zal dan weer de lage COI items eerst toewijzen aan de dichtstbijzijnde opslaglocaties, onafhankelijk van de langsgang waarin zij zich bevinden. Het voordeel voor de return strategie is duidelijk: de order pikker zal minder afstand in een individuele langsgang moeten afleggen. De perimeter toewijzingsmethode ten slotte zal de uiteinden van de langsgangen eerst opvullen, ook hier zal de order pikker minder afstand in de individuele langsgangen moeten afleggen. Na simulatie trekken de auteurs volgende besluiten: voor bijna elke piklijstgrootte, scoort midpoint (met perimeter) het best, behalve wanneer de piklijst zeer klein of zeer groot is. In het geval van een kleine piklijst scoort return (met within-aisle) het best. Voor een grote piklijst is traversal dan weer beter. Hoe schever de ABC curve, hoe korter de 20
reisafstanden, dit komt doordat veelgevraagde producten zich relatief dichter bij de depot zullen bevinden of beter in de route zullen passen en op die manier via de vermelde mechanismen de reisafstanden zullen verminderen. 6.1.3.2 Heuristieken in magazijnen bestaande uit meerdere blokken Het magazijn in Caron, Marchet en Perego (1998) bestaat uit twee blokken met een even aantal langsgangen per blok. De depot ligt opvallend genoeg ter hoogte van de middengang uiterst rechts. De auteurs vermelden dat een lay-out met de opslaggangen loodrecht op de wand waar de depot zich bevindt, altijd slechtere resultaten oplevert. In Caron, Marchet en Perego (2000) argumenteren zij dat de hierboven vermelde lay-out beter is dan een magazijn bestaande uit één blok (dit wordt onder meer bevestigd door Roodbergen en De Koster 2001a), zij geven hier echter ook geen verklaring waarom een depot gelegen in het verlengde van de middengang beter is. Caron et al. (1998) bestuderen de prestaties van de traversal en return heuristiek onder een COI gebaseerd opslagbeleid waarbij deze net zoals in Hwang, Oh en Lee (2004) gelinkt worden aan de beste implementatie van dit opslagbeleid (supra). De auteurs passen de traversal heuristiek slim aan indien een oneven aantal subgangen moet bezocht worden in een blok. In dat geval moet de pikker namelijk de subgang die de ‘largest gap’ bevat niet helemaal doorsteken, maar terugkeren zoals in de return methode. De resultaten tonen aan dat de beste heuristiek afhankelijk is van het gemiddeld aantal te pikken items per subgang en van de scheefheid van de ABC curves. Het aantal subgangen speelt geen rol. In het algemeen presteert traversal beter dan return, behalve wanneer het gemiddeld aantal items per subgang zeer laag (<1) is. Onder random storage is traversal altijd even goed of beter dan return. Dit is ook aangetoond door Goetschalckx en Ratliff (1988) en Hall (1993). De return methode profiteert het meest van het COI beleid, dit voordeel zal in zeer dynamische markten echter minder groot zijn aangezien opslaglocaties vaak herzien dienen te worden om het COI beleid up-to-date te houden. Omdat in de praktijk de herziening niet continu maar periodiek gebeurt is de werkelijke ABC curve minder scheef dan de theoretische, behalve dan in de periode net na de herziening. Vaughan en Petersen (1999) onderzoeken het effect van extra dwarsgangen op de reisafstand. Zij ontwikkelen een routeringstrategie die toepasbaar is op een magazijn bestaande uit meerdere blokken: de aisle-by-aisle heuristiek. De pikker bezoekt hierbij elke langsgang slechts één maal, beginnende bij deze het dichtst bij de depot. De dwarsgang, via dewelke men overgaat naar de volgende langsgang, wordt bepaald via dynamisch programmeren. De rekentijd voor dit algoritme is bij benadering lineair in het aantal langsgangen, kwadratisch in het aantal dwarsgangen en onafhankelijk van het aantal het aantal te pikken items. De auteurs besluiten dat de rekentijd 21
verwaarloosbaar is. Een voordeel van de aisle-by-aisle heuristiek is dat deze eenrichtingsverkeer in de dwarsgangen mogelijk maakt, hierdoor mogen deze smaller zijn, wat op zijn beurt de reisafstand positief beïnvloedt. Zij concluderen onder meer dat er grote winst door het toevoegen van dwarsgangen mogelijk is wanneer de lengte van de langsgangen relatief groot wordt ten opzichte van de breedte van de dwarsgangen. Dit is intuïtief ook logisch: enerzijds leiden extra dwarsgangen tot meer flexibiliteit in de routering die bepaald wordt via de aisle-by-aisle heuristiek. Anderzijds kunnen een overmatig aantal dwarsgangen zorgen dat een te grote afstand moet overbrugd worden bij het kruisen van deze dwarsgangen. Daarnaast zullen extra dwarsgangen ook leiden tot een extra kost aangezien een grotere ruimte nodig is voor hetzelfde aantal opslaglocaties of minder opslaglocaties mogelijk zijn in dezelfde ruimte. Ook Roodbergen en De Koster (2001a) vermelden in hun studie dat het toevoegen van dwarsgangen kan leiden tot het verkorten van de routes maar dat te veel dwarsgangen een stijging van de reistijd veroorzaken. In de eerste plaats beschrijven de onderzoekers een aantal heuristieken die kunnen toegepast worden in een magazijn met 2 of meerdere dwarsgangen. Hiervoor breiden ze bestaande heuristieken zoals S-shape en largest gap uit, gebruiken ze de aisle-by-aisle methode van Vaughan en Petersen (1999) en ontwikkelen ze de combined en combined+ heuristiek. Aangezien de uitgebreide S-shape nog zal gebruikt worden in deze masterproef (deel 7), is deze heuristiek in detail beschreven in bijlage 3. De prestaties van deze heuristieken worden vervolgens getoetst aan de optimale oplossing, die verkregen wordt door toepassing van een branch-and-bound algoritme. In 74 van de 80 gevallen presteerde combined+ het best, waarbij het verschil met de optimale oplossing varieerde van 1% tot 25%, afhankelijk van het aantal langsgangen en het aantal te pikken items. De Reistijd voor de S-shape ligt minstens 7% hoger dan die van de combined heuristiek in een magazijn met drie dwarsgangen, echter wanneer het aantal dwarsgangen toeneemt convergeert dit verschil naar 0%. Ook wanneer de grootte van de piklijst stijgt dan presteert de S-shape heuristiek beter. Largest gap doet het dan weer behoorlijk in één blok en bij lage pikdensiteit, zoals ook Hall (1993) en Petersen (1997) constateerden. 6.1.4
Brede langsgangen
Wanneer de afstand tussen beide zijden van de langsgang niet verwaarloosbaar is, dan spreekt men in de literatuur van brede langsgangen. De assumptie dat de pikker van het midden van de langsgang beide opslaglocaties kan bereiken gaat hier dan niet meer op omdat een extra afstand moet worden afgelegd om 2 overstaande producten te pikken. Brede langsgangen laten onder meer tweerichtingsverkeer van vorkliften toe, opslag van producten op paletten en het keren van
22
vorkliften. Over het algemeen wordt een breedte van 3,7m als grens genomen (Goetschalckx and Ratliff, 1988 in Won en Olafsson, 2005). Caron et al. (1998) merken op dat naarmate de gangen breder zijn, de return methode relatief beter scoort ten opzichte van de traversal of S-shape heuristiek. Volgens de S-shape moet de pikker zich zigzaggend in de langsgang voortbewegen, terwijl via de return methode in het gaan de ene kant kan gepikt worden en in het terugkeren de andere. Goetschalckx and Ratliff (1988) stellen volgende heuristieken voor om de routering vast te leggen binnen een langsgang: traversal, return en fixed Zpick. Daarnaast ontwikkelden ze ook een optimale versie van het traversal algoritme waarbij de totale reisafstand binnen een langsgang geminimaliseerd wordt. Op basis van simulaties besluiten zij dat de aangepaste traversal heuristiek tot 30% efficiënter is dan de return of Z-pick heuristiek, waarbij de resultaten sterk afhankelijk zijn van de pikdensiteit en de breedte van de langsgang. Net als Caron et al.(1998) wint de return heuristiek aan belang bij zeer brede langsgangen (Goetschalckx and Ratliff, 1988 in: Won en Olafsson, 2005; Theys en Herroelen, 2005; Choe en Sharp, 1991). 6.1.5
Besluit
Routeringstrategieën krijgen in vergelijking met de andere operationele vraagstukken in magazijnen veruit het meeste aandacht in de literatuur (Gu et al., 2007). Dit is omdat een goede routering van de orderpikkers significante kostenbesparingen kan opleveren (Petersen ,1997)). Exacte algoritmes zijn ontwikkeld voor magazijnen bestaande uit één of twee blokken (De Koster en Van Der Poort (1998) en Ratliff en Rosenthal (1983). Daarnaast worden ook heuristieken voorgesteld en dit voor magazijnen bestaande uit één of meerdere blokken (o.m. Vaughan en Petersen, 1999). De S-shape (In de oudere literatuur ook wel traversal genoemd) en largest gap heuristieken komen frequent voor en worden dan ook als benchmark gebruikt om nieuwe of complexere methodes (aisle-by-aisle, combined,…) aan te toetsen. Verschillende auteurs melden significante winst in reisafstand via deze nieuwe methodes, maar de resultaten, verkregen via simulatie, zijn sterk afhankelijk van factoren zoals de lay-out van het magazijn (aantal en breedte langsgangen, even of oneven zijn van het aantal langsgangen, locatie van de depot, aantal blokken), de gekozen opslagmethode of het aantal te pikken items (o.m. Vaughan en Petersen, 1999). Belangrijk is ook dat Roodbergen en De Koster (2001a) wezen op het positieve effect van het toevoegen van dwarsgangen op de reisafstand, onafhankelijk van de gebruikte routeringheuristiek.
23
6.2 Batching
6.2.1
Inleiding
Wanneer men orders één voor één zal verzamelen en naar een depot brengen dan spreekt men in de literatuur van single order picking, discrete picking of pick-by-order. Als orders relatief klein zijn ten opzichte van de capaciteit van een pikker is het vaak voordelig om orders te groeperen en tezamen te pikken. Wanneer deze strategie wordt toegepast spreekt men van order batching: het groeperen van orders tot subsets, waarbij elke subset vervolgens afzonderlijk in één keer wordt gepikt. Impliciet zit in deze definitie de grouping constraint of het verbod op ordersplitsing vervat. In sommige gevallen groepeert men ook individuele items tot subsets, waarbij het niet uitmaakt tot welk order dit item behoort. Van den Berg (1999) wijst op de trade off tussen efficiëntie en urgentie. Bij het pikken van grote batches met veel orders zullen er langere doorlooptijden zijn voor de orders. De capaciteit van de pikker zal echter beter benut worden en hij zal over al de orders samen ook minder afstand moeten afleggen. Een oplossing om toch rekening te houden met de urgentie kan zijn om een groep van orders te onderscheiden met een hoge urgentie en deze apart van de rest te batchen. De volgende groep zal dan slechts mogen worden vrijgegeven als de eerste groep gepikt is. Dit is de statische aanpak. In de dynamische aanpak zal men aan elk order een tijdstip meegegeven waartegen het order moet gepikt zijn. Alle orders worden vervolgens onmiddellijk vrijgegeven en een planning wordt opgemaakt zodat deze deadlines kunnen gehaald worden. Hsu, Chen en Chen (2005) merken op dat niet enkel de totale reisafstand maar ook het aantal batches een rol speelt bij het bepalen van de kosten. Minder batches zorgen voor minder tijdsverlies. Voorbeelden zijn administratief tijdsverlies bij het krijgen van nieuwe instructies of tijdsverlies omdat de pikker een nieuw mandje of pikvoertuig moet ophalen (De Koster, Van Der Poort en Wolters, 1999). Daarnaast moet men voor een evenwichtige verdeling van de werklast rekening houden met de variatie in reisafstand tussen de batches. Een goede balans kan ook problemen bij het sorteren vermijden (zie 6.3.5). Choe en Sharp (1991) beschrijven twee criteria waarop men batchingstrategieën kan baseren. Ten eerste onderscheidt men proximity batching. Elk order wordt hierbij toegewezen aan een batch op basis van zijn opslaglocatie ten opzichte van de andere orders in de batch. De moeilijkheid is dus om de nabijheid van de orders ten opzichte van elkaar te bepalen en er is in dat opzicht nood aan een ‘closeness of proximity metric/measure’ (zie ook 5.7). Opdat men deze strategie efficiënt zou
24
kunnen toepassen moet men reeds op voorhand weten in welke volgorde men de items zal pikken of tenminste weten welke de mogelijke routeringmethoden zijn die men zal toepassen om de items te pikken. Op die manier kan men een betere closeness metric definiëren. Ten tweede kan men time-window batching onderscheiden. Bij deze batchingmethode groepeert men orders die binnen hetzelfde tijdsinterval worden geplaatst in eenzelfde batch. Dit is niet hetzelfde als de statische aanpak van Van den Berg (1999). Het is namelijk niet omdat een order eerst is binnengekomen dat het ook een hoge prioriteit heeft. Wanneer we het onderscheid proximity en time-window batching vergelijken met de trade off van Van den Berg (1999) dan zal men bij time-window batching eerder urgentie beklemtonen terwijl efficiëntie bij proximity batching voorop staat. We zullen in deze masterproef de verdeling van Choe en Sharp (1991) grotendeels volgen. Exacte algoritmes en de metaheuristieken worden daarentegen apart besproken. In Figuur 6.1 (paragraaf 6.2.6) geven wij vervolgens een up-to-date overzicht van de huidige literatuur inzake batchingalgoritmen, ingedeeld op basis van de aard van de oplossingsmethode en de lay-out van het magazijn waarin deze oplossingsmethode is getest. 6.2.2
Exacte algoritmes
Gademann, Van Den Berg en Van Der Hoff (2001) beschouwen het batchingprobleem in een manualpick, wave-picking magazijn bestaande uit één blok. Het doel van dit onderzoek is om de maximale doorlooptijd van een batch te minimaliseren. De auteurs stellen een branch-and-bound algoritme voor om het probleem exact op te lossen. Om goede bovengrenzen voor het branch-and-bound algoritme te verkrijgen maken ze gebruik van een 2-opt procedure. De 2-opt procedure start met het vormen van een willekeurige initiële oplossing. Vervolgens kiest men de batch, de ‘bottleneck batch’ genaamd, met de langste reisafstand, bepaald door het optimaal algoritme van Ratliff en Rosenthal (1983). Daarna berekent men de reisafstand opnieuw voor elke nieuwe oplossing die kan bekomen worden door elk order uit de bottleneck batch te verwisselen met elk order uit de overige batches. Wordt door deze wissel een betere totale reisafstand bekomen dan behoudt men deze nieuwe oplossing en kiest men een nieuwe bottleneck batch. De procedure stopt wanneer op een bepaald moment geen betere oplossing gevonden is. Men kan de procedure een aantal maal herhalen met telkens een andere initiële oplossing. Factoren die de rekentijd beïnvloeden zijn het aantal batches en orders, de lay-out, het aantal te pikken items en de spreiding van deze items over het magazijn. Om problemen met een groot aantal orders of items (niet optimaal) op te lossen menen zij dat de combinatie van het branch-and-bound algoritme en de 2-opt procedure bij een maximale rekentijd van één minuut reeds goede oplossingen kan geven.
25
Gademann en Van De Velde (2005) nemen dan weer het minimaliseren van de totale reistijd als objectief. Ten eerste tonen ze aan dat het probleem NP-hard is wanneer het aantal orders per batch groter is dan 2. Ten tweede construeren ze een branch-and-price algoritme om kleinere problemen optimaal op te lossen. Branch-and-price wordt gebruikt om grote IP (Integer programming) problemen op te lossen en is gebaseerd op LP (Lineair programming) en branch-and-bound. Via deze methode kunnen zij kleine problemen optimaal oplossen. Ten slotte stellen ze ook een iterated descent approximation algoritme voor dat geschikt is voor grotere problemen maar weliswaar geen optimale oplossing garandeert . 6.2.3
Metaheuristieken
Hsu, Chen en Chen (2005) pakken het batchingprobleem aan via een genetisch algoritme (GABM). Genetische algoritmen bootsen het ‘surviving of the fittest’ mechanisme na dat zich ook in de natuur afspeelt. Het is de bedoeling om via recombinatie en mutatie van de elementen van de populatie een zo optimaal mogelijke oplossing te bekomen. In de eerste plaats moet men een mogelijke oplossing genetisch voorstellen. Vervolgens kan men starten met het genereren van een aantal verschillende initiële oplossingen. De beginpopulatie is de verzameling van deze initiële oplossingen. Men berekent de kwaliteit van de gegenereerde oplossingen en bepaalt aan de hand daarvan hun overlevingskans. De verschillende elementen (oplossingen) worden dan gecombineerd, rekening houdend met hun overlevingskans en nieuwe oplossingen ontstaan. Na een mutatie van deze kinderen en het selecteren van de beste ouders (elitisme) zal uiteindelijk een nieuwe populatie ontstaan. Deze procedure wordt herhaald tot wanneer een stopconditie bereikt is. Zo kan men bijvoorbeeld stoppen na een vooraf bepaald aantal generaties, na een bepaalde rekentijd of wanneer de kwaliteit van de oplossing gedurende een bepaalde tijd niet meer wijzigt of naar een bepaalde waarde convergeert. Om de kwaliteit van de oplossingen te evalueren berekenen Hsu et al. (2005) de totale reistijd van de oplossing via de S-shape heuristiek. Het genetisch algoritme wordt vervolgens vergeleken met de first-come-first-serve methode (FCFS) en de methode van Gibson en Sharp (1992) (GSBM). Zowel de GABM als GSBM scoren beter dan FCFS. Daarnaast scoort GABM het best op zowel het aantal gevormde batches als de totale reisafstand. De nieuwe methode wordt ook getest voor 3D magazijnen waarbij de hoogte van de rekken in rekening wordt gebracht. GABM scoort ook daar beter dan FCFS maar de rekentijd voor GABM loopt bij deze simulatie wel op tot 5,5 u. Het genetisch algoritme is in Hsu et al. (2005) vrij goed beschreven met uitzondering van de bepaling van het aantal gevormde batches. Het is bijvoorbeeld onduidelijk op welke manier de onderzoekers het totaal aantal gevormde batches bepalen bij het vormen van de initiële populatie. Zij geven enkel een 26
waarde voor het minimale aantal batches, maar deze waarde is gebaseerd op de verhouding van de totale capaciteitsbehoefte tot de capaciteit dus houdt ze weinig rekening met de invloed van het verbod op ordersplitsing op het aantal gevormde batches. Een eenvoudig tegenvoorbeeld schept duidelijkheid: stel bijvoorbeeld dat 10 orders moeten gebatched worden waarbij het volume van elk order 9 bedraagt. Wanneer nu de capaciteit van de pikker 15 bedraagt dan zouden Hsu et al. (2005) concluderen dat het minimaal aantal batches (9x10)/15 = 6 bedraagt. Dit is fout want het minimaal aantal batches is in dit geval 10. Geen enkel order kan namelijk samengevoegd worden met een ander order aangezien de capaciteit van de pikker ontoereikend is (9+9 > 15). De minimale waarde komt daarenboven niet meer terug in de beschrijving van de werking van het algoritme. In de resultaten wordt daarentegen wel telkens geclaimd dat het genetisch algoritme gezorgd heeft voor het behalen van dit ‘minimum aantal batches’. Aangezien het aantal gevormde batches een sterke invloed zal uitoefenen op de totale reisafstand is verduidelijking omtrent de werking van het algoritme zeker aan de orde. Geïnspireerd door Hsu et al. (2005) gaan Tsai, Liou en Huang (2008) nog verder. Naast het gebruik van een genetisch algoritme voor het vormen van de batches (GA_BATCH), zullen zij ook de volgorde waarin de opslaglocaties bezocht worden (i.e. de pikvolgorde) via een genetisch algoritme vastleggen (GA_TSP). De pikker zal zich daarbij telkens begeven op het kortste pad (zie bijlage 2) tussen opeenvolgende (in de pikvolgorde) opslaglocaties. Belangrijk is dat zowel de reisafstand als de deadline van het order in beschouwing worden genomen. Een extra kost zal namelijk aangerekend worden wanneer een item niet op tijd gepikt is. In tegenstelling tot Hsu et al. (2005) is de bepaling van het aantal gevormde batches hier wel duidelijk beschreven. Voor het bepalen van het optimaal aantal batches zal men GA_BATCH verschillende malen laten lopen, telkens met een andere waarde voor het aantal gevormde batches, startend bij een minimale waarde. Men zal per cyclus de waarde van het aantal batches met 1 verhogen en dit tot een maximale waarde wordt bereikt. Het spreekt voor zich dat hoe groter de breedte van het interval [minimum aantal batches, maximum aantal batches] is, hoe langer het algoritme zal moeten rekenen. De bepaling van de breedte van dit interval laat men daarom over aan het management. Een nadeel van dit onderzoek is wel dat de auteurs de voorgestelde methode niet met bestaande heuristieken hebben kunnen vergelijken. Tsai et al. (2008) laten namelijk ordersplitsing toe, dit in tegenstelling tot de meeste andere onderzoeken (vb.: Hsu et al., 2005)). Zoals we in deel 5 reeds aanstipten is juist deze ‘grouping constraint’ een cruciaal kenmerk van het batchen van orders en zorgt zij voor de extra complexiteit bij het vinden van een gepaste oplossingsmethode. Wanneer in bovenstaande methode de ‘grouping constraint’ zou geïncorporeerd zijn dan kan zij vergeleken worden met andere batchingmethodes en zullen we de resultaten beter naar waarde kunnen schatten. 27
6.2.4
Proximity batching
Het overgrote deel van de algoritmen die ontwikkeld zijn om het batchingprobleem op te lossen via proximity batching kan men onderverdelen in seed algoritmen en savings algoritmen. Recent maakt men ook gebruik van data mining om verbanden tussen de orders te ontdekken. 6.2.4.1 Data mining / Clusteranalyse Clusteranalyse slaat op de verzameling van statistische methodes die gebruikt worden om elementen toe te wijzen aan clusters op basis van gemeenschappelijke kenmerken tussen deze elementen (Hwang en Kim, 2005). Een voorbeeld van het gebruik van clusteranalyse vindt men in Hwang en Kim (2005). Zij bepalen tussen elk paar orders een ‘measure of similarity’. De berekening van deze coëfficiënt verschilt naargelang de routering die de orderpikker na het batchen zal volgen. Zo testen ze 1 coëfficiënt voor de S-shape, 2 voor de midpoint en 2 voor de return heuristiek. De orders worden samengenomen op basis van deze coëfficiënt, vervolgens wordt tussen deze nieuwe batch en elk ander order (of batch) opnieuw een ‘measure of similarity’ berekend. De nieuwe algoritmes worden vergeleken met het algoritme van Clarke en Wright (1964) zoals beschreven in De Koster et al. (1999) en met een seed algoritme. Het is echter onduidelijk welk seed algoritme bedoeld wordt. Ze besluiten in de eerste plaats dat geen enkel van de algoritmes superieure resultaten oplevert. Ten tweede scoren de clusteralgoritmen slechter ten opzichte van het seed algoritme wanneer het aantal orders laag is (10) maar daarentegen beter wanneer er 20 of 30 orders moeten gepikt worden. Ten slotte wijzen zij er op dat het vormen van een klein aantal batches niet noodzakelijk leidt tot kleinere reisafstanden. Hwang en Kim (2005) stellen ook voor om in de toekomst een gelijkaardige oplossingsmethode te ontwikkelen voor magazijnen bestaande uit 2 blokken. Chen en Wu (2005) bestuderen een methode om batches te vormen op basis van een association based clustering benadering. Ze berekenen de nabijheid van de orders door de mate van associatie tussen de orders in rekening te brengen. Orders met veel gelijkaardige items hebben een hoger associatieniveau. Via een clustering model gebaseerd op BIP (binary integer programming) maximaliseren ze de totale associatie. Chen, Huang, Chen en Wu (2005) beschrijven een data mining methode om verbanden tussen orders te ontdekken. Data mining is een techniek waarbij men een grote hoeveelheid data bestudeert met het doel patronen of verbanden te ontdekken. Via het apriori algoritme selecteren de auteurs zogenaamde grote ‘itemsets’ bestaande uit een aantal orders. Vervolgens zal men via association rule mining de verbanden zoeken tussen deze orders. Ze vergelijken vervolgens hun resultaten, 28
verkregen door simulatie, met bestaande batchingstrategieën zoals First-come First-served, de center of gravity methode, de batchingmethode van Gibson en Sharp (1992), de ARIP methode van Chen en Wu (2005) en de ‘minimum aisle addition’ methode (bij Ho en Tseng, 2006 is dit: smallest number of additional aisles). De reisafstanden worden berekend via de S-shape routering De auteurs besluiten dat in de meeste gevallen via data mining kwalitatief betere resultaten worden bekomen. De ARIP methode scoort kwalitatief even goed maar is daarentegen trager op het vlak van rekentijd. 6.2.4.2 Seed algoritmen De constructie van een seed algoritme verloopt in 2 fasen. Eerst selecteert men het eerste order van een nieuwe batch volgens een seed selection rule. Vervolgens worden orders toegevoegd op basis van een order addition, order congruency of order accompanying rule, en dit zolang de capaciteit van de pikker dit toelaat. De order addition rule bepaalt enkel de prioriteit van de orders. De capaciteitsrestrictie kan gebaseerd zijn op bijvoorbeeld het aantal orders in een batch, het gewicht of de totale reistijd van de batch (Gu et al., 2007). Meestal voegt men orders toe op basis van de afstand tot de orders in de batch of tot het seed order. In bijlage 4 vindt de lezer de gangbare procedure betreffende de toepassing van een seed algoritme. Seed algoritmen toegepast op een ‘man on board’ AS/RS systeem waarbij het systeem slechts 1 gang heeft, worden besproken door een aantal auteurs. Pan en Liu (1995) vergelijken 16 algoritmen samengesteld uit 4 seed selection en 4 order addition rules. In hun onderzoek scoort het ‘economic vortex hull’ algoritme het best. Hwang, Baek en Lee (1988) simuleren de prestaties van 14 verschillende algoritmen. Het gebruikte algoritme is de combinatie van een seed heuristiek en een clusteranalyse. Zij besluiten dat het aangewezen is om overeenkomsten te zoeken tussen de verschillende orders om daarna te kunnen batchen op basis van ‘similarity’. Ook in Elsayed (1981), Elsayed en Stern (1983) en Hwang en Lee (1988) worden seed heuristieken in het ‘single aisle manon-board AS/RS’ systeem besproken. Wanneer het systeem meerdere gangen telt (1 blok in plaats van 1 langsgang) verhoogt de moeilijkheidsgraad van het batchingprobleem. Een veel besproken heuristiek in deze context is die van Gibson en Sharp (1992). Zij bestuderen drie methodes: four-dimensional space-filling curve, Sequential Minimal Distance en First-come-first serve. Na simulatie blijkt dat de Sequential Minimal Distance heuristiek de voorkeur geniet. In deze heuristiek wordt een order geselecteerd als seed en aan een batch toegewezen, vervolgens wordt de som genomen van de afstanden van elk item in het seed order tot het dichtstbijzijnde item in het nieuwe order. Bij het berekenen van de afstand beschouwen ze de locatie van de items als gekend maar wordt enkel het midden van de langsgang
29
waarin het item zich bevindt gebruikt om de reisafstand te berekenen. Op die manier benaderen ze slechts de echte reisafstand en het verschil is soms groot. Het order met de kleinste afstand tot het seed order wordt tenslotte toegevoegd. Dit proces herhaalt zich zolang de capaciteit toereikend is. Nadien worden de routes geëvalueerd via de S-shape routering (Gibson en Sharp, 1992 in: Bozer en Kile, 2007 en Rosenwein, 1996). Ruben en Jacobs (1999) menen dat een effectieve batchingheuristiek rekening zou moeten houden met zowel de locatie van de items in een order als de capaciteit van de pikker. In hun experiment proberen ze te identificeren welke van de twee criteria het meest doorweegt op het eindresultaat en dus het meeste aandacht verdient. De auteurs combineren verschillende batchingheuristieken met 3 opslagstrategieën en bepalen de beste combinatie. De ‘First Fit-Envelope Based Batching’ heuristiek is volgens hen veelbelovend. Deze heuristiek houdt zowel rekening met de orderlocatie als de ordergrootte en scoort in bijna alle omstandigheden goed. Voor het berekenen van de envelope index baseert men zich op de uiterste langsgangen die in het order bezocht moeten worden. De First Fit Envelope Based Batching methode scoort beter dan de heuristiek van Gibson en Sharp (1992). Ho en Tseng (2006) combineren 9 seed order selection rules en 10 order addition rules. In hun studie is elke regel ofwel gebaseerd op langsgangen die moeten bezocht worden of op de exacte locatie van de items. De combinatie van de SNPA seed selection rule, i.e. het kleinste aantal verschillende langsgangen dat moeten worden bezocht in een order, en de SNAPA addition rule, i.e. het order waarbij de batch na toevoeging het minst aantal extra langsgangen bevat, scoort het best. Eerder onderzochten De Koster et al. (1999) reeds 84 verschillende seed algoritmen. Zij combineerden namelijk 2 seed rules (enkelvoudig of cumulatief), 6 seed selection en 7 order addition rules. Ze merken op dat in het geval dat twee orders identiek scoren op een order addition criteria, het order dat de grootste capaciteit in beslag neemt moet worden toegevoegd. Ze veronderstellen hierbij dat een kleiner order in een latere fase makkelijker kan worden toegevoegd. In Wolters (1996) vindt men een vrij compleet overzicht van de bestaande seed selection rules. Seed algoritmen in magazijnen uit één blok vindt men ook in Rosenwein (1994) . 6.2.4.3 Savings algoritmen De savings algoritmen zijn gebaseerd op het algoritme van Clarke en Wright (1964), ontwikkeld voor het vehicle routing problem (VRP). De logica achter dit algoritme kan duidelijk gemaakt worden aan de hand van een eenvoudig voorbeeld. Stel dat een bedrijf twee klanten bedient. Initieel zullen zij vanaf de depot een vrachtwagen naar de eerste klant laten rijden en terug. Vervolgens zal de andere 30
klant bediend worden op dezelfde manier. Het spreekt voor zich dat indien de capaciteit van de vrachtwagen bij een bepaalde trip niet volledig benut is, er mogelijkheden zijn tot efficiëntieverbetering. Door bijvoorbeeld de twee routes te combineren tot één route kan men vaak de totale reisafstand verkorten en dus de kosten verminderen. In een situatie met meer dan twee klanten zal men juist die klanten samenvoegen en bevoorraden in één route, zodat in elke ronde de grootste besparing wordt bekomen. Toegepast op het orderbatchen zal elk order dus worden toegewezen aan een aparte batch. Vervolgens worden twee batches gecombineerd of samengenomen op basis van de opgeleverde winst (combination rule) en dit zolang de capaciteit van de pikker toereikend is. Elsayed en Unal (1989) bestuderen vier batchingheuristieken in een AS/RS waarbij het SL (Small Large) algoritme als beste naar voor komt. Dit algoritme deelt de orders in kleine en grote orders in. De grote orders worden eerst gebatched volgens de EQUAL methode, vervolgens voegt men de kleine orders toe aan de batches gebaseerd op de potentiële winst. In de EQUAL methode wordt de seed bepaald door de twee orders, die de grootste besparingen opleveren, samen te nemen. De besparingen worden berekend aan de hand van het handelsreizigeralgoritme, besproken in Little et al. (1963). Vervolgens zal men aan deze combinatie het order toevoegen welke de meeste besparingen zal opleveren. Ook Hwang en Lee (1988) bestuderen het savings algoritme in een AS/RS. Rosenwein (1996) beschrijft methodes om de afstand tussen orders te meten. De eerste methode is gebaseerd op het principe van de savings heuristiek van Clarke en Wright (1964). Wanneer men veronderstelt dat een S-Shape routering wordt gevolgd dan is het logisch om rekening te houden met het aantal extra gangen dat moet worden bezocht indien 2 orders worden gecombineerd. Dit was ook het uitgangspunt van de SNAPA addition rule van Ho en Tseng (2006). Het verschil zit hem in de procedure die gebruikt wordt (seed vs. savings). De tweede methode is dan weer gebaseerd op het centre of gravity principe. Ze introduceren een savings heuristiek gebaseerd op deze twee afstandsmaten en vergelijken die met de seed methode van Gibson en Sharp (1992). Hun savings heuristiek scoort tot 12% beter op de totale reisafstand maar heeft wel tot 2 maal meer rekentijd nodig. De Koster et al. (1999) vergelijken de prestaties van verscheidene seed en savings algoritmen. Opvallend is dat zij de savings heuristiek van Clarke en Wright (1964) aanpassen zodat deze naast het minimaliseren van de reisafstand ook het aantal batches tot een minimum tracht te beperken. Dit doen zij door een penalty toe te kennen aan orders die individueel worden gepikt. Het is echter moeilijk om een optimale waarde voor deze penalty te bepalen. Aangezien wij in deze masterproef nog zullen gebruik maken van dit aangepast algoritme, staat in bijlage 5 de exacte procedure 31
beschreven. Zij concluderen in de eerste plaats dat het sowieso beter is te batchen dan helemaal niet te batchen en dat alle onderzochte methodes beter scoren dan de FCFS methode. Ten tweede stellen zij vast dat de seed algoritmen beter presteren in combinatie met een hogere capaciteit van de pikker en een S-shape routeringheuristiek. De savings algoritmen scoren dan weer goed in combinatie met de largest gap routeringheuristiek en een lagere capaciteit van de pikker. Ten slotte merken zij op dat door het minimaliseren van de reisafstand vaak, het aantal gevormde batches beperkt blijft. Omgekeerd is dit echter niet het geval. Dit is overeenkomstig Hwang en Kim (2005). Op basis van deze stelling rechtvaardigen ze het gebruik van de reisafstand (in plaats van de minimalisatie van het aantal batches) in de doelfunctie. 6.2.5
Time window batching
Chew en Tang (1999) raden time window batching aan wanneer het piksysteem (i) een groot volume aan orders moet verwerken, (ii) de informatie over de orders niet op voorhand gekend is en (iii) er slechts een beperkt aantal pikkers beschikbaar zijn. Zij beschouwen het piksysteem als een wachtlijn en berekenen het vereiste aantal pikkers, gegeven het service level. Tang en Chew (1997) ontwikkelden een methode om de gemiddelde tijd te berekenen dat een order in het systeem doorbrengt, i.e. de doorlooptijd van het order. De resultaten kunnen gebruikt worden om het optimale aantal orders per batch te berekenen. Le-Duc en De Koster (2007) bouwen verder op het onderzoek van Chew en Tang (1999) maar bestuderen als enige tot nu toe het batchingprobleem in een magazijn bestaande uit twee blokken. In Roodbergen en De Koster (2001b) is namelijk aangetoond dat een magazijn met een middengang vaak kortere reistijden oplevert dan een magazijn zonder middengang. Zij tonen aan dat de gemiddelde wachttijd van een order in functie van de batchgrootte een convexe functie is. Daaruit volgt dat er altijd een unieke optimale batchgrootte bestaat die deze gemiddelde wachttijd minimaliseert. Elsayed, Lee, Kim en Scherer (1993) bestuderen het order batchingprobleem in een AS/RS waarbij de orders een deadline krijgen. De deadline is het tijdstip waarop het order moet gepikt zijn. Het groeperen van de batches gebeurd op basis van een doelfunctie die zowel het te vroeg als het te laat pikken van het order bestraft. De auteurs stimuleren op die manier just-in-time picking. Om de oplossingen na simulatie te evalueren voeren zij de Traffic Congestion ratio in. Deze geeft een indicatie van de waarschijnlijkheid van het halen van de order deadlines. Wanneer de S/R machine een lage capaciteit heeft besluiten zij dat er niet echt een voordeel is om orders te batchen, rekening houdend met de doelfunctie. Elsayed en Lee (1996) bouwen hierop verder en bekijken hoe men het
32
in voorraad leggen en het ophalen van orders kan combineren en in welke volgorde dit best zou gebeuren. Men probeert daarenboven de vertraging van het ophaalorder te minimaliseren (Elsayed en Lee, 1996 in: Gademann et al., 2001). Won en Olafsson (2005) bepalen de optimale tijd tussen het pikken van twee batches in een typisch AS/RS. De doelfunctie is een gewogen gemiddelde van de tijd nodig om de orders te pikken (reistijd) en de tijd dat het order moet wachten (holding time). Door de wegingcoëfficiënten aan te passen kan men dus ofwel efficiëntie stimuleren ofwel lagere wachttijden aanmoedigen. Ze stellen ook een tweede algoritme voor: Joint Order Batching and Picking (JBP). Dit algoritme zou het batching- en pikproces integreren en zou nog een betere oplossing kunnen bieden. Aangezien dit algoritme perfect aansluit bij onze onderzoeksvraag, zou dit een interessant algoritme kunnen zijn. De auteurs blijven echter te vaag over de inhoud van dit algoritme (JBP) zodat de resultaten niet op hun waarde kunnen beoordeeld worden. 6.2.6
Besluit
In dit hoofdstuk werd de onderzochte literatuur ingedeeld en besproken volgens de aard van de batchingalgoritmes. Exacte algoritmes zijn ontwikkeld voor problemen met een klein aantal orders of batches (Gademann et al., 2001 en Gademann en Van De Velde, 2005). Voor meer realistische situaties stelt men heuristieken voor. Het overgrote deel zijn construction heuristieken zoals de seed en savings heuristieken (o.m. De Koster et al., 1999). Inzake seed algoritmen zijn de addition rules, gebaseerd op de vergelijking tussen de langsgangen in de batch en het kandidaat order, vrij efficiënt en dus populair. Meer recent wordt er ook gezocht in de richting van data mining en metaheuristieken. Opvallend is ook dat nagenoeg alle auteurs de batchingheuristieken vergelijken op basis van de reisafstand verkregen via de S-shape routering. De First-come-first-serve (of random) batchingmethode geldt daarbij als één van de belangrijkste benchmarks. De prestaties van de batchingheuristieken zijn echter sterk afhankelijk van de lay-out van het magazijn, de verhouding van de capaciteit van de pikker tot de grootte van de orders, het aantal orders, het opslagbeleid en de gebruikte routeringmethode (o.m. De Koster et al., 1999). Anderzijds kunnen we de literatuur ook indelen op basis van de lay-out van het magazijn waarin de de batchingheuristieken gesimuleerd werden en de aard van het piksysteem (picker-to-part, manon-board of AS/RS). In deze masterproef ligt de focus op picker-to-part systemen. Opvallend is dat er slechts één studie bestaat over het batchen in een magazijn uit meer dan één blok (Le-Duc en De Koster, 2007). Alhoewel reeds is aangetoond in Roodbergen en De Koster (2001a) en Vaughan en Petersen (1999) dat het verdelen van magazijnen in verschillende blokken een positief effect kan
33
hebben op de reistijd van de pikker, blijven simulaties in magazijnen bestaande uit meer dan twee blokken alsnog uit. Vele seed en savings heuristieken zijn daarenboven specifiek ontworpen voor een traditioneel magazijn met slechts 2 dwarsgangen waardoor de uitbreiding naar een complexere lay-out ook een aanpassing van het algoritme vergt. Het is dus onzeker of de algoritmes in een complexe lay-out op dezelfde manier zullen presteren als in een traditioneel magazijn. Figuur 6.1 geeft een overzicht van de huidige literatuur, ingedeeld naar de aard van de oplossingsmethode en de lay-out van het magazijn waarin deze oplossingsmethode is toegepast.
34
Figuur 6.1 Literatuuroverzicht van de batchingalgoritmen
35
Ho en Tseng (2006) De Koster et al. (1999) De Koster, Van Der Poort en Wolters (1999) Gibson en Sharp (1992) Rosenwein (1996) Rosenwein (1994) De Koster et al. (1999) Rosenwein (1996)
Pan en Liu (1995) (S/RS) Hwang en Lee (1988) (S/RS) Hwang, Baek en Lee (1988) (S/RS) Elsayed en Stern (1983) (S/RS) Elsayed (1981) Hwang en Lee (1988) (S/RS) Elsayed en Unal (1989) (S/RS)
Tsai, Liou en Huang (2008) (2D en 3D) Hsu, Chen en Chen (2005) (2D en 3D)
METAHEURISTIEK
S/RS = Storage Retrieval System (automated of man-on-board) 3D = Driedimensionaal magazijn
Gademann en Van De Velde (2005) Gademann, Van Den Berg en Van Der Hoff (2001)
Chew en Tang (1999) Tang en Chew (1997)
Chen, Huang, Chen en Wu (2005) Chen en Wu (2005) Hwang en Kim (2005)
Ruben en Jacobs (1999) Won en Olafsson (2005) (S/RS)
1 blok
Elsayed, Lee, Kim en Scherer (1993) (S/RS) Elsayed en Lee (1996) (S/RS)
1 gang
EXACT
WACHTLIJNTHEORIE
DATA MINING & CLUSTERING
SAVINGS
SEED
LOCAL SEARCH & CONSTRUCTION HEURISTIEKEN
Aard oplossingsmethode / lay-out
Le-Duc en De Koster (2007)
2 blokken
> 2 blokken
6.3 Sorteren 6.3.1
Inleiding
Wanneer men batches heeft gevormd moeten de items na het pikken gesorteerd en/of samengevoegd worden per order of bestemming (pick-and-sort). Dit proces noemt men het sorteerof consolidatieproces. In vele picker-to-parts systemen zal men echter sorteren tijdens het pikken zelf (sort-while-pick). In 6.3.2 wordt een kort overzicht gegeven van de verschillen tussen deze twee sorteerprincipes. De keuze van het gepaste sorteersysteem is echter geen operationeel vraagstuk. Wij zullen de verschillen toch kort beschrijven om de invloed van de batchingmethodes op de sorteerkost (6.3.3) beter te kunnen begrijpen. De operationele beslissing bij het sorteren (zie 4.3) is volgens Gu et al. (2007) de beslissing omtrent de keuze van order-to-lane toewijzingsalgoritme. Dit algoritme moet op een zo efficiënt mogelijk wijze orders of items toewijzen aan sorteerlanen. Een overzicht van de bestaande oplossingsmethoden voor dit operationeel probleem wordt gegeven in 6.3.4. 6.3.2
Sort-while pick vs. pick-and-sort
In de literatuur onderscheidt men hoofdzakelijk twee sorteerprincipes: ‘sort-while pick’ en ‘pick-andsort’ (De Koster et al., 1999 en Gademann en Van De Velde, 2005 ). In nagenoeg alle onderzochte literatuur waarin batchingalgoritmen worden gesimuleerd en vergeleken veronderstelt men een sort-while pick procedure, waarbij de pikker tijdens het verzamelen de items reeds sorteert. Na het pikken zullen dus weinig tot geen sorteerinspanningen meer nodig zijn. Daartegenover staan de Pickand-sort systemen: In deze methodes wordt het pikken gescheiden van het sorteren. Nadat alle items van de batch verzameld zijn worden zij in het sorteersysteem gebracht. Het grote voordeel van een pick-and-sort strategie is dat er tijdens het pikken geen tijd verloren gaat aan het sorteren. De pikker zal dus meer items kunnen pikken in dezelfde tijdsspanne. Er is op die manier dus duidelijk een trade off tussen pikefficiëntie en de investeringen in een sorteersysteem. Parikh en Meller (2008) wijzen erop dat dit in essentie ook een afweging is tussen arbeids- en kapitaalkosten. Het pikken van de orders is namelijk arbeidsintensief (zie 3.3) terwijl de investering in een sorteersysteem een kapitaalinvestering betreft. Daarenboven zal via pick-and-sort de capaciteit van de pikker beter kunnen benut worden. Door het weglaten van verschillende compartimenten zal de ruimte van het voertuig efficiënter benut worden. In een sort-while-pick systeem wordt de ruimte in het voertuig dus minder goed benut naarmate het gemiddeld aantal verschillende orders in een batch stijgt. Het spreekt voor zich dat sort-while-pick enkel realistisch is
36
wanneer men relatief weinig orders pikt in eenzelfde route, dus in het geval van een relatief kleine batchgrootte (Ruben en Jacbos, 1999). Een voorstelling van een traditioneel pick-and-sort sorteersysteem kunnen we vinden in Choe en Sharp (1991) en in De Koster et al. (2007). Beiden beschrijven een automatisch ‘closed-loop’ sorteersysteem. De input voor het systeem is een batch bestaande uit een aantal items, die behoren tot een welbepaald order. Wanneer het item voorbij een sensor passeert zal deze het bijhorend order identificeren. Items van een welbepaald order zullen slechts in de binnenste loop kunnen terechtkomen en aan een sorteerlaan worden toegewezen indien alle items van dit order in het sorteersysteem zijn gebracht. Zolang dat dit niet het geval is zullen de items in een buitenste loop circuleren rond de binnenste loop. Eens de binnenste loop is bereikt zal het item langs de verschillende sorteerlanen passeren en wordt dit item eventueel naar een laan gestuurd, conform het toewijzingsalgoritme. Indien geen laan beschikbaar is blijft het item in de binnenste loop circuleren. Een laan kan bijvoorbeeld geblokkeerd zijn wanneer deze reeds vol is of wanneer het item niet mag toegewezen worden aan die laan om andere reden. Er moet op gewezen worden dat niet alle auteurs spreken over een binnenste en een buitenste loop en dus niet altijd de restrictie opnemen dat alle items van het order zich reeds in het systeem moeten bevinden voordat aan het order een laan wordt toegewezen. 6.3.3
De invloed van het batchingproces op het sorteerproces
Brynzér en Johansson (1995) wijzen erop dat het pikken van batches in plaats van individuele orders de complexiteit van het orderpikken (routeren, batchen en sorteren) verhoogt. Zij beschrijven de trade off tussen een hogere pikefficiëntie door winst in reistijd en de toenemende complexiteit van de administratieve en de sorteerprocessen. Wanneer men dus het positieve effect van batchen wil laten doorwegen in de eindafrekening moet zowel de design van het sorteerproces als de consequenties van de gekozen batching- of zoningmethode op het sorteerproces grondig bestudeerd worden. Zo kan men bijvoorbeeld overwegen om het sorteerproces te mechaniseren. Deze laatste beslissing is echter geen operationele beslissing. De beslissing omtrent de automatisering van het sorteerproces vergt namelijk een aanzienlijke investering en men zal een ruime tijdshorizon in acht moeten nemen. Wanneer de orders in hun geheel gepikt worden (ordersplitsing is niet toegelaten) zal de consolidatie tot een minimum beperkt worden. Het samenvoegen van items uit verschillende batches behorende tot hetzelfde order valt dan weg. Enkel de consolidatie van orders die samen
37
horen (omdat zij bijvoorbeeld samen getransporteerd zullen worden) zal dan nodig zijn. De Koster et al. (1999) wijzen op de stijgende kosten bij een groter aantal consolidatiegroepen. Ruben en Jacobs (1999) merken op dat de grootte van de batch de kost van het sorteren beïnvloedt. Zij vinden het daarom belangrijk dat het effect van de pikcapaciteit op de sorteerkost wordt bestudeerd. Net als de meeste onderzoekers nemen zij de kost voor het sorteren niet expliciet op in hun model. Tang en Chew (1999) en Chew en Tang (1997) (zie 6.2.5) doen dit wel. De tijd voor het sorteren via de sort-while pick methode wordt gemodelleerd op basis van een kansdichtheid, maar het is uit hun onderzoek niet mogelijk om conclusies te trekken omtrent de invloed van de gekozen batchingmethode op de sorteertijd. Deze zijn in hun model namelijk onafhankelijk van mekaar gemodelleerd. De tijd voor het sorteren tijdens het pikken wordt in de overige onderzoeken vaak gemodelleerd door bij de totale tijd nodig om een item te pikken een vaste tijdsduur op te tellen. De Koster et al. (2007) beschrijven een situatie waarbij ordersplitsing is toegelaten en meerdere orders tezelfdertijd worden gepikt per zone. Dit in tegenstelling tot een meer traditionele zoning strategie waarbij orders wel mogen gesplitst worden maar slechts één order tezelfdertijd wordt gepikt. Deze situatie verhoogt natuurlijk nog eens extra de complexiteit van het sorteerproces. Parikh en Meller (2008) ontwikkelen een kostenmodel dat kan toegepast worden op de combinaties van twee zoning strategieën (sequentieel en gelijktijdig) en twee sorteermethodes (sort-while pick en pick-and-sort). Vier kosten worden in rekening gebracht: arbeids-, kapitaal-, synchronisatie- en sorteerkosten. Met synchronisatiekosten worden de kosten bedoeld die voortvloeien uit een onevenwichtige verdeling van het werk. Daarnaast onderscheiden ze vaste en variabele kosten. Vooral de kosten, die afhangen van het aantal aanvoerstations, invoerpunten per station en het aantal sorteerlanen zijn van groot belang. Ze evalueren de kosten in functie van het aantal orders en items per order dat moet worden gesorteerd. In het sorteersysteem variëren ze naast het aantal lanen, invoerpunten en aanvoerstations ook het totaal aantal orders dat moet worden gesorteerd en het aantal orders toegewezen aan elke laan. De onderzoekers wijzen er op dat de marginale opbrengsten van een extra aanvoerstation of invoerpunt een dalende functie is van het aantal aanwezige aanvoerstations en invoerpunten. De auteurs besluiten dat de relatie tussen het aantal orders en de kosten van het sorteersysteem een convexe functie is. 6.3.4
Order-to-lane algoritmen
De Koster et al. (2007) wijzen erop dat de performantie van het sorteersysteem afhangt van zowel de sorteerinstallatie als van operationele beslissingen. Een belangrijke beslissing is de toewijzing van de orders aan de sorteerlanen en dit omdat het aantal lanen vaak kleiner is dan het aantal orders. 38
Order-to-lane algoritmen kunnen bestudeerd worden als onderdeel van de ‘conveyor’ theorie. Het sorteerproces is echter vrij specifiek en verschilt van de klassieke conveyor theorie doordat verondersteld wordt dat een order niet verloren gaat wanneer er geen plaats meer is in een laan. Het order zal namelijk gewoon terug in de loop gaan en circuleren. Daarenboven kunnen bepaalde lanen ook vast toegewezen zijn aan specifieke transportbedrijven. Hierdoor kunnen sommige orders dus nooit toegewezen worden aan deze lanen (Johnson, 1998). 6.3.4.1 Heuristieken Bozer en Sharp (1985) (in: Choe en Sharp, 1991) bestuderen als eerste de order-to-lane algoritmen in detail. Variabele parameters zijn onder meer het aantal en de lengte van de lanen en de aanwezigheid van een loop. Belangrijk om te vermelden is dat het aantal lanen in deze studie groter of gelijk is dan het aantal orders. Bozer, Quiroz, and Sharp (1988) (in: Choe en Sharp, 1991) bestuderen het toewijzen van orders aan sorteerlanen in een automatische sorteeromgeving waarin het aantal orders in de batch groter is dan het aantal beschikbare lanen. Dit is een meer realistische situatie dan in Bozer et al. (1988). De doorlooptijd van een order wordt voornamelijk bepaald door het aantal keer dat een item terechtkomt in de loop. Zij stellen dat de toevallige toewijzing, Firstcome-first-serve, de beste methode is om de doorlooptijd te minimaliseren. In een statische methode wordt een schema opgesteld volgens een prioriteitsregel, die geen rekening zal houden met de volgorde waarin de items de sorteerband zullen betreden. Tijdens het sorteren zal het schema dan ook niet meer gewijzigd worden. Men zou het principe ‘eerst het kleinste order’ kunnen verantwoorden via de wachtlijntheorie. Het kleinste order voorop in de rij plaatsen verkleint de gemiddelde doorlooptijd. Wanneer men het grootste order eerst zal batchen doelt men eerder op het verminderen van het aantal maal dat een item een loop zal maken. Statische toewijzingsschema’s zoals ‘sorteer het grootste (kleinste) order eerst’ scoren altijd slechter of even goed als de dynamische First-come-first serve methode. Johnson (1998) toont dit via een analytisch model aan. Er moet wel opgemerkt worden dat voor de opbouw van het analytisch model het blokkeren van orders door een tekort aan capaciteit in de lanen niet in beschouwing wordt genomen. De onderzoekers geven ook een formule voor de potentiële verbetering tussen de statische en dynamische methode. De potentiële verbetering is een inverse functie van de ordergrootte (1/n²). Dus bij het sorteren van kleinere orders is de dynamische methode zeer voordelig. Vervolgens vergelijken ze het analytisch model met resultaten verkregen door simulatie. Een tweede simulatie is nodig om het effect van geblokkeerde lanen te kunnen inschatten, dit was initieel niet in het analytisch model opgenomen. Ze besluiten dat indien de sorteerlanen vaak
39
geblokkeerd worden, omdat het proces om de lanen vrij te maken relatief veel tijd in beslag neemt, er weinig potentieel is tot verbetering door de keuze van een gepaste sorteerregel. 6.3.4.2 Exact algoritme Ook in Meller (1997) komen de items van elk order in een willekeurige volgorde voorbij het invoerpunt en zal de toewijzing niet statisch gebeuren, maar bij het passeren aan de scanner net voor het invoerpunt. Het probleem wordt gemodelleerd als een binair integer programming probleem en vervolgens ontwikkelt men een algoritme dat zal rekening houden met de volgorde van de binnenkomende items. De doelfunctie is het minimaliseren van de maximale doorlooptijd van een order. Belangrijk is dat het uitvoeren van het dynamisch algoritme slechts enkele seconden mag duren. De items moeten namelijk gekoppeld zijn aan een laan voordat zij daadwerkelijk de laan hebben bereikt. Voor kleine problemen zal het algoritme een optimale oplossing kunnen voorstellen. In praktijk is het echter niet altijd belangrijk om de optimale oplossing te kennen, het is voldoende dat alle orders gesorteerd zijn voordat de volgende golf van batches of orders het sorteersysteem betreedt. Belangrijk voor de prestaties van het algoritme is de mate waarin de volgorde van de items gekend is voordat de items het sorteersysteem bereiken. Een betrouwbare informatiestroom tussen de verschillende subsystemen in het magazijn is om die reden aangewezen. Meller (1997) onderstreept in die context ook het belang van een goede balans tussen het piksysteem en het sorteersysteem. De auteur stelt voor om de planning voor het pikken (de pikvolgorde en de samenstelling van de batches) op te stellen op basis van de verwachte sorteertijden. Ook is het balanceren van de verschillende pikgolven (keuze tijdsvensters, grootte van de zones en batches) belangrijk voor een efficiënte werking van het sorteersysteem. De auteurs pleiten dus voor een meer algemene probleemstelling die het pikprobleem en het sorteerprobleem integreert. 6.3.5
Besluit
We onderzochten de literatuur inzake sorteersystemen en order-to-lane algoritmes omdat dit relevant was voor het onderwerp van deze masterproef, namelijk de verdere integratie van de operationele beslissingen gerelateerd aan het orderpikken. Onder meer Meller (1997) en Johnson (1998) pleiten voor een verdere integratie tussen de order-to-lane, de batching- en routeringprocedure. Deze algemene probleemstelling wordt nog niet concreet ingevuld door deze auteurs aangezien zij enkel het order-to-lane algoritme optimaliseren, gegeven de pikvolgorde. Er wordt wel gesuggereerd dat integratie het best kan gebeuren door de pikgolven en de zones waarin gepikt wordt optimaal te balanceren en gelijktijdig rekening te houden met de capaciteit van het
40
sorteersysteem. Omdat een vlotte doorstroming van goederen in een magazijn belangrijk is, verdient dit probleem in de toekomst zeker meer aandacht. Verder onderzochten we welke factoren invloed kunnen uitoefenen op de algemene kosten van een sorteersysteem. Bij de keuze van een sorteermethode moet men verschillende kosten ten opzichte van elkaar afwegen. In essentie zal dit meestal een trade off zijn tussen arbeidskosten en kapitaalkosten. Belangrijk is dat het aantal orders of het aantal consolidatiegroepen een significante invloed zal uitoefenen op de kosten van het automatisch sorteersysteem (in het geval van pick-andsort). Maar ook in een sort-while-pick situatie zal het sorteren voor de pikker complexer zijn en zal de capaciteit minder goed benut worden wanneer er zich een groter aantal orders in de batch bevinden.
41
7. Eigen emprisch onderzoek In 7.1 wordt een beschrijving gegeven van de verschillende algoritmen die zullen gebruikt worden tijdens de experimenten. Vervolgens worden in 7.2 de assumpties besproken die zullen gelden voor alle experimenten. Ook wordt in dit hoofdstuk de lay-out van het magazijn vastgelegd. In 7.3 wordt de methode beschreven die het aantal herhalingen per simulatie bepaalt. Definities van de reisafstand en benuttinggraad, belangrijke prestatiemaatstaven, worden gegeven in 7.4. 7.5 geeft een toelichting bij de programmeercode. De specifieke assumpties en resultaten per experiment worden besproken in 7.6, 7.7 en 7.8. Ten slotte volgt een besluit in 7.9. 7.1 Algoritmen In de experimenten zullen we verschillende geïntegreerde methoden (GM) testen. Elk van deze methoden bestaat uit vier delen. Een routeringalgoritme, een samenvoegingprocedure, een batchingheuristiek en een verbeteringsalgoritme. In dit hoofdstuk zullen we de rol van elk element toelichten en de verschillende algoritmen beschrijven die in de experimenten zullen gebruikt worden. De algoritmen zijn ingedeeld per element van de geïntegreerde methode en naargelang de aard van het algoritme. 7.1.1
Routering
7.1.1.1 S-shape Aangezien in de literatuur en in de realiteit de S-shape of traversal routering enorm veel gebruikt wordt (zie 6.1.5 en 6.2.6) zullen wij deze heuristiek integreren in enkele van de methodes. De aangepaste S-shape voor meerdere blokken zal geprogrammeerd worden zoals beschreven in Roodbergen en De Koster (2001a). De exacte procedure van de uitgebreide S-shape vindt de lezer in bijlage 3. 7.1.1.2 Kortste pad routering (KP) Pikt men volgens de kortste pad routering dan zal men gegeven een pikvolgorde van items in een batch telkens het kortste pad volgen tussen twee opeenvolgende te bezoeken opslaglocaties in de batch. Het bepalen van het kortste pad in een magazijn tussen twee opslaglocaties of tussen een opslaglocatie en de depot is vrij eenvoudig. In tegenstelling tot de S-shape bepaalt deze heuristiek dus niet zelf de pikvolgorde van de items in een batch maar is dit een noodzakelijke input. KP bepaalt dus enkel het kortste pad tussen twee opeenvolgende te bezoeken locaties. De wijze waarop het kortste pad kan berekend worden vindt de lezer in bijlage 2. 42
7.1.2
Samenvoegingprocedures
De samenvoegingprocedure kan gezien worden als een link tussen de batchingprocedure en de routeringprocedure. In de batchingprocedure zal men een order en een batch selecteren. Dit order moet daarna worden toegevoegd aan een batch of twee batches/orders moeten worden samengevoegd tot één batch. De vraag is nu op welke manier de items in de batch zullen geordend zijn (de pikvolgorde) net na deze samenvoeging. Het batchingalgoritme wordt dus gedefinieerd als het algoritme dat de wijze bepaalt waarop orders of batches worden geselecteerd om te worden samengevoegd en deze orders of batches vervolgens ook selecteert. Het samenvoegen zelf wordt bij wijze
van
spreken
uitbesteed
aan
de
samenvoegingprocedure.
De
input
voor
de
samenvoegingprocedure is dus een combinatie van een aantal orders of batches (en de huidige overeenkomstige pikvolgordes), de output is een tijdelijke of definitieve pikvolgorde. De samenvoegingprocedure is vooral belangrijk in combinatie met de KP routering. We stellen 2 procedures voor. De eerste procedure (S1) is puur formeel en wordt gebruikt in combinatie met de S-shape routeringmethode. De INS samenvoegingprocedure voegt wel degelijk waarde toe en kan gebruikt worden in combinatie met KP. 7.1.2.1 S1 Indien men in de geïntegreerde methode enkel gebruikt maakt van routeringalgoritmes zoals de Sshape, largest gap, mid-point, aisle-by-aisle enz… dan zal de samenvoegingprocedure triviaal zijn. Het maakt dan helemaal niet uit wat de volgorde van de items in de batch is vlak na de samenvoeging. De pikvolgorde wordt door deze routeringalgoritmen namelijk ondubbelzinnig vastgelegd, gegeven de items/orders in de batch. Dus wanneer één van deze routeringalgoritmen zal gebruik maken van de huidige pikvolgorde zal deze de huidige pikvolgorde als het ware overschrijven. In combinatie met deze routeringalgoritmes wordt dan ook de eenvoudige samenvoeginsprocedure S1 gebruikt (figuur 7.1). Ondanks het mindere belang van dit algoritme wordt het toch beschreven omdat het zo is geprogrammeerd.
43
Stel B gelijk aan een bestaande batch of een nieuwe batch. B heeft reeds een pikvolgorde Vb, bepaald tijdens een eerdere samenvoegingprocedure of indien de batch nieuw is, wordt een lege Vb aangemaakt. Y is het order of een andere batch dat men wil toevoegen aan B. Indien Y een order is dan zijn de items van het order gerangschikt volgens oplopende opslaglocatie. Indien Y een batch is dan is de pikvolgorde Vy binnen Y bepaald door een vorige samenvoegingprocedure. Stap 1: Selecteer het eerste item uit Vy, ga naar stap 3. Stap 2: Selecteer het volgende item uit Vy. Ga naar stap 3. Stap 3: Indien Vb nog leeg is: voeg het item toe op de eerste plaats in Vb. Anders: voeg dit item toe in Vb na het huidige laatste item uit Vb. Ga naar stap 4. Stap 4: Stop indien dit item het laatste item uit Vy was, indien niet ga naar stap 2 Figuur 7.1 Procedure voor S1 7.1.2.2 INS Wanneer men de items zal pikken volgens KP dan moet de pikvolgorde reeds gekend zijn voordat men KP kan toepassen. KP bepaalt namelijk niet de pikvolgorde, maar enkel de manier waarop je van de ene naar de volgende opslaglocatie reist. Het zou dus handig zijn indien de pikvolgorde reeds kan geconstrueerd worden tijdens het batchen. Daarenboven zal de huidige pikvolgorde van de batches zelf invloed kunnen hebben op het batchingproces. Sommige batchingmethodes zullen namelijk de orders selecteren op basis van de nabijheid tot de bestaande batches en dit gegeven de tijdelijke routes. Om deze tijdelijke routes te kunnen berekenen is dus ook de tijdelijke pikvolgorde van belang. Er is dus tweerichtingsverkeer. De wijze waarop deze pikvolgorde wordt aangepast wanneer twee orders/batches of een order en een batch worden samengevoegd noemen we in deze masterproef de samenvoegingprocedure. Deze samenvoegingprocedure zorgt er ook voor dat het batchen en routeren niet sequentieel gebeurt: de route wordt namelijk al geconstrueerd tijdens het batchen. De voorgestelde samenvoegingprocedure (INS) kan een meerwaarde bieden in combinatie met KP. De procedure is een variant op de insertion constructie heuristiek voor het TSP en staat beschreven in figuur 7.2. Het kenmerk van een insertion heuristiek is dat deze in elke stap een lokaal optimum nastreeft.
44
Stel B gelijk aan een bestaande batch of een nieuwe batch. B heeft reeds een pikvolgorde Vb, bepaald tijdens een eerdere samenvoegingprocedure, of indien de batch nieuw is, wordt een lege Vb aangemaakt. Y is het order of een andere batch dat men wil toevoegen aan B. Indien Y een order is dan zijn de items van het order in onze experimenten gerangschikt volgens oplopende opslaglocatie. Indien Y een batch is dan is de pikvolgorde Vy binnen Y bepaald door een vorige samenvoegingprocedure. Stap 1: Stel de virtuele pikvolgorde Vv = Vb Selecteer het eerste item uit Vy, ga naar stap 3. Stap 2: Stel Vv = Vb. Selecteer het volgende item uit Vy. Ga naar stap 3. Stap 3: Voeg dit item toe op elke mogelijke plaats in Vv, bereken de overeenkomstige routes volgens KP en onthoud de plaats die de kortste afstand opleverde. Ga naar stap 4. Stap 4: Voeg het item toe in Vb op de beste plaats. Ga naar stap 5. Stap 5: Stop indien dit item het laatste item uit Vy was, indien niet ga naar stap 2 Figuur 7.2 Procedure voor INS 7.1.3
Batching
7.1.3.1 Seed algoritme Enkele seed heuristieken zullen in het onderzoek worden opgenomen. De procedure voor het selecteren van een seed en het vervolgens toevoegen van extra orders aan de batch wordt volledig geprogrammeerd conform Ho en Tseng (2006). Dit model vindt de lezer terug in bijlage 4. 7.1.3.1.1
FCFS (First come First serve)
FCFS is het meest eenvoudige algoritme en kan als benchmark worden gebruikt. De seed is telkens het order met het kleinste volgnummer. Vervolgens worden op basis van het volgnummer (kleinste volgnummer krijgt prioriteit) orders aan de batch toegevoegd zolang de capaciteit dit toelaat. 7.1.3.1.2
SNPA - SNAPA
In Ho en Tseng (2006) is te lezen dat de combinatie van SNA (smallest number of picking aisles) als seed selection rule en SNAPA (smallest number of additional picking aisles) als order addition rule zeer sterk presteerde, en dit vooral in combinatie met de S-shape routering. Om die reden zal deze heuristiek ook in de experimenten gebruikt worden. De heuristiek kan echter niet zonder meer
45
overgenomen worden, aangezien deze ontworpen is voor magazijnen uit één blok. Om deze heuristiek te kunnen toepassen op meerdere blokken stellen we 2 varianten voor, waarbij het onderscheid gebaseerd is op het verschil tussen een sub- en langsgang. Het verschil tussen een subgang en een langsgang is weergegeven in bijlage 1. A. SNSA – SNASA (smallest number of sub-aisles – smallest number of additional sub-aisles) In de eerste variant selecteert men als seed het order dat het minste aantal subgangen met te pikken items bevat. Daarna voegt men orders toe opdat zo min mogelijk extra subgangen met te pikken items in de batch terechtkomen. B. SNA – SNAA (smallest number of aisles – smallest number of additional aisles) In de tweede variant selecteert men als seed het order dat het minste aantal langsgangen met te pikken items bevat. Daarna voegt men orders toe opdat zo min mogelijk extra langsgangen met te pikken items in de batch terechtkomen. Merk op dat de twee varianten hetzelfde resultaat zullen geven in een magazijn uit één blok. Zij komen dan beide overeen met de SNPA – SNAPA heuristiek van Ho en Tseng (2006). 7.1.3.1.3
SNB – SNAB (smallest number of blocks – smallest number of additional blocks)
Aangezien de algoritmes worden gesimuleerd in een magazijn bestaande uit meerdere blokken wordt er ook een nieuwe selection rule getest, gebaseerd op het aantal blokken met te pikken items dat een order bevat. Als seed zal het order gekozen worden dat het minste aantal blokken met te pikken items bevat. Vervolgens zal men een order toevoegen opdat zo min mogelijk extra blokken met te pikken items in de batch terechtkomen. 7.1.3.2 Savings algoritme (CW) De koster et al. (1999) merken op dat een variant (CW(ii)) van het savings algoritme van Clarke en Wright (1964) zeer goed presteert. Dit algoritme zal dan ook volledig conform De koster et al. (1999) geprogrammeerd worden. Daarnaast wordt ook een andere variant uit dezelfde paper, namelijk CW (iii) in beschouwing genomen. In deze laatste variant kan de vaste kost van een batch in rekening worden gebracht. CW (iii) is in feite identiek aan CW(ii) wanneer de vaste kost op 0 wordt gezet. We zullen deze twee algoritmes dus gelijkstellen aan elkaar en simpelweg CW noemen. Bij elk experiment zal aangeven worden hoeveel de vaste kost bedraagt. De exacte procedure voor de CW heuristiek is beschreven in bijlage 5.
46
7.1.3.3 Gready heuristieken We stellen vier procedures voor, gebaseerd op de Gready heuristieken voor het TSP of VRP. In elke iteratie wordt de goedkoopste combinatie order/bestaande batch of order/nieuwe batch gekozen. Indien ordersplitsing is toegelaten zal men niet over orders maar over individuele items spreken. In deze procedures kan de vaste kost voor het opstarten van een nieuwe batch worden geïncorporeerd. We zullen bij elk experiment aangeven hoeveel deze vaste kost bedraagt. A. Ordersplitsing is niet toegelaten (G1 / G2) De procedure voor G1 en G2 is beschreven in figuur 7.3 . Stap 1:
G1:
Selecteer uit alle orders die nog niet toegewezen zijn aan een batch het
order O met G2:
het laagste volgnummer. Ga naar stap 2.
Beschouw alle orders die nog niet toegewezen zijn aan een batch en alle
bestaande batches. Ga naar stap 2. Stap 2:
G1:
Voeg O virtueel toe aan alle bestaande batches waarbij de capaciteit dit
toelaat. Creëer daarnaast ook een virtuele nieuwe batch enkel bestaande uit O. De samenvoeging moet gebeuren conform de geldende samenvoegingprocedure. Ga naar stap 3. G2:
Creëer een virtuele batch voor elke combinatie van een bestaande batch en
een order, de capaciteitsrestricties in acht genomen. Creëer daarnaast ook een virtuele nieuwe batch voor elk van deze orders. De samenvoeging moet telkens gebeuren conform de samenvoegingprocedure. Ga naar stap 3. Stap 3:
Bereken voor elk van deze virtuele batches de kost dat dit zou opleveren gegeven het routeringalgoritme. Ga naar stap 4.
Stap 4:
Kies de virtuele batch B*, samengesteld uit een bestaande of nieuwe batch b* en een order o*, die het minste extra kosten zou opleveren. De kost voor het opstarten van een nieuwe batch kan hier in rekening worden gebracht. Ga naar stap 5.
Stap 5:
Voeg o* toe aan b* volgens de samenvoegingprocedure. Ga naar stap 6.
Stap 6:
Stop indien alle orders toegewezen zijn aan een batch. Indien niet ga naar stap 1.
Figuur 7.3 Procedure voor G1 en G2
47
Het is duidelijk dat G1 meer rekentijd zal vergen dan G2 aangezien in stap 3 minder afstanden moeten berekend worden. B. Ordersplitsing is toegelaten (G3 / G4) Indien ordersplitsing is toegelaten worden de items ‘uit’ de orders gehaald en zullen we de items batchen in plaats van de orders. In de beschrijving voor de procedure voor G1 en G2 (figuur 7.3) kunnen we dus gewoon ‘orders’ vervangen door ‘items’. G3 volgt vervolgens de stappen van G1, G4 die van G2. Omdat het aantal gevormde batches bij G3 en G4 theoretisch zeer hoog kan zijn, namelijk gelijk aan het totaal aantal te pikken items (terwijl dit bij G1 en G2 gelijk was aan het totaal aantal orders), zou in stap 2 de clausule kunnen opgenomen worden dat geen nieuwe virtuele batch mag worden gecreëerd indien een maximaal aantal batches is bereikt. In deze masterproef zal niet bepaald worden wat de optimale waarde voor dit maximum aantal batches is. In de experimenten wordt het maximum aantal batches formeel gelijkgesteld aan het aantal te batchen orders. 7.1.4
Verbeteringsalgoritmen
De verbeteringsalgoritmen zullen worden toegepast op de samenstelling van de batches en de pikvolgorde binnen deze batches, verkregen na toepassing van het batchingalgoritme. Deze verbeteringsalgoritmen zullen slechts toevallig een globaal optimum kunnen vinden. Zij kunnen moeilijk een globaal optimum vinden omdat het aantal batches tijdens het verbeteren niet meer zal wijzigen. Enkel de inhoud van de bestaande batches (en de pikvolgorde) zal worden gewijzigd. De oplossingenruimte waarin het algoritme zal kunnen werken is dus gelimiteerd. Door middel van het toepassen van deze verbeteringsalgoritmen wordt dus vooral een lokaal optimum nagestreefd. Het swap items algoritme (SI) kent een sterke gelijkenis met het routeverbeteringsalgoritme van Makris en Giakoumakis (2003) (zie 6.1.3.1). Het swap orders algoritme (SO) lijkt dan weer op het 2-opt algoritme uit Gademann et al. (2001) (zie 6.2.2). Zowel SI als SO zijn gebaseerd op de k-opt methodologie van Lin en Kernighan (1973). 7.1.4.1 Swap items (SI) Wanneer de orders worden gepikt volgens KP kunnen we een methode voorstellen, gebaseerd op de 2-opt methodologie, die de oplossing lokaal kan verbeteren. De procedure voor SI staat beschreven in figuur 7.4
48
Gegeven de huidige pikvolgorde Vh en de overeenkomstige afstand Ah volgens KP, doorloopt men volgende procedure. Stap 1: Selecteer twee plaatsen (i en j) uit Vh; i en j worden geselecteerd volgens een welbepaalde procedure. Ga naar stap 2. Stap 2: Construeer een virtuele pikvolgorde Vv = Vh . Verwissel vervolgens het item op plaats i uit Vv met het item op plaats j uit Vv. Ga naar stap 3. Stap 3: Bereken de virtuele afstand Av gekoppeld aan Vv volgens KP. Ga naar stap 4. Stap 4: Als Av < Ah: Stel Vh = Vv en Ah = Av. Ga naar stap 5. Stap 5: Stop indien de stopconditie is bereikt, anders ga naar stap 1. De stopconditie is vooraf bepaald. Figuur 7.4 Procedure voor SI Deze methode is in feite een 2-opt verbeteringsheuristiek die veel gebruikt wordt in het TSP of VRP. Meestal worden de plaatsen uit stap 1 ad random gekozen en wordt de procedure n aantal keer herhaald. Wanneer wij de swap items methode zullen gebruiken zullen wij daarentegen alle mogelijke combinaties van twee plaatsen (of 2 maal indien men (1,2) en (2,1) als dezelfde combinatie beschouwd) in beschouwing nemen volgens een vast patroon. We illustreren dit met een voorbeeld voor een batch met vier items. De plaatsen die achtereenvolgens door het algoritme geselecteerd zullen worden zijn: (1,2) (1,3) (1,4) (2,1) (2,3) (2,4) (3,1) (3,2) (3,4) (4,1) (4,2) (4,3) In het algemeen zullen we dus voor een batch met n items n.(n-1) iteraties uitvoeren. 7.1.4.2 Swap orders (SO) In deze lokale verbeteringsmethode wordt door het wisselen van twee orders tussen de batches gepoogd een betere oplossing te verkrijgen. Dit verbeteringsalgoritme kan enkel toegepast worden op de methodes zonder ordersplitsing. Dit is omdat telkens volledige orders worden verwisseld. De procedure voor SO vindt men in figuur 7.5 .
49
Stap 1: Selecteer twee batches Bhi en Bhj met bijhorende reisafstanden Ahi en Ahj, de reisafstanden zijn berekend conform de routeringprocedure. De batches worden geselecteerd op basis van een vooraf vastgelegde procedure. Ga naar stap 2. Stap 2: Selecteer een order k uit Bhi en een order m uit Bhj; k en m worden bepaald op basis van een vooraf vastgelegde procedure. Ga naar stap 3. Stap 3: Indien de orders niet kunnen gewisseld worden rekening houdend met de capaciteitsrestrictie ga naar stap 7, anders ga naar stap 4. Stap 4: Stel Bvi = Bhi. Construeer de virtuele batch Bvi door eerst k te verwijderen uit Bvi en vervolgens, conform de samenvoegingprocedure, m toe te voegen aan Bvi. Stel Bvj = Bhj. Construeer de virtuele batch Bvj door eerst m te verwijderen uit Bvj en vervolgens, conform de samenvoegingprocedure, k toe te voegen aan Bvj. Ga naar stap 5. Stap 5: Bereken de reisafstanden Avi voor Bvi en Avj voor Bvj, conform de routeringprocedure. Ga naar stap 6. Stap 6: Indien Avi + Avj < Ahi + Ahj, stel Ahi = Avi, Ahj = Avj, = Bvi en = Bvj. Ga naar stap 7. Stap 7: Ga naar stap 8 indien stopconditie 1 bereikt is, anders ga naar stap 2. Stap 8: Stop indien stopconditie 2 bereikt is, anders ga naar stap 1. Stopconditie 1 en 2 zijn vooraf bepaald. Figuur 7.5 Procedure voor SO De stopcondities en procedures voor het selecteren van de batches en orders worden in de experimenten als volgt bepaald. De batches in stap 1 worden op de volgende wijze geselecteerd: Wanneer n batches gevormd zijn wordt stap 1 n.(n-1) keer uitgevoerd. De selectie van de batches in stap 1 gebeurd niet ad random maar volgens een vooraf gedefinieerd patroon: Stel Bi gelijk aan de batch met volgnummer i dan worden in een voorbeeld met vier batches achtereenvolgens volgende batches geselecteerd: (B1, B2) (B1, B3) (B1, B4) (B2, B1) (B2, B3) (B2, B4) (B3, B1) (B3, B2) (B3, B4) (B4, B1) (B4, B2) (B4, B3)
50
Per combinatie van 2 batches i en j wordt stap 2 tot 7 vervolgens k.m keer uitgevoerd waarbij k het aantal orders is in batch i en m het aantal orders in batch j. Dit gebeurt volgens het gekende patroon: Stel Oia gelijk aan het order met volgnummer a in batch i en
Oja gelijk aan het order met
volgnummer a in batch i dan worden in een voorbeeld met k = 2 en m = 3 achtereenvolgens volgende orders geselecteerd: (Oi1, Oj1) (Oi1, Oj2) (Oi1, Oj3) (Oi2, Bj1) (Bi2, Bj2) (Bi2, Bj3) 7.1.5 De
Geïntegreerde methodes (GM)
geïntegreerde
methodes
bestaan
uit
vier
delen.
De
batchingprocedure,
de
samenvoegingprocedure, een of meerdere verbeteringsalgoritmen en de routeringprocedure. Elke GM is geprogrammeerd in twee versies: MX en MX+. MX+ is MX gecombineerd met een of meerdere verbeteringsalgoritmes. Ten slotte wordt in tabel 7.1 ook nog aangegeven of ordersplitsing is toegelaten of niet. De volgorde van de verbeteringsalgoritmen wijst op de volgorde waarin deze verbeteringsalgoritmen worden toegepast. Zo zal M1+ de oplossing van M1 verbeteren door eerst SI toe te passen, vervolgens SO en ten slotte opnieuw SI. Methode
Routering
Samenvoeging
Batching
Verbeteringsalgoritme
Ordersplitsing
M1 (+)
KP
INS
GR1
+: SI, SO, SI
Nee
M2 (+)
KP
INS
GR2
+: SI, SO, SI
Nee
M3 (+)
KP
INS
GR3
+: SI
Ja
M4 (+)
KP
INS
GR4
+: SI
Ja
M5 (+)
KP
INS
CW
+: SI, SO, SI
Nee
M6 (+)
S-shape
S1
GR2
+: SO
Nee
M7 (+)
S-shape
S1
CW
+: SO
Nee
M8 (+)
S-shape
S1
FCFS
+: SO
Nee
M9 (+)
S-shape
S1
SNSA-SNASA
+: SO
Nee
M10 (+)
S-shape
S1
SNA-SNAA
+: SO
Nee
M11 (+)
S-shape
S1
SNB - SNAB
+: SO
Nee
Tabel 7.1 Overzicht van de geïntegreerde methodes
51
7.2 Algemene assumpties en lay-out van het magazijn De volgende assumpties gelden voor alle experimenten:
Het aantal en het type van items in elk order wordt ad random volgens een uniforme verdeling bepaald tussen een minimum- en een maximumwaarde. Er is gekozen voor een random storage strategie waarbij elk type item daarenboven terug te vinden is op één specifieke opslaglocatie. Voor de eenvoud komt het nummer van het item overeen met het nummer van de opslaglocatie in het magazijn. Deze laatste assumptie is eigenlijk geen restrictie maar dit zorgt voor minder werk bij het programmeren. In feite kan men de orderlijst dus ook interpreteren als een lijst van te bezoeken opslaglocaties.
Het aantal orders en de samenstelling van de orders (= de orderlijst) ligt vast voordat de geïntegreerde methodes worden toegepast.
Elke opslaglocatie bevat slechts één type item. De capaciteit (bijvoorbeeld uitgedrukt in volume of gewicht) dat een item in beslag neemt kan per item verschillen en wordt ad random bepaald tussen een minimum- en een maximumwaarde (uniforme verdeling).
Omdat voor de meeste methodes ordersplitsing niet is toegelaten moet de capaciteit van de pikker voldoende groot zijn (of elk order voldoende klein) zodat elk order apart volledig kan gepikt worden.
De depot bevindt zich linksonder in het magazijn en komt overeen met de kruising van de eerste dwarsgang en de eerste langsgang. Een route start en eindigt steeds bij de depot. Een voorbeeld van het type magazijn dat wordt gebruikt tijdens de experimenten vindt men in bijlage 1.
De hoogte van de opslaglocatie speelt geen rol voor het bepalen van de reisafstand. We beschouwen dus een tweedimensionaal magazijn.
De langsgangen worden beschouwd als smal (< 3,7m) (zie 6.1.4), de pikker zal beide kanten van de langsgang kunnen pikken vanaf het midden van de langsgang. De afstand van het midden van de langsgang tot de eigenlijke piklocatie, zoals gebruikelijk is in dit type van simulaties, wordt dus verwaarloosd.
De lay-out van het rechthoekig magazijn zal een grote invloed hebben op de resultaten (zie 6.2.6). We zullen in deze studie het aantal dwarsgangen en langsgangen variëren, maar om de experimenten werkbaar te houden en de resultaten interpreteerbaar moeten keuzes gemaakt worden over de waarden van enkele lay-out parameters (tabel 7.2). Belangrijk is de verhouding tussen de breedte van de dwarsgang en de afstand tussen opeenvolgende langsgangen (breedte langsgang + diepte opslaglocaties). Om een betere vergelijkbaarheid te garanderen tussen verschillende experimenten kunnen deze waarden bepaald worden op basis van gelijkaardige 52
studies. Aangezien er echter nog geen studies zijn over batchingheuristieken in meerdere (>2) blokken zullen we de waarde van deze lay-out parameters overnemen uit Theys en Herroelen (2005), die routeringalgoritmen in meerdere blokken bestuderen. De vaste parameters in verband met de orderlijst kunnen niet overgenomen worden uit They en Herroelen (2005) omdat in hun experimenten van batchen geen sprake is. Parameters die de aard van de items en de samenstelling van de orders beschrijven zijn daarom bepaald volgens De Koster et al. (1999) en Ho en Tseng (2006). Breedte langsgang
2
Min. Aantal items per order
2
Breedte dwarsgang
3
Max. aantal tems per order
10
Breedte opslaglocatie
1
Min. volume/item
1
Diepte opslaglocatie
2
Max. volume/item
3
aantal opslaglocaties
1200
Aantal orders
60
Tabel 7.2 Vaste parameters experimenten 7.3 Aantal herhalingen Per simulatie of herhaling zal door het programma een magazijn en een orderlijst gecreëerd worden op basis van de vaste parameters in de tabel en de assumpties beschreven in 7.2. Voor het bepalen van het aantal simulaties per combinatie is de werkwijze van Theys en Herroelen (2005) gevolgd. De experimenten zijn eerst uitgevoerd met 100 herhalingen per testconfiguratie. Voor elke testconfiguratie wordt vervolgens de halve breedte van het 95% betrouwbaarheidsinterval berekend op basis van volgende formule: s = steekproefstandaardafwijking en n = aantal herhalingen. 𝑎𝑙𝑣𝑒 𝑏𝑟𝑒𝑒𝑑𝑡𝑒 = 𝑡𝑛−1,1−𝛼 2
𝑠 𝑛
Vervolgens wordt voor elke combinatie de verhouding van de halve breedte van het 95% betrouwbaarheidsinterval tot het gemiddelde berekend. Theys en Herroelen (2005) argumenteren dat een waarde voor deze ratio van minder dan 5% voldoende is. Deze werkwijze wordt gevolgd voor elk van de 3 experimenten en dit voor zowel de reisafstanden als de benuttinggraden. Andere specifieke prestatiemaatstaven voor experiment 2 en 3 worden ook op dezelfde manier getest. Na analyse van de bekomen ratios (zie bijlage 6 / CD-ROM) zien we dat 100 herhalingen voldoende blijken voor elk van de drie experimenten en dit zowel voor de reisafstanden als de benuttinggraden.
53
7.4 Definitie reisafstand en benuttinggraad
7.4.1
Reisafstand
De reisafstand in de experimenten is de som van de reisafstanden van de individuele batches die gevormd zijn. De reisafstand van een individuele batch is de afstand die de pikker moet afleggen om de items van de batch te verzamelen volgens een bepaalde routeringheuristiek (en gegeven pikvolgorde) bepaald door de geïntegreerde methode. Bij de bespreking van de resultaten zullen we nooit de reisafstand van een individuele batch analyseren. Wanneer we spreken over de reisafstand of de gemiddelde reisafstand zal het dus altijd gaan over de totale reisafstand of de gemiddelde totale reisafstand. 7.4.2
Benuttinggraad
Benuttinggraad =
1 𝑛
𝑛 𝑔𝑒𝑏𝑟𝑢𝑖𝑘𝑡𝑒 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑒𝑖𝑡 𝑖𝑛 𝑏𝑎𝑡𝑐 𝑖 𝑖=1 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑒𝑖𝑡 𝑣𝑎𝑛 𝑑𝑒 𝑝𝑖𝑘𝑘𝑒𝑟
. 100%, met n = aantal gevormde batches.
Aangezien in de experimenten voor elke batch dezelfde capaciteit beschikbaar is en alle orders van de orderlijst worden gebatched , is de benuttinggraad ook gelijk aan: 𝑘 𝑖=1 𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑒𝑖𝑡𝑠𝑏𝑒
𝑜𝑒𝑓𝑡𝑒 𝑣𝑎𝑛 𝑜𝑟𝑑𝑒𝑟 𝑖
𝑛 .𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑒𝑖𝑡 𝑣𝑎𝑛 𝑑𝑒 𝑝𝑖𝑘𝑘𝑒𝑟
. 100% ,met k = aantal orders in de orderlijst en n = aantal
gevormde batches. Uit deze laatste vergelijking blijkt dat de benuttinggraad enkel afhankelijk is van het aantal gevormde batches, want de capaciteit van de pikker en het aantal orders (en de samenstelling van een order) is immers gegeven. Een algoritme zal dus beter scoren op deze prestatiemaatstaf wanneer zij het aantal gevormde batches kan beperken. Merk op dat wanneer 𝑘 𝑖=1 (𝑐𝑎𝑝𝑎𝑐𝑖𝑡𝑒𝑖𝑡𝑠𝑏𝑒𝑜𝑒𝑓𝑡𝑒
𝑣𝑎𝑛 𝑜𝑟𝑑𝑒𝑟 𝑖 ) geen veelvoud zal zijn van de capaciteit, het sowieso
onmogelijk zal zijn om een benuttinggraad van 100% te bekomen. Aangezien de totale capaciteitsbehoefte kan verschillen per gesimuleerde orderlijst is het zeker aan te raden bij de analyse gebruik te maken van een ‘within-subject’ design (zie 7.6.4.1). 7.5 Programmeercode De algoritmes werden geprogrammeerd in C++ met behulp van Microsoft Visual Studio 2005. Het schrijven van een simulatieprogramma was geen doel op zich maar een middel om de simulaties te kunnen uitvoeren. Alhoewel bepaalde delen van de code zeker efficiënter kunnen worden geprogrammeerd, is dit zeker niet van invloed op de resultaten. Een efficiëntere code zou wel kunnen leiden tot een kortere rekentijd. Aangezien de rekentijd nu minder dan één seconde bedroeg voor het uitvoeren van één methode, werd de rekentijd echter niet als een restrictie ervaren. Voor de exacte programmeercode wordt verwezen naar bijlage 6 / CD-ROM. 54
7.6 Experiment 1
7.6.1
Onderzoeksvragen
Er worden vier specifieke onderzoeksvragen onderscheiden voor dit experiment: 1) Hoe presteren de verschillende algoritmes op vlak van reisafstand en benuttinggraad? 2) Is het aan te raden om een verbeteringsalgoritme te integreren in de algoritmes? Met andere woorden: is er een significant verschil tussen de prestaties op vlak van reisafstand met en zonder verbeteringsalgoritme? 3) Heeft de lay-out van het magazijn een invloed op de prestaties van de algoritmes? 4) Heeft de capaciteit van de pikker een invloed op de prestaties van de algoritmes?
7.6.2
Onafhankelijke variabelen
Net zoals in Roodbergen en De Koster (2001a) en Theys en Herroelen (2005) zullen het aantal opslaglocaties constant gehouden worden wanneer het aantal dwarsgangen of langsgangen wijzigt. Aangezien het aantal subgangen zal wijzigen, zal het aantal opslaglocaties per subgang dus afhankelijk zijn van het aantal langsgangen en dwarsgangen. In tabel 7.3 staan de variabele parameters beschreven. Aantal langsgangen
5, 10 en 15
Aantal dwarsgangen
2, 3, 5 en 6
Capaciteit (volume) van de pikker
36, 60 en 84
Tabel 7.3 Variabele parameters experiment 1 De vaste kost van een batch wordt in dit experiment verwaarloosd en dus op 0 gezet in de algoritmes die deze kost in beschouwing kunnen nemen. We testen vervolgens alle methodes die geen ordersplitsing toelaten. Dit zijn de volgende 9 methodes, die eens met en zonder het voorgesteld verbeteringsalgoritme zullen worden uitgevoerd (in totaal dus 18 methodes) : M1(+),M2(+),M5(+),M6(+),M7(+),M8(+),M9(+),M10(+) en M11(+) Het totaal aantal configuraties in dit experiment is: 3 (langsgangen) x 4 blokken x 3 (capaciteit) = 36. Voor elk van deze configuraties zal nu 100 maal een fictief magazijn + orderlijst worden gesimuleerd. Vervolgens wordt elk van de 18 methodes onderworpen aan dezelfde orderlijst + magazijn. 55
Aangezien de methodes dus eenzelfde orderlijst zo optimaal mogelijk hebben proberen batchen verhoogt dit de betrouwbaarheid ten opzichte van een situatie waarbij men een verschillende orderlijst zou simuleren voor elke methode afzonderlijk Ellis (2006). 7.6.3
Afhankelijke variabelen
Per configuratie, per herhaling en per methode zal de benuttinggraad, totale reisafstand en het verschil met de best presterende heuristiek worden berekenend. Daarnaast zal voor elke verbeteringmethode (met +) worden weergegeven hoeveel deze de oplossing (zonder +) heeft verbeterd op vlak van reisafstand. 7.6.4
Resultaten
7.6.4.1 Statistische test Om de statistische significantie van de geobserveerde effecten te kunnen testen wordt een variantie-analyse toegepast en meerbepaald: Generalized Linear Model (GLM) – Repeated Measures. Uit 7.5.2 blijkt inderdaad dat meerdere metingen per ‘respondent’, een bepaalde herhaling binnen een configuratie, werden uitgevoerd. We zullen dus zowel ‘within subject’ als ‘between subject’ effecten bestuderen. De eerste effecten slaan op de verschillen in prestatie tussen de methodes per ‘respondent’. Het tweede effect handelt over de invloed van de lay-out of de capaciteit van de pikker en de interactie-effecten tussen het aantal blokken, langsgangen, capaciteit en de methodes. Normaalgezien moet men bij een within subject onderzoek opletten voor carryover of volgorde effecten. Deze zijn in ons onderzoek niet aanwezig aangezien het helemaal niet uitmaakt welke methode eerst wordt toegepast op de orderlijst en de resultaten objectief worden bekomen. In dit geval hebben we dus een 3x4x3 between subjects design en voor de within subjects design zullen we 1 factor definiëren op 18 niveaus: per methode een meting. De gangbare term voor deze analyse is: ‘repeated measures ANOVA with between-subject factors’. De analyse van de effecten en de voorwaarden zijn uitgevoerd via SPSS. Alle SPSS output bestanden zijn beschikbaar, er wordt hiervoor verwezen naar bijlage 6 / CD-ROM. Enkele voorwaarden moeten voldaan zijn voor het toepassen van een mix tussen een between subjects en de within subjects design geanalyseerd via ANOVA repeated measures : A. Hypothese van gelijke varianties (homoscedasticiteit) (Wijnen et al., 2002) De foutentermen moeten een constante variantie hebben. We kunnen een scatterplot opstellen waarin de residuen zijn uitgezet ten opzichte van de voorspelde waarden. Indien de punten 56
ongeveer even breed verspreid liggen, dan kan worden aangenomen dat de foutenterm niet afhankelijk is van de voorspelde waarden. De hypothese van gelijke varianties kan meer formeel worden getest via de Levene’s test. Zowel in het geval van de reisafstanden als de benuttinggraden verwerpt de Levene’s test de hypothese van gelijke varianties. Wanneer wij echter kijken naar de scatterplots zien wij een vormeloze puntenwolk en zijn de varianties zo even breed verspreid, we beschouwen deze voorwaarde dus als voldaan. B. Storingstermen zijn normaal verdeeld (Ellis, 2006) De storingstermen van de afhankelijke variabelen binnen elke groep moeten normaal verdeeld zijn. ANOVA (analysis of variance) is echter vrij robuust ten opzichte van de schendig van deze voorwaarde. De normaliteit kan getest worden aan de hand van een ‘normal Q-Q plot’, histogrammen en aan de hand van de toetsen Kolmogorov-Smirnov en Shapiro-Wilk. Wanneer de normaliteit wordt getest voor de reisafstanden en benuttinggraden via KolmogorovSmirnov en Shapiro-Wilk, wordt de hypothese van normaliteit soms verworpen en soms aanvaard naargelang de groep. De Q-Q plots en histogrammen van de residuen wijzen echter allemaal op normaliteit voor deze groepen. C. Onafhankelijkheid van de storingstermen (Wijnen et al., 2002) De ene observatie mag de andere niet beïnvloeden. In dit experiment is dit zeker niet het geval. D. Sphericiteit (Ellis, 2006; Wijnen et al., 2002) De sphericiteitvoorwaarde houdt in dat de populatievariantie van de verschillen tussen de reisafstanden/benuttinggraden van elk van de twee niveaus van een within subject-factor dezelfde is, onafhankelijk van welke twee niveaus men kiest. Wanneer aan deze assumptie is voldaan, kan men de krachtige univariate toets toepassen. Wanneer deze sphericity-asumptie is geschonden moet worden gekeken naar gecorrigeerde univariate toetsen zoals Greenhouse-Geisser, Huynh-Feldt en Lower bound. Een andere mogelijkheid is het volgen van de multivariate benadering. De assumptie van sphericiteit wordt getest via de Mauchly’s Test of Sphericity. Op basis van de Mauchly’s test of sphericity verwerpen we de sphericiteit zowel in het geval van de reisafstanden als van de benuttinggraden. We zullen dus kijken naar de gecorrigeerde univariate toetsen of naar de multivariate benadering. Het zal blijken dat beide voor de uitgevoerde experimenten dezelfde resultaten zullen geven. 57
E. Gebalanceerde opzet (Wijnen et al., 2002) Voor elk subject moet men voor elke experimentele conditie een observatie hebben. Indien dit niet het geval is moet men dit subject uit de analyse weren. In onze simulatie is deze voorwaarde vervuld voor alle 100 herhalingen per configuratie. 7.6.4.2 Bespreking resultaten De bespreking van de resultaten zal worden opgesplitst in twee delen. Eerst zullen de benuttingraden kort besproken worden omdat deze resultaten belangrijk zullen zijn om de verschillen in prestatie tussen methodes op vlak van reisafstand te kunnen interpreteren. Er worden zowel significante hoofdeffecten voor de within subject effecten (methodes) als voor de between subject effecten (het aantal blokken, gangen en capaciteit van de pikker) waargenomen. Ook zijn er significante interactie-effecten. De bespreking van de resultaten zal ingedeeld worden op basis van de onderzoeksvragen. De analyse zal beperkt worden tot de hoofdeffecten, de eerste orde interactie-effecten en één tweede orde interactie-effect (blokken*gangen*methodes) omdat deze effecten de meest relevante informatie opleveren met betrekking tot de onderzoeksvragen. 7.6.4.2.1
Benuttinggraden
De reisafstand wordt in dit experiment als de belangrijkste prestatiemaatstaf beschouwd. De waargenomen benuttinggraden kunnen echter nuttige informatie verschaffen over de werking van de algoritmes. Bij het verklaren van de verschillen in reisafstand tussen de algoritmen zal frequent verwezen worden naar de resultaten die in dit hoofdstuk besproken worden. Daarnaast kan ook de benuttinggraad op zich van belang zijn (zie 5.5 en 6.1). A. Beste methode We kunnen besluiten dat M8 methode gemiddeld genomen de beste methode is op vlak van benuttinggraad (tabel 7.4). Van de algoritmen die gebruik maken van KP scoort M1 het best. In de analyse zullen omwille van de overzichtelijkheid enkel de methoden worden weergegeven zonder verbeteringalgoritme, de equivalente methoden met verbeteringalgoritme hebben namelijk dezelfde benuttinggraad. Tussen methodes die een significant verschillend resultaat opleveren is een scheidingslijn getrokken.
58
Benuttinggraad (%) Plaats Methode 1 M8 2 M1 3 M11 4 M5 5 M10 6 M2 7 M9 M6 9 M7
Gemiddelde 92,83 92,32 91,47 91,00 89,06 88,40 87,96 87,91 83,81
Ondergrens 92,75 92,24 91,38 90,91 88,96 88,30 87,86 87,81 83,69
Bovengrens 92,91 92,40 91,55 91,10 89,15 88,50 88,06 88,01 83,93
Tabel 7.4 Betrouwbaarheidsintervallen voor de gemiddelde benuttinggraad Wanneer voor elke gesimuleerde orderlijst en magazijn wordt geëvalueerd welk algoritme het best scoort, tellen we 3448 overwinningen op 3600 (96%) voor M8. Vaak gebeurt het dat meerdere algoritmen even goed scoren, zo was ook M1 in 86% van de gevallen één van de beste algoritmen. B. Invloed van de lay-out Uit de resultaten blijkt dat de benuttinggraad daalt naarmate de complexiteit van de lay-out toeneemt (tabel 7.5). Een lay-out wordt als complexer beschouwd wanneer deze meer blokken of langsgangen telt. blokken 1 2 4 5 langsgangen 5 10 15 5 10 15 5 10 15 5 10 15 benuttinggraad 90,5 90,0 89,8 90,0 89,6 89,3 89,2 89,0 89,2 89,0 88,8 88,9 Tabel 7.5 Benuttinggraad in functie van de lay-out van het magazijn Deze daling doet zich echter niet bij alle algoritmen voor. Wanneer bijvoorbeeld M8 apart wordt bekeken dan zien we een vrij constante benuttinggraad. In tegenstelling tot bijvoorbeeld de methoden die gebruik maken van complexere seed algoritmen (M9, M10, M11) houdt M8 bij het batchen geen rekening met de lay-out van het magazijn. Het is dus normaal dat de benuttinggraad onafhankelijk is van de lay-out. Zoals op figuur 7.6 en figuur 7.7 duidelijk te zien is daalt de benuttinggraad bij de seed algoritmen naarmate het algoritme meer rekening houdt met de lay-out van het magazijn. Zo houden M9 (met seed algoritme SNSA-SNASA) als M10 (met seed algoritme SNA-SNAA) tijdens het batchen rekening met respectievelijk de subgangen en langsgangen die moeten bezocht worden bij het pikken van een bepaald order. Hoe meer subgangen er zijn (evenredig met het aantal langsgangen), hoe meer deze algoritmes kunnen discrimineren bij het selecteren van het orders maar hoe minder rekening zal gehouden worden met de benuttinggraad 59
(figuur 7.6). Een gelijkaardig fenomeen doet zich voor wanneer de benuttinggraad in functie van het aantal blokken wordt beschouwd (figuur 7.7). M11 (met seed algoritme SNB-SNAB) zal een lagere benuttinggraad vertonen naarmate het aantal blokken toeneemt. Ook M9 vertoont dit gedrag. Dit is logisch, aangezien ook het aantal subgangen (= aantal langsgangen x aantal blokken) in het magazijn stijgt bij een toenemend aantal blokken. Gemiddelde benuttinggraad in functie van het aantal langsgangen 93,00 92,00 91,00
M8
90,00
M9
89,00 88,00
M10
87,00
M11
86,00 5
10
15
Figuur 7.6 Gemiddelde benuttinggraad in functie van het aantal langsgangen (a) Gemiddelde benuttinggraad in functie van het aantal blokken 93,00 92,00 91,00
M8
90,00
M9
89,00 88,00
M10
87,00
M11
86,00 1
2
4
5
Figuur 7.7 Gemiddelde benuttinggraad in functie van het aantal blokken (a) Uit bovenstaande analyse blijkt dat het batchingalgoritme, als deel van de geïntegreerde methode, de benuttinggraad zal bepalen. We kunnen deze stelling ter controle eens toepassen op de overige methodes. Op figuren 7.8 en 7.9 is te zien dat de lay-out in het geval van GR1 als GR2, de batchingalgoritmes van M1 en M2/M6, niet veel invloed zal hebben op de benuttinggraad. Het batchingalgoritme CW zal echter meer beïnvloedbaar zijn door de lay-out van het magazijn. Vooral bij een stijgend aantal blokken (figuur 7.9) merken we een significante en relevante daling in de
60
benuttinggraad. De invloed van de lay-out verschilt dus opnieuw naargelang de aard van het batchingalgoritme. Gemiddelde benuttinggraad in functie van het aantal langsgangen 93,00 91,00
M1
89,00
M2
87,00
M5
85,00
M6
83,00
M7 5
10
15
Figuur 7.8 Gemiddelde benuttinggraad in functie van het aantal langsgangen (b) Gemiddelde benuttinggraad in functie van het aantal blokken 93,00 91,00 M1
89,00
M2
87,00
M5
85,00
M6
83,00
M7
81,00 1
2
4
5
Figuur 7.9 Gemiddelde benuttinggraad in functie van het aantal blokken (b) C. Invloed van de capaciteit Uit de resultaten blijkt dat de gemiddelde benuttinggraad stijgt bij een toenemende capaciteit van de pikker (tabel 7.6). Na analyse van de betrouwbaarheidsintervallen (zie bijlage 6 / CD-ROM) voor het interactie-effect methoden*capaciteit blijkt dit zo te zijn voor alle methodes met uitzondering van M1 en M8. Deze twee methodes kennen hun maximale benuttinggraad bij een capaciteit van 60 in plaats van 84. capaciteit benuttinggraad
36 86,85
60 90,54
84 90,86
Tabel 7.6 Benuttinggraad in functie van de capaciteit
61
De slechte benuttinggraad (bij alle algoritmen) bij een capaciteit van 36 kan als volgt verklaard worden. De maximale grootte van een order is maximaal 10 x 3 = 30 en gemiddeld 6 x 2 = 12. Theoretisch kan een batch dus gemiddeld uit 3 orders bestaan bij een capaciteit van 36, 5 orders bij een capaciteit van 60 en 7 orders bij een capaciteit van 84. De afwijking van de werkelijke ordergrootte ten opzichte van het gemiddelde zal echter een grotere rol spelen wanneer de capaciteit klein is. Wanneer bij een capaciteit van 36 reeds twee middelgrote orders (vb. 15 en 16 = 32) zich in de batch bevinden (de meeste algoritmen houden namelijk weinig rekening met de capaciteitsbezetting maar wijzen de orders aan de batches toe op basis van een andere maatstaf) kan enkel een zeer klein order (vb. 3) nog zorgen voor een goede benuttinggraad. Wanneer de capaciteit echter groter is kunnen deze twee middelgrote orders nog gecompenseerd worden door twee kleinere orders (vb. 15, 16, 9, 10 en 12 = 60) en kan gewacht worden met het opstarten van een nieuwe batch. Een grotere capaciteit houdt dus een grotere kans in tot een betere bezetting. 7.6.4.2.2
Reisafstanden
A. Beste methode In de eerste plaats wordt het significant within subjects hoofdeffect bestudeerd. De aanwezigheid van een dit significant hoofdeffect betekent dat minstens één van de methodes een significant verschillend resultaat geeft dan een andere methode. Dit kan onderzocht worden door de 95% betrouwbaarheidsintervallen te vergelijken per methode. Wanneer er geen overlap is tussen twee intervallen dan zijn de gemiddelde reisafstanden significant verschillend. Op die manier kunnen de methodes geordend worden op basis van de geschatte gemiddelde reisafstand. In tabel 7.7 zijn de methodes gerangschikt van beste naar slechtste reisafstand. Wanneer de methode significant verschillend is van de vorige of de volgende methode in de rangschikking dan werd er een scheidingslijn getrokken.
62
Gemiddelde reisafstand Plaats Methode Gemiddelde 1 M5+ 6114 2 M5 6188 3 M1+ 6526 4 M2+ 6618 M2 5 6919 6 M1 7471 7 M8+ 7769 8 M11+ 7830 M6+ 7832 10 M10+ 7879 M9+ 7893 M7+ 7895 13 M6 8177 M9 14 8363 15 M10 8568 16 M7 8650 17 M11 8959 M8 18 9036
Ondergrens 6099 6174 6512 6603 6902 7455 7752 7813 7813 7861 7874 7876 8156 8343 8548 8629 8940 9017
Bovengrens 6128 6203 6540 6634 6936 7487 7786 7847 7851 7898 7913 7914 8197 8384 8589 8670 8979 9055
Tabel 7.7 Betrouwbaarheidsintervallen voor de gemiddelde reisafstand Gemiddelde reisafstand per methode 9000 8500 8000 7500 7000 6500
M1 M1+ M2 M2+ M5 M5+ M6 M6+ M7 M7+ M8 M8+ M9 M9+ M10 M10+ M11 M11+
6000
Figuur 7.10 Gemiddelde reisafstand per methode Ten eerste is het duidelijk dat M5+ veruit de beste methode is (tabel 7.7 en figuur 7.10). Wanneer we alle gevallen apart bekijken (3600) vinden we dat in 97% van de gevallen (3498 gevallen) M5+ als de beste of gedeeld beste methode naar voor komt (bijlage 6 / CD-ROM). In tabel 7.8 is weergegeven wat de gemiddelde procentuele afwijking was van elke methode ten opzichte van de beste methode voor hetzelfde magazijn en dezelfde orderlijst.
63
methode afstand tot beste (%) methode afstand tot beste (%)
M1 18,50 M7+ 22,58
M1+ M2 M2+ M5 M5+ M6 6,69 11,40 7,53 1,32 0,03 24,81 M8 M8+ M9 M9+ M10 M10+ 32,43 21,55 26,42 22,25 28,35 22,25
M6+ 21,65 M11 31,77
M7 29,46 M11+ 22,12
Tabel 7.8 Gemiddelde procentuele afwijking ten opzichte van de kortste reisafstand Het moge duidelijk zijn dat een toepassing van M5+ ten opzichte van een klassieke FCFS strategie gecombineerd met een S-shape routering (M8) significante en relevante winst (32,43%) in reisafstand oplevert. Ten tweede valt het op dat methoden die gebruik maken van KP allemaal significant beter scoren dan zij die gebruik maken van de S-shape routering. We zien ook dat KP aan te raden is in combinatie met CW, zelf zonder verbetering (M5), maar dat de combinatie CW en S-shape (M7) slecht scoort ten opzichte van andere batchingmethoden die worden getest in combinatie met de Sshape. Dit is overeenkomstig De Koster et al. (1999) (zie 6.2.4.3). Zij vonden ook dat de combinatie van een savings algoritme (zoals CW) en een S-shape routering niet altijd geslaagd is. Zij raden daarom het gebruik van een largest gap routering aan in combinatie met een savings algoritme. B. Invloed van de verbeteringsheuristiek Uit de statistische analyse via ANOVA repeated measures kunnen we ten eerste besluiten dat de methodes zonder verbeteringsheuristiek allemaal significant slechter scoren dan hun equivalent met verbeteringsheuristiek. In tabel 7.9 is weergegeven wat de gemiddelde procentuele afwijking was van de methode zonder verbeteringsheuristiek ten opzichte van deze met, voor eenzelfde orderlijst en magazijn. Zo scoort M1+ gemiddeld 12,7% beter dan M1. In de tabel staat de gemiddelde verbetering over alle configuraties en herhalingen. Na uitsplitsing per configuratie bleek namelijk dat de configuratie geen relevante invloed heeft op de verbeteringsmogelijkheden per methode. Tabel 7.9 is dus representatief voor alle geteste configuraties. methode verbetering (%)
M1+ M2+ 12,7 4,2
M5+ 1,3
M6+ 4,0
M7+ 8,9
M8+ 13,9
M9+ 5,4
M10+ M11+ 8,0 12,4
Tabel 7.9 Gemiddelde procentuele winst in reisafstand door toepassing van het verbeteringsalgoritme Ten tweede is de sterke verbetering van M1+, M8+ en M11+ opvallend. Waar M8 als slechtste heuristiek naar voren komt, bezet M8+ de zevende plaats en is deze uiteindelijk de beste methode in combinatie met de S-shape routering. M1+ laat M2+ achter zich, ook al scoorde M1 slechter dan M2. Het is geen toeval dat de hoge benuttingraad van M1, M8 en M11 (zie 7.6.4.2.1) er voor zorgt dat er meer potentieel is tot verbetering ten opzichte van methodes die initieel meer aandacht schenken 64
aan het construeren van een ideale route, ten nadele van het minimaliseren van het aantal batches. De route in de eerste methodes zal dus initieel niet zo goed zijn maar mits een goede herschikking van de orders in de batches en de volgorde van de items in de routes, kunnen deze methodes toch nog een goede prestatie neerzetten. We zien hier duidelijk de gelijkenis met het onderzoek van De Koster et al. (1999) (zie 6.2.4.3) waarin werd besloten dat het minimaliseren van het aantal batches niet tot optimale reisafstanden zal leiden. Dit is in ons onderzoek ook zo wanneer we bijvoorbeeld M1 en M8 beschouwen. Deze methodes scoren slechter dan verwante methodes (resp. M2 en M11) die meer aandacht schenken aan het minimaliseren van de reisafstand. Echter, in De Koster et al. (1999) werden na de initiële constructie van de batches geen verbeteringsalgoritme toegepast. Wij zien dat wanneer de methode een zeer goede benuttinggraad heeft, zij achteraf door een verbeteringsalgoritme ook zeer sterk kan scoren op vlak van reisafstand. We kunnen hieruit besluiten dat het belangrijk is om een algoritme te ontwikkelen dat initieel rekening houdt met zowel de benuttingraad als met de reisafstand. In dit verband kan M5 als voorbeeld genomen worden, deze methode scoort zowel goed op benuttingraad (minder dan M1, maar meer dan M2) en op reisafstand. Vaak besluit men dat FCFS veel slechter scoort in combinatie met S-shape ten opzichte van meer complexe batchingmethoden. Op het eerste zicht lijkt dit ook zo, maar na het toepassen van een verbeteringsalgoritme scoort deze methode echter even goed of beter dan het complexe algoritme. We kunnen in deze context als voorbeeld Ho en Tseng (2006) nemen (zie 6.2.4.2). Zij besluiten dat de combinatie SNA-SNAPA en S-shape (M10) veel beter scoort dan FCFS en S-shape (M8). Inderdaad, M8 scoort slechter dan M10, maar M8+ scoort gemiddeld beter dan M10+. Wanneer we het verschil enkel in 1 blok bekijken (zoals in Ho en Tseng, 2006) dan zien we ook dat M8+ niet significant verschilt van M10 voor 1 blok / 10 lansgangen, significant beter scoort voor 1 blok / 15 langsgangen en significant slechter voor 1 blok / 5 langsgangen. De resultaten bekomen via experiment 1 zijn dus een nuttige aanvulling op de bestaande literatuur. C. Invloed van de lay-out Volgens de statistische test is er een hoofdeffect wat betreft het aantal gangen en blokken en zijn er daarnaast nog één of meerdere significante 1e orde interactie-effecten (blokken * gangen, blokken * methodes, gangen * methodes). Ook het 2e orde interactie-effect blokken * gangen * methodes zal besproken worden. Figuur 7.11 geeft het interactie-effect blokken * gangen weer. De grafiek toont dat de combinatie van 4 blokken met 10 langsgangen gemiddeld de beste reisafstand zal opleveren. Deze resultaten
65
bevestigen de conclusies van o.m. Roodbergen en De Koster (2001a): het toevoegen van extra dwarsgangen aan een magazijn uit één blok levert significante voordelen in reisafstand op. In ons onderzoek is het inderdaad ook zo dat de reisafstand sterk daalt wanneer we een magazijn uit 2 blokken vergelijken met een magazijn uit één blok. Ook de overgang van 2 blokken naar 4 blokken levert nog een significante winst op. Gemiddelde reisafstand in functie van de lay-out van het magazijn 9500 9000 8500 8000 7500 7000 6500 6000 5
10 1
15
5
10 2
15
5
10 4
15
5
10
15
5
Figuur 7.11 Gemiddelde reisafstand in functie van de lay-out van het magazijn De analyse van het effect blok * methodes en gangen * methodes levert ook interessante resultaten op. Figuur 7.12 toont per methode, per blok wat de gemiddelde reisafstand was, figuur 7.13 doet hetzelfde voor het aantal langsgangen. In de figuren zijn enkel de relevante methodes weergegeven. Op voorhand dachten we dat M11, dat het aantal gemeenschappelijke blokken tussen een order en een batch in beschouwing neemt tijdens het batchingproces door het algoritme SNB-SNAB, wel eens goed zou kunnen scoren naarmate het aantal blokken toeneemt. Deze methode scoort inderdaad relatief beter bij een groter aantal blokken. Waar M11 eerst nog even slecht scoorde als M8 (in één blok zijn M8 en M11 namelijk identiek), scoort zij bij 5 blokken al veel beter dan M8 en verkleint zelf de kloof met M9 en M10 (de andere methodes die gebruik maken van seed algoritmen). Opvallend is ook de slechte prestatie van M1 bij 1 blok. Waar M5+ bij 1 blok reeds afstand neemt van de rest, behoort M1 zelfs niet tot de top 6. Naarmate het aantal blokken toeneemt vergroot de kloof met de slechtere methodes. De slechte prestatie bij één blok is zeker niet te wijten aan het gebruik van KP als routering want bijvoorbeeld M1+, M2 en M5+ scoren wel goed maar louter aan het batchingalgoritme GR1 dat te weinig toegevoegde waarde brengt. Het verbeteringsalgoritme dat leidt tot M1+ (SI en SO) kan deze initiële slechte batching teniet doen (tabel 7.9 en figuur 7.12).
66
Gemiddelde reisafstand per methode in functie van het aantal blokken 9990 9490 8990
M1
8490
M1+
7990
M2 M5+
7490
M8 6990
M9
6490
M10
5990
M11
5490 1
2
4
5
Figuur 7.12 Gemiddelde reisafstand per methode in functie van het aantal blokken Bij een stijgend aantal langsgangen verwachten we vooral een sterke prestatie van M9 en M10. Deze methodes maken namelijk gebruik van respectievelijk SNSA-SNASA en SNA-SNAA, beide in combinatie met een S-shape routering. De achterliggende redenering is dat deze batchingmethodes het aantal te doorkruisen subgangen per batch minimaliseren. De S-shape routeringheuristiek stelt namelijk dat telkens (behalve in de laatste te bezoeken subgang van een blok) de volledige subgang moet doorkruist worden. Wanneer er meer langsgangen zijn stijgt, ceteris paribus, het aantal subgangen in het magazijn en kan het samennemen van orders met gelijke subgangen (SNASA) of langsgangen (SNAA) dus voordelig zijn. Het is wel zo dat dit positief effect zal gecompenseerd worden een door een kleiner aantal items per subgang, dit is te wijten aan de specifieke opzet van het experiment. Door het gelijk houden van het aantal opslaglocaties zal een stijgend aantal langsgangen leiden tot minder opslaglocaties per subgang. De lengte van een subgang wordt bepaald door het aantal opslaglocaties. Aangezien de subgang nu minder lang zal zijn zorgt dit er voor dat het niet meer zo tijdrovend is om een subgang volledig te doorkruisen. Dit is waarschijnlijk de reden dat het verschil tussen M9 en M10 en M8 niet groter wordt bij stijgend aantal langsgangen. Afgaande op de bekomen resultaten wordt zelfs het tegendeel vermoed. De lengte van de subgang is zo belangrijk bij 5 langsgangen dat het in dit geval cruciaal wordt om rekening te houden met het doorkruisen van een subgang. Dit verklaart waarschijnlijk de grote verschillen tussen de verschillende methodes bij 5 langsgangen. Een andere vaststelling is dat het beter is om M9 te
67
kiezen dan M10. Wanneer men de gekende SNAPA methode voor één blok wil uitbreiden naar meerdere blokken past men dus best SNASA toe. Gemiddelde reisafstand per methode in functie van het aantal langsgangen 9500
9000 M8 8500
M9 M10 M11
8000
7500 5
10
15
Figuur 7.13 Gemiddelde reisafstand per methode in functie van het aantal langsgangen We kunnen ten slotte vermelden dat voor alle combinaties gangen en blokken de top 5 van de beste methodes ongewijzigd blijft: M5+, M5, M1+, M2+, M2. D. Invloed van de capaciteit In dit onderdeel worden het hoofdeffect capaciteit en het interactie-effect capaciteit * methoden besproken. Deze effecten zijn significant, wat betekent dat de gemiddelde reisafstand verschilt naargelang de capaciteit en dat de relatieve prestaties van één of meerdere methodes verschilt naargelang de capaciteit van de pikker. Het hoofdeffect is makkelijk in te zien. Hoe groter de capaciteit van de pikker, hoe groter het positieve effect van batchen wordt (tabel 7.10). De pikker zal meer items kunnen pikken in één ronde en dus minder vaak de afstand naar de depot moeten afleggen. Daarnaast kunnen ook meer gelijkaardige orders in dezelfde batch worden opgenomen waardoor minder vaak naar dezelfde opslaglocatie moet gereisd worden of dezelfde subgang zal worden doorkruist. Zoals in tabel 7.10 te zien is kan men in absolute reisafstand zeer veel besparen bij het verhogen van de capaciteit van 36 naar 60. Relatief gezien is de besparing van 36 naar 60 ongeveer 30% en van 60 naar 84 ongeveer 20%. Dit fenomeen weerspiegelt de afnemende marginale opbrengsten van een extra eenheid capaciteit. De orders die eerst worden samengenomen in een batch bevinden zich waarschijnlijk (dit is toch de bedoeling van de voorgestelde algoritmen) het dichtst bij elkaar of hebben het meeste gemeenschappelijke
68
kenmerken. De winst door het samennemen van deze orders ten opzichte van het individueel pikken van deze orders is dus zeer groot. Nadien voegt men, indien de capaciteit dit toelaat, extra orders toe aan de batch. Deze nieuwe orders hebben echter minder gemeen met de andere orders in de batch, dus zal de marginale winst afnemen. capaciteit gemiddelde reisafstand
36 60 84 10194 7167 5753
Tabel 7.10 Gemiddelde reisafstand in functie van de capaciteit Evalueert men de relatieve verhoudingen tussen de algoritmen bij wisselende capaciteit dan vallen er geen belangrijke verschuivingen op. Algemeen gesproken blijft het verschil met de beste methode in de drie situaties ongeveer gelijk. Het is dus niet zo dat het beste algoritme bij een bepaald capaciteitsniveau meer voordeel zou opleveren. In absolute reisafstand is dit wel het geval (namelijk bij capaciteit 36) maar relatief gezien niet. Dit is weergegeven in tabel 7.11. Capaciteit 36 60 84 gemiddeld verschil in reisafstand met de beste methode (%) 19,47 19,91 19,13 Tabel 7.11 Gemiddelde procentuele afwijking ten opzichte van de beste reisafstand in functie van de capaciteit Wanneer de reisafstanden worden opgesplitst per methode bekomt men figuur 7.14. Op figuur 7.14 zijn enkel de methodes zonder verbeteringsalgoritme weergegeven en de beste methode (M5+). De grafiek toont dat de verhoudingen vrij goed gerespecteerd blijven. Na analyse van de betrouwbaarheidsintervallen (zie bijlage 6 / CD-ROM) valt wel op dat bij een capaciteit van 36, de methodes zo goed als allemaal significant verschillende reisafstanden produceren. Dit in tegenstelling tot een capaciteit van 60 of 84, waar de middelmatige algoritmen niet significant verschillende resultaten zullen opleveren. Daarnaast is ook de slechte prestatie van M6 en M2 ten opzichte van M5 en de relatief goede score van M7 bij een capaciteit van 36 opmerkelijk. De eerste twee methodes gebruiken GR2 als batchingalgoritme en de laatste twee gebruiken CW. We vermoeden dus dat als de capaciteit beperkt is, CW beter de orders zal batchen dan GR2. Uit al deze bevindingen kunnen we besluiten dat het bij een beperkte capaciteit (36) het extra belangrijk is om aandacht te schenken aan het kiezen van de gepaste methode.
69
gemiddelde reisafstand per methode per capaciteit 12000 11000 10000 9000
36
8000
60
7000
84
6000 5000 4000 M1
M2
M5
M5+
M6
M7
M8
M9
M10
M11
Figuur 7.14 Gemiddelde reisafstand per methode in functie van de capaciteit 7.7 Experiment 2
7.7.1
Onderzoeksvragen
Uit experiment 1 bleek dat een goede benuttinggraad significante voordelen kan opleveren voor de geïntegreerde methodes met een verbeteringsalgoritme. Daarnaast bleek uit de literatuurstudie dat een batch vaste kosten met zich meebrengt (zie 6.2.1). Het zou dus nuttig kunnen zijn de vaste kost te integreren in de voorgestelde methodes. Omwille van deze twee redenen wordt een 2 e experiment opgezet. Dit experiment wordt uitgevoerd om een antwoord te bieden op volgende specifieke onderzoeksvragen: 1) Wat zijn de totale kosten van de batches wanneer rekening wordt gehouden met een vaste kost per batch? Zijn er verschillen tussen de prestaties van de algoritmen op vlak van reisafstand of totale kost? 2) We proberen te weten te komen of de algoritmes beter zullen presteren op de prestatiemaatstaf reisafstand wanneer het batchingalgoritme het vullen van de batches meer benadrukt. De vaste kost is in dit geval fictief en is slechts een hulpmiddel om een betere benuttinggraad te bekomen.
70
7.7.2
Onafhankelijke variabelen
De waarden voor de variabele parameters in dit experiment worden weergegeven in tabel 7.12. Aantal langsgangen
10 en 15
Aantal dwarsgangen
2, 3 en 6
Capaciteit (volume) van de pikker
36 en 60
Tabel 7.12 Variabele parameters experiment 2 Daarnaast zal in dit experiment de vaste kost van een batch in rekening worden gebracht en als een variabele parameter worden beschouwd. Deze vaste kost is voornamelijk afhankelijk van de tijd besteed aan administratieve activiteiten tussen twee batches of het ophalen van een nieuw pikmandje/voertuig (zie 5.5 en 6.1). Aangezien in de algoritmen steeds gewerkt wordt met afstandmaten zal dit tijdsverlies getransformeerd worden naar equivalente reisafstand. Roodbergen en De Koster (2001a) schatten de snelheid van het reizen van de pikker op 0,6m/s. Aan de hand van deze snelheid berekenen we de vaste kost, uitgedrukt in reisafstand (m), voor verschillende waarden van dit tijdsverlies (tabel 7.13). Tijdsverlies tussen twee batches (in minuten)
Equivalente reisafstand
0
0
5
180
10
360
15
540
Tabel 7.13 Vaste kosten experiment 2 We zullen de methodes evalueren die ontworpen zijn om een vaste kost per batch in rekening te brengen met uitzondering van zij die ordersplitsing toelaten. In principe kunnen M3 en M4 deze kost ook in rekening brengen maar aangezien zij ordersplitsing toelaten worden zij als minder realistisch (en dus relevant) beschouwd. De methodes die in dit experiment getest worden zijn: M1(+), M2(+), M5(+), M6(+) en M7(+). Het aantal verschillende configuraties is: 2 (langsgangen) x 3 (blokken) x 2 (capaciteit) = 12. Binnen elke configuratie worden 100 herhalingen uitgevoerd (simulatie van een orderlijst en magazijn) (zie 7.3). Elk orderlijst zal onderworpen worden aan de 10 methodes, waarbij elke methode nog eens zal opgesplitst worden in 4 niveaus. Elk niveau staat dan voor een andere vaste kost.
71
7.7.3
Afhankelijke variabelen
Naast de reisafstand en de benuttinggraad zal ook de totale kost berekend worden, en dit per configuratie, per herhaling en per methode. De totale kost is uitgedrukt in afstand en is de som van de totale reisafstand en de totale vaste kosten. 7.7.4
Resultaten
7.7.4.1 Statistische test Om de statistische significantie van de effecten te testen wordt gebruik gemaakt van dezelfde procedures als in experiment 1 (zie 7.6.4.1). Ook het statistisch testen van de assumpties verloopt identiek aan experiment 1. Het enige verschil is dat we voor dit experiment 2 within-subjects factoren definiëren en dus ook interactie-effecten kunnen waarnemen tussen niveaus van deze factoren. Zo is de factor methode op 10 niveaus (de verschillende methodes) gedefinieerd en de factor kost op 4 niveaus (0, 180, 360, 540). De SPSS output bestanden zijn te vinden in bijlage 6 / CDROM. 7.7.4.2 Bespreking resultaten
A. Invloed van de vaste kost op de reisafstand Na analyse van de resultaten kunnen we besluiten dat de incorporatie van een vaste kost in de batchingmethodes niet veel invloed zal hebben op de uitkomst van dit proces. Voor M1(+), M2(+), en M5(+) was er geen enkel verschil tussen de benuttinggraden en reisafstanden bij een verschillende vaste kost. Enkel voor M6(+) en M7(+) werden verschillen waargenomen en deze zijn weergegeven tabel 7.14. Het valt op dat dit beide methodes zijn die gebruik maken van een S-shape routering. Uit de 95% betrouwbaarheidsintervallen (zie bijlage 6 / CD-ROM) blijkt echter dat deze gemiddelde reisafstanden niet significant verschillend zijn. Methode vaste kost gemiddelde reisafstand gemiddelde benuttinggraad Methode vaste kost gemiddelde reisafstand gemiddelde benuttinggraad
0 9207 86,65 0 9607 82,97
M6 180 360 9226 9226 86,94 86,93 M7 180 360 9607 9607 82,99 82,99
540 0 9226 8822 86,93 86,65 540 0 9607 8815 82,99 82,97
M6+ 180 360 8834 8835 86,94 86,93 M7+ 180 360 8815 8815 82,99 82,99
540 8835 86,93 540 8815 82,99
Tabel 7.14 Gemiddelde benuttinggraad en reisafstand per methode voor experiment 2
72
We kunnen concluderen dat het incorporeren van een fictieve vaste kost per batch groter dan 0 in de algoritmes, niet echt invloed zal hebben op uitkomst van het batchingproces. Een mogelijke verklaring is dat de algoritmes sowieso de mogelijkheid tot het opstarten van een nieuwe batch bestaande uit order i, wanneer order i ook nog kan worden toegevoegd aan een bestaande batch, weinig tot nooit zullen gebruiken. Dit komt omdat het order toevoegen aan een bestaande batch in de meeste gevallen sowieso een betere winst in reisafstand (CW) of een kleinere extra reisafstand (GR1, GR2) zal opleveren, dan in het geval van het opstarten van een nieuwe batch. Een extra stimulans door het toekennen van een fictieve vaste kost aan de batch zal dus voor deze algoritmes overbodig zijn. B. Invloed van de vaste kost op de totale kost Wanneer nu de vaste kost niet als fictief beschouwd wordt, maar achteraf ook doorgerekend wordt in de totale kosten van het batchingproces (de reisafstand + de vaste kosten van een batch), dan verwachten we dat een methode met een hogere benuttinggraad een betere totale kost zal opleveren (in vergelijking met methodes met een lage benuttinggraad) naarmate deze vaste kost stijgt. Immers, een hogere benuttinggraad impliceert een kleiner aantal batches en dus lagere vaste kosten. In tabel 7.15 is weergegeven in hoeveel procent van de gevallen M1+ of M5+ als één van de beste methodes op vlak van totale kost naar voor kwam. Tabel 7.15 is daarnaast nog opgesplitst per combinatie van capaciteit en aantal blokken omdat dit relevante interactie-effecten opleverde. Zoals ook uit experiment 1 bleek is M5+ de onbetwistbare nummer één bij een vaste kost = 0. Wanneer nu de vaste kost opgedreven wordt zal de sterke benuttinggraad van M1+ doorwegen op de resultaten. In die mate zelf dat bij een capaciteit van 36 en 5 blokken, M1+ meer dan M5+ de beste methode zal zijn in het geval van een vaste kost van 360 of meer. Dit is eenvoudig te verklaren uit experiment 1. Daar bleek namelijk dat de benuttinggraad van M5(+) sterk daalde bij een toenemend aantal blokken terwijl die van M1(+) ongeveer gelijk bleef. methode vaste kost 1 36 2 5 1 60 2 5
0 0,0 1,0 14,0 0,0 0,0 0,5
M1+ 180 3,5 19,0 47,0 0,0 1,5 10,5
360 15,0 34,5 59,0 3,0 11,0 29,5
540 21,5 37,0 59,0 5,0 16,0 31,0
0 100,0 99,0 86,5 100,0 100,0 99,5
M5+ 180 96,5 80,5 52,5 100,0 98,0 83,5
360 85,0 64,5 39,5 96,5 88,0 60,5
540 78,5 62,0 39,5 94,5 83,0 59,0
Tabel 7.15 Aantal keer dat de methode de laagste totale kost opleverde (%)
73
7.8 Experiment 3
7.8.1
Onderzoeksvragen
Voor dit experiment worden 2 specifieke onderzoeksvragen onderscheiden: 1) Presteren de algoritmen die ordersplitsing toelaten beter op vlak van reisafstand en benuttinggraad dan de best presterende algoritmen uit experiment 1? 2) We onderzoeken welke methode die ordersplitsing toelaat het minst moeilijkheden zal opleveren voor sortering en consolidatie achteraf.
7.8.2
Onafhankelijke variabelen
De waarden voor de variabele parameters in dit experiment worden weergegeven in tabel 7.16. Aantal langsgangen
10 en 15
Aantal dwarsgangen
2, 3 en 6
Capaciteit van de pikker
36 en 60
Tabel 7.16 Variabele parameters experiment 3 De methoden die geëvalueerd zullen worden zijn M1(+), M2(+), M3(+), M4(+) en M5(+). De vaste kosten zullen in dit experiment op 0 gezet worden. Het aantal verschillende configuraties is: 2 (langsgangen) x 3 (blokken) x 2 (capaciteit) = 12. Voor elk van deze configuraties simuleren we 100 maal (zie 7.3) een fictieve orderlijst en magazijn. Vervolgens testen we de 10 methodes gegeven deze input. We beschouwen een situatie zoals in De Koster et al. (2007) (zie 6.3.3). Het is dus mogelijk voor M3(+) en M4(+) om items behorende tot hetzelfde order te spreiden over meerdere batches. Het blijft ook mogelijk dat één batch items bevat uit verschillende orders. 7.8.3
Afhankelijke variabelen
In 6.3.5 werd geargumenteerd dat het aantal orders of consolidatiegroepen bepalend is voor de kostprijs van het sorteersysteem. Om die reden zullen we naast de indicatoren reisafstand en de benuttinggraad nog twee andere indicatoren berekenen via de simulatie. De bedoeling is om via deze twee extra indicatoren een idee te krijgen van de inspanningen die nodig zijn indien een pickand-sort procedure wordt gevolgd na het batchen. We willen benadrukken dat het juiste verband tussen deze indicatoren en de kosten van het sorteersysteem nog niet empirisch is aangetoond. De 74
indicatoren worden daarom louter gebruikt om de ontwikkelde batchingmethoden onderling te vergelijken en een eerste indruk te krijgen van de verschillen. Een eerste indicator is het gemiddeld aantal verschillende orders dat zich in de batch bevindt. Niet alle items van een order hoeven zich in die batch te bevinden opdat het order deel zal uitmaken van deze indicator. Bij M1(+), M2(+) en M5(+) zullen alle items van een order zich in dezelfde batch bevinden zijn, terwijl dit bij M3(+) of M4(+) niet noodzakelijk het geval zal zijn. De argumentatie voor het gebruik van deze indicator is dat bij het de input van een batch in het sorteersysteem, het aantal verschillende orders waarin de batch opnieuw moet gesplitst worden een maat zal zijn voor de benodigde capaciteit van het sorteersysteem. Een tweede indicator is een ratio die 2 elementen bevat die de complexiteit van het sorteren vergroten ten opzichte van een situatie zonder ordersplitsing:
Hoe groter het aantal batches waarover een order verspreid is, hoe complexer.
Hoe groter het aantal gesplitste orders in een batch, hoe complexer.
We definiëren de volgende variabelen: X = aantal orders die over één of meerdere batches gesplitst zijn. Y = gemiddeld aantal batches waarover de gesplitste orders gespreid zijn. De volgende constanten worden gedefinieerd (zij zijn gegeven): max#B = maximaal aantal batches dat mag gevormd worden (bepaald door het management). De geprogrammeerde algoritmes kunnen rekening houden met max#B tijdens het batchen. #O = het totaal aantal te batchen orders. Split Ratio (SR) =
X∗Y #O ∗ max#B
De Split Ratio ligt altijd tussen 0 en 1. Dit komt doordat X minimaal 0 is (dit is wanneer geen enkel order gesplitst is) en maximaal gelijk is aan het aantal orders (dit is wanneer alle orders gesplitst zijn). Y zal minimaal 0 zijn (dit is wanneer geen enkel order gesplitst is) en maximaal gelijk aan max#B (dit is wanneer men in elke batch een deel van elk gesplitst order kan terugvinden en het aantal gevormde batches gelijk is aan het maximum). De Split Ratio kan een eenvoudig instrument zijn om voor een gegeven input, de algoritmen te scoren en te vergelijken op de complexiteit met betrekking tot de consolidatie- of sorteerprocessen achteraf.
75
7.8.4
Resultaten
7.8.4.1 Statistische test Ook in dit geval zal een ANOVA repeated measures test gebruikt worden. Voor de bespreking van de assumpties verwijzen we opnieuw naar experiment 1 (7.6.4.1). De SPSS output bestanden zijn te vinden in bijlage 6 / CD-ROM. 7.8.4.2 Bespreking resultaten
A. Reisafstand en benuttinggraad Zoals uit tabel 7.17 blijkt blijven de verhoudingen tussen M1(+), M2(+) en M5(+) gerespecteerd in vergelijking met experiment 1. We zien echter dat tussen M5+ en de beste methode het gemiddeld verschil maar liefst 56,3% bedraagt. Met andere woorden, men zou nog eens de helft zoveel reisafstand kunnen besparen bij het gebruik van M4+ in plaats van M5+. Methode gemiddelde reisafstand gemiddeld verschil met beste afstand (%) gemiddelde benuttinggraad gemiddeld verschil met beste benuttinggraad (%)
M1 M1+ M2 M2+ M3 M3+ M4 M4+ M5 M5+ 8166 7205 7726 7381 8055 7956 2964 2952 6897 6831 63,4 58,6 61,2 59,4 62,9 62,4 0,4 0,0 56,7 56,3 92,25 92,25 87,25 87,25 96,03 96,03 95,98 95,98 91,06 91,06 4,22
4,22
10,4
10,4
0,05
0,05
0,11
0,11
5,64
5,64
Tabel 7.17 Gemiddelde benuttinggraad en reisafstand per methode voor experiment 3 Opvallend is de prestatie van M3(+). M3 scoort het best op vlak van benuttinggraad. Maar er is al eerder geargumenteerd dat een goede benuttinggraad op zich geen garantie is op succes. Dit was wel voordelig, zo bleek duidelijk uit experiment 1, wanneer er daarna een verbeteringsalgoritme werd toegepast dat orders kon switchen tussen batches onderling. Wanneer die logica gevolgd wordt, zou men kunnen verwachten dat M3+ wel relatief goed zou scoren. Uit de resultaten blijkt dat dit echter ook niet het geval is. De verklaring is simpel: voor M3 en M4 is enkel het SI verbeteringsalgoritme toegepast. Dit betekent dat enkel de pikvolgorde van de items in een individuele batch zal gewijzigd worden. Het SO algoritme wordt in deze methodes niet toegepast omdat er weinig volledige orders te vinden zijn in de batches en dit algoritme in feite ontwikkeld is voor methodes zonder ordersplitsing. We stellen voor dat indien één van de methodes met ordersplitsing in de toekomst verder wordt gebruikt, er best een verbeteringsalgoritme wordt toegevoegd dat individuele items kan verwisselen tussen de batches. Dit verbeteringalgoritme zou dan zowel kunnen rekening houden met het verbeteren van de reisafstand als met andere 76
prestatiemaatstaven zoals SR en het gemiddeld aantal orders per batch (zie B). We kunnen echter besluiten dat indien men ordersplitsing overweegt, men voor M4+ moet kiezen en zeker niet voor M3+. M3+ genereert namelijk een slechtere reisafstand dan M5+ en vergt daarenboven extra sorteerinspanningen ten opzichte van M5+ door de ordersplitsing. B. Invloed van ordersplitsing op het sorteren We moeten in de eerste plaats vermelden dat we tijdens het batchingproces het maximaal aantal te vormen batches formeel gelijk hebben gesteld aan het aantal te batchen orders. Op de vraag wat de beste waarde is voor dit maximum is, gaan we in deze masterproef verder niet op in. Allerlei redenen kunnen aangehaald worden. Wanneer alle batches tegelijk moeten gepikt worden kan men dit maximum bijvoorbeeld gelijkstellen aan het maximum aantal pikkers of het maximum aantal pikvoertuigen. Ook kan men argumenteren dat men misschien door middel van een optimale waarde van dit getal de algoritmes beter kan laten presteren doordat ze met deze waarde kunnen rekening houden. Er wordt in deze laatste redenering dan een fictief maximum ingesteld, net zoals in experiment 2 er een fictieve vast kon worden ingegeven. In dit experiment zien de algoritmes max#B, door de hoge waarde van max#B, nog niet als een beperking. Het maximum aantal batches zal wel de waarde van de SR beïnvloeden. De waarde van SR op zich is echter niet belangrijk, eerder de verhouding van de SR tussen verschillende methodes. In tabel 7.18 is het gemiddeld aantal orders per batch en de SR weergegeven voor elke methode, onderverdeeld naargelang de capaciteit van de pikker. M1(+) M2(+) M3(+) M4(+) M5(+) SR O/B SR O/B SR O/B SR O/B SR O/B 36 0,00 2,76 0,00 2,54 0,01 4,02 0,09 15,12 0,00 2,71 60 0,00 4,67 0,00 4,52 0,01 5,84 0,08 22,60 0,00 4,62 7.18 Gemiddeld aantal orders per batch en de SR per methode in functie van de capaciteit Verscheidene zaken vallen op bij het bekijken van tabel 7.18. Eerst en vooral zien we dat zoals verwacht het aantal orders per batch bij de methodes zonder ordersplitsing ongeveer 3 en 5 bedraagt. Dit is logisch, gegeven de assumpties omtrent de samenstelling van de orders (tabel 7.2). Opmerkelijk is ook dat M3 het aantal orders per batch beperkt, gecombineerd met een hoge benuttinggraad (tabel 7.17). Dit betekent dat er waarschijnlijk nog complete orders terug te vinden zijn in M3. Daarnaast zal ook het aantal batches waarover de items van een order gespreid zijn beperkt blijven. Deze resultaten volgens logischerwijs uit de werking van het algoritme. De items worden namelijk één voor één (gesorteerd per order en per volgnummer) geselecteerd om deze vervolgens toe te wijzen aan een bestaande of een nieuwe batch. Vooral de orders met een kleiner 77
volgnummer zullen door deze procedure vaker intact teruggevonden worden in een batch. M4+, de geprefereerde methode wanneer men via ordersplitsing de reisafstand drastisch wil laten dalen, zal daarentegen veel sorteerinspanningen vergen. Bij een capaciteit van de pikker van 36, zullen er zich ongeveer 15 verschillende orders in een batch bevinden. Wanneer we weten dat een item tussen 1 en 3 capaciteit inneemt, is het makkelijk in te zien dat zo goed als elk item in de batch zal behoren tot een verschillend order. Er moet daarnaast opgemerkt worden dat ook de SR van M4(+) acht maal hoger is dan die van M3(+). Dit wijst op een hoger aantal gesplitste orders en/of een groter aantal batches waarover deze gesplitste orders verspreid zijn. De goede benuttinggraad en dito reisafstand van M4+ gaat dus samen met een complex sorteerproces. Een afweging zal dus moeten gemaakt worden tussen de winst in reisafstand (tabel 7.17) en de extra kosten voor het sorteren achteraf. 7.9 Besluit Via een eerste experiment werd aangetoond dat niet enkel het aantal langsgangen en de capaciteit van de pikker, maar ook het aantal blokken en de combinatie van het aantal langsgangen en blokken een invloed zal hebben op de prestaties van de batchingalgoritmen. We beschouwen deze batchingalgoritmen echter liever als een onderdeel van een geïntegreerde methode bestaande uit een routeringheuristiek, samenvoegingheuristiek, verbeteringmethode en een batchingalgoritme. De geteste geïntegreerde methodes zijn enerzijds samengesteld uit bestaande algoritmen die werden overgenomen, gewijzigd of uitgebreid en anderzijds uit nieuwe algoritmen. Uit experiment 1 kwam M5+ als beste geïntegreerde methode naar voor, onafhankelijk van de layout van het magazijn of de capaciteit van de pikker. Deze methode bestaat uit de combinatie van een KP routering, INS samenvoegingprocedure, CW batchingalgoritme en de SO en SI verbeteringsalgoritmen. In 7.1 staan deze algoritmen in detail beschreven. M5+ verbetert de klassieke combinatie FCFS & S-shape met maar liefst 30%. De keuze van het gepaste algoritme zal daarenboven belangrijker worden wanneer de capaciteit van de pikker relatief laag is. We besluiten ook dat het toevoegen van een verbeteringsalgoritme significante en relevante winst in reisafstand kan opleveren. Wanneer een methode initieel een slechte reisafstand genereert maar wel een hoge benuttinggraad (of klein aantal batches), stijgt het winstpotentieel door toepassing van de verbeteringsalgoritmes ten opzichte van methodes met een lage benuttinggraad een goede reisafstand. E Uit experiment 2 concluderen we dat ook de grootte van de vaste kost van een batch belangrijk is voor de keuze van een geïntegreerde methode. Hoe hoger deze kost, hoe meer men moet zoeken naar algoritmes die een hogere benuttinggraad combineren met een degelijke reisafstand. Bij een 78
grote vaste kost en groot aantal dwarsgangen wordt om die reden M1+ aangeraden in plaats van M5+. Experiment 3 ten slotte leerde ons dat de reisafstand met meer dan 50% kan verminderd worden door toepassing van M4+ in plaats van M5+. M4+ laat echter ordersplitsing toe waardoor extra sorteerinspanningen nodig zijn. Een afweging zal dus moeten gemaakt worden tussen de winst in reisafstand en de extra kosten voor het sorteren.
79
8. Algemeen besluit
8.1 Samenvatting en conclusies In deze masterproef werd aangetoond dat excellent logistiek beheer cruciaal is om als bedrijf competitief te blijven. Men moet continu streven naar een perfecte doorstroming van goederen, financiële middelen en informatie doorheen de supply chain. Optimalisatie van het orderpikproces kan een middel zijn om de efficiëntie van de supply chain te verhogen. Volgens Tompkins (2003) tellen de kosten voor orderpikken namelijk mee voor 50% van de totale kosten in magazijnbeheer en bestaat het grootste deel van deze activiteit uit het reizen van de ene naar de andere opslaglocatie. Indien men deze reistijd, die geen waarde toevoegt voor de klant, tot een minimum herleidt kan men de orders efficiënter verzamelen en zullen de operationele kosten dalen. Omwille van dit economisch belang onderzochten we de verschillende operationele beslissingen gerelateerd aan het orderpikken. Beslissingen in deze categorie zijn het batchen van de orders, het routeren van de pikker en het sorteren of consolideren van de gepikte items. In deze masterproef werd onderzocht of het mogelijk is een algoritme te ontwikkelen die de reistijd voor de pikker significant verminderd door efficiënt te batchen en te routeren en tegelijkertijd rekening te houden met de sorteerinspanningen. Op die manier kan de efficiëntie van de supply chain namelijk worden verbeterd. In de eerste plaats werd de combinatie van het routering- en batchingvraagstuk bestudeerd als een combinatorisch probleem. Dit probleem kan beschreven worden als een variant op het klassieke Vehicle Routing Problem (VRP). Het verbod op ordersplitsing is de oorzaak van de specifieke complexiteit van het pikprobleem. Door deze restrictie moet men de afstand of nabijheid tussen orders meten in plaats tussen de individuele items of opslaglocaties. Het doel is gelijkaardige of nabije orders samen te pikken. Aangezien een order bestaat uit items, gelegen op verschillende locaties, is het zeer moeilijk vast te stellen wat de ‘locatie’ van een order is. Daarenboven wordt de afstand tussen orders ook bepaald door het gekozen routeringalgoritme. Dit alles spreekt in het voordeel van een oplossingsmethode die het batching- en routeringprobleem tezamen optimaliseert. Vervolgens werden bestaande batching-, routering- en sorteringstrategieën onderzocht aan de hand van een literatuurstudie. De meeste aandacht in deze studie ging naar het batching- en routeringvraagstuk, in mindere mate werd ook het sorteerproces besproken. Voor het routeringprobleem werden zowel exacte algoritmes als heuristieken ontwikkeld. Alhoewel het
80
gebruik van een exact algoritme significante voordelen kan opleveren ten opzichte van het gebruik van een heuristiek (De Koster en Van Der Poort, 1998) wordt dit exact algoritme niet altijd gebruikt. Ten eerste bestaan er slechts exacte algoritmes voor magazijnen bestaande uit één of twee blokken. Ten tweede zijn de exacte algoritmes minder transparant voor de pikker en dus moeilijker aan te leren. Ten slotte kunnen ook praktische restricties zoals congestie in de gangen het gebruik van een exact algoritme onmogelijk maken. Omwille van deze redenen worden door verschillende auteurs routeringheuristieken voorgesteld voor magazijnen bestaande uit één of meerdere blokken (Vaughan en Petersen, 1999). De prestaties van deze heuristieken variëren in functie van de lay-out van het magazijn, de gekozen opslagmethode of de grootte van de piklijst. Ook batchingalgoritmen zijn veelvuldig bestudeerd in de wetenschappelijke literatuur. In deze masterproef werd een overzicht gegeven gebaseerd op de aard van het algoritme. Exacte algoritmes werden ontwikkeld voor problemen met een klein aantal orders of batches. Voor meer realistische situaties stellen de meeste onderzoekers seed of savings heuristieken voor. Recent worden ook data-mining, clusteranalyse en metaheuristieken toegepast. Net zoals bij de routeringalgoritmen is ook de prestatie van vele batchingalgoritmen sterk afhankelijk van de lay-out van het magazijn (aantal langsgangen), het opslagbeleid, de capaciteit van de pikker en de grootte van de orderlijst. Daarnaast speelt ook de gevolgde routeringmethode een belangrijke rol. Alhoewel de lay-out dus een belangrijke rol speelt en een magazijn uit meerdere blokken voordelig is (Roodbergen en De Koster, 2001a), zijn er nog geen onderzoeken bekend waarin batchingalgoritmen worden gesimuleerd of gemodelleerd in magazijnen bestaande uit meer dan twee blokken. Zo goed als alle algoritmen worden gesimuleerd in een magazijn bestaande uit één blok, met uitzondering van LeDuc en De Koster (2007) die een oplossingmethode voorstellen voor een magazijn uit twee blokken (figuur 6.1). In het laatste deel van de literatuurstudie werd het sorteerproces van naderbij bekeken. Belangrijk was dat in een automatisch sorteersysteem het aantal orders of consolidatiegroepen per pikgolf een invloed zal hebben op de kost van dit sorteersysteem. Verder is ook de efficiëntie van het order-tolane algoritme afhankelijk van het batchingproces. Men moet namelijk streven naar gebalanceerde batches die rekening houden met de capaciteit van het sorteersysteem. Meller (1997) en Johnson (1998) besluiten dus dat verdere integratie tussen de order-to-lane toewijzing (en het sorteerproces in het algemeen), de batchingprocedure en de routeringprocedure noodzakelijk is. Ten slotte werden geïntegreerde methoden voorgesteld om de combinatie van het batching- en routeringprobleem op te lossen. De voorgestelde heuristische methoden bestaan uit vier elementen: een routeringheuristiek, samenvoegingheuristiek, verbeteringsmethode en een 81
batchingalgoritme. Aangezien er vaak interactie is tussen deze verschillende algoritmes worden zij dan ook niet apart maar tezamen als een geïntegreerde methode geëvalueerd. De algoritmes vinden hun oorsprong in enerzijds bestaande methodes, die eventueel werden gewijzigd of uitgebreid en anderzijds in nieuwe methodes, die gebaseerd zijn op algoritmen ontwikkeld voor het Vehicle Routing Problem (VRP) of Travelling Salesman Problem (TSP). Er wordt via deze methodes ook getracht het batching- en routeringproces niet sequentieel te laten verlopen maar gelijktijdig. De routes zullen reeds gevormd worden tijdens het batchen. De voorgestelde methodes werden getest door middel van drie experimenten. In een eerste experiment werd aangetoond dat niet enkel het aantal langsgangen en de capaciteit van de pikker, maar ook het aantal blokken een invloed zal hebben op de prestaties van de algoritmen. Over de hele lijn presteerde M5+ het best, dit is een heuristiek die bestaat uit een KP routering, INS samenvoegingprocedure, CW batchingalgoritme en de SO en SI verbeteringsalgoritmen (zie tabel 7.1). In hoofdstuk 7.1 staan deze algoritmen beschreven. Via dit experiment werd ook duidelijk dat het toevoegen van verbeteringsalgoritmen aan te raden is en dat batchingalgoritmen moeten rekening houden met zowel de benuttinggraad (het minimaliseren van het aantal batches) als de reisafstand. De voorgestelde verbeteringsalgoritmes zullen namelijk goed presteren wanneer de initiële oplossing wordt gekenmerkt door een sterke benuttinggraad. In een tweede experiment onderzochten we de mogelijkheden om de algoritmes beter te laten presteren op vlak van benuttinggraad en reisafstand door een fictieve vaste kost in te voegen. Aangezien tijdens het batchen het sowieso voordeliger bleek orders samen te nemen in plaats van individueel te pikken, had deze ingreep weinig effect. Vervolgens werd onderzocht welk algoritme het best scoorde op de totale kost. De totale kost is samengesteld uit een reële vaste kost per batch en de reisafstand. De resultaten gaven aan dat hoe complexer de lay-out (meer blokken, meer langsgangen) en hoe hoger de vaste kost (vb.: meer tijdsverlies tussen twee batches) hoe meer het gebruik van M1+ aan te raden was. M1+ wordt namelijk gekenmerkt door de combinatie van een sterke benuttinggraad en degelijke reisafstand. Ten slotte werd in een derde experiment het verbod van ordersplitsing losgelaten. We stelden vier methodes voor die orders kunnen spreiden over meerdere batches en vergeleken deze methodes met de best presterende methodes uit de vorige experimenten. Het experiment leerde ons dat we de reisafstand tot 50% kunnen verminderen wanneer we M4+ toepassen in plaats van M5+. Er moet op gewezen worden dat deze vorm van ordersplitsing er voor zal zorgen dat meer sorteerinspanningen zullen nodig zijn na het pikken. Een afweging zal dus moeten gemaakt worden tussen de winst in reisafstand en de extra kosten voor het sorteren. 82
8.2 Beperkingen van het onderzoek Bij het onderzoeken van de literatuur waren de meeste wetenschappelijke artikels vrij beschikbaar en terug te vinden via elektronische platformen (ELIN, Web of Science,…). Sommige wetenschappelijke artikels waren niet of slechts tegen betaling te verkrijgen. Deze artikels werden in het mate van het mogelijke besproken via andere bronnen. In het algemeen werden weinig tot geen beperkingen of moeilijkheden ervaren bij het vinden van de relevante literatuur. Het is echter wel moeilijker om de verschillende studies met elkaar te vergelijken, in het bijzonder dan de studies over batchingalgoritmen. Dit omwille van de verschillende omstandigheden waarin deze algoritmen worden gesimuleerd. Vele onderzoekers simuleren wel de reisafstanden na het batchen op basis van de S-shape routering, maar de combinatie van de lay-out van het magazijn, de samenstelling van de orderlijst en de capaciteit van de pikker is voor 2 verschillende studies, uitgevoerd door verschillende onderzoekers, nooit dezelfde. Ook de resultaten van onze experimenten zijn niet direct veralgemeenbaar voor alle magazijnen of alle types van orderlijsten. Er is gepoogd enkele parameters in verband met de lay-out en de capaciteit variabel te houden, maar het was praktisch niet mogelijk om alle parameters te variëren. Daarenboven zijn er ook nog geen studies bekend die batchingalgoritmen testen in magazijnen bestaande uit meer dan twee blokken, er is dus geen vergelijkingsmateriaal voor de resultaten bekomen voor die specifieke configuraties. Hetzelfde geldt voor de nieuwe algoritmes die werden getest in de experimenten. 8.3 Richtlijnen voor verder onderzoek Om in de toekomst de resultaten van de experimenten, uitgevoerd via simulatie, te kunnen veralgemenen zou er een dataset van magazijn- en orderlijstconfiguraties moeten worden geproduceerd die de volledige verscheidenheid aan orderlijsten en magazijnen omvat (‘full range of complexity’) en die daarbij rekening houdt met de factoren die van invloed kunnen zijn op routering, batching en sortering. Deze dataset zou dan kunnen gebruikt worden bij de simulaties en men zou de resultaten op die manier kunnen veralgemenen. Het andere uiterste is een individuele oplossing zoeken, case per case. Uiteraard kan men een oplossing voor één specifieke case niet veralgemenen. De huidige studies bevinden zich ergens tussen deze twee uitersten, maar het lijkt efficiënter om te streven naar de complete dataset. Verdere integratie van de operationele processen in magazijnen is nodig. In deze masterproef is de combinatie van het routeren en batchen aangepakt. Daarnaast is er ook een aanzet gegeven tot integratie met het sorteerproces. Men kan ook het opslagbeleid in de analyse betrekken. Zeker en 83
vast moet men streven naar een zo algemeen mogelijk probleemstelling, dit om globaal en niet lokaal te optimaliseren. Specifiek voor de integratie van het batchen en routeren lijkt de toepassing van een metaheuristiek het onderzoeken waard. Metaheuristieken bieden een perfecte mogelijkheid om het routeren en batchen te integreren (ten opzichte van een sequentiële optimalisatie). De moeilijkheid zal zijn om de oplossingen zo te coderen dat deze integratie kan bereikt worden en deze oplossingen tegelijkertijd nog makkelijk te manipuleren zijn. Zowel het toewijzen van de orders aan de batches als de pikvolgorde moeten namelijk in de codering verwerkt worden voor de ideale geïntegreerde en simultaan uitgevoerde oplossingsmethode. Hsu et al. (2005) en Tsai et al. (2008) introduceerden het genetisch algoritme als oplossingmethode voor het pikprobleem. De resultaten van Tsai et al. (2008) leken veelbelovend, ware het niet dat zij ordersplitsing toelieten. Zoals ook uit ons derde experiment bleek zorgt ordersplitsing sowieso voor kortere reisafstanden en veranderingen in de rangordes van de algoritmen. Hsu et al. (2005) simuleerden hun methode in een magazijn bestaande uit één blok en in combinatie met de S-shape routering. Omwille van de beperkingen van de vorige onderzoeken raden wij een nieuwe vergelijkende studie aan waarbij een genetisch algoritme geconstrueerd wordt op basis van Tsai et al. (2008) maar met het verbod op ordersplitsing. Naast het toepassen van dit genetisch algoritme kan ook het potentieel van andere metaheuristieken worden onderzocht (vb. tabu-search en simulated annealing). Deze nieuwe algoritmen kunnen dan vergeleken worden met de M5+ methode (zie 7.1.5).
84
Bronnen Aminoff A., Kettunen O. en Pajunen-Muhonen H., 2002, Research on factors affecting warehousing efficiency, International Journal of Logistics Research and Applications, volume 5, issue 1, 45-57. Apte U.M. en Viswanathan S., 2000, Effective cross docking for improving distribution efficiencies, International Journal of Logistics Research and Applications, volume 3, issue 3, 291-302. Armstrong R.D., Cook W.D. en Saipe A.L., 1979, Optimal batching in a semi-automated order picking system, The Journal of the Operational Research Society, volume 30, No. 8, 711-720. Ballou R.H., 1992, Business Logistics Management, 3e editie, Prentice-Hall, Englewood Cliffs, NJ. In: Apte en Viswanathan (2000). Bartholdi J.J. en Hackman S.T., 2008, Warehouse & Distribution science, URL: <www.warehouse-science.com>. Bozer Y.A. en Cho M., 2005, Throughput performance of automated storage/retrieval systems under stochastic demand, IEE Transactions, volume 37, No. 4, 367-378. Bozer Y.A. en Kile J.W., 2007, Order batching in walk-and-pick order picking systems, International Journal of Production Research, volume 46, No. 7, 1 april 2008, 1887-1909. Bozer Y.A. en Sharp G.P., 1985, An empirical evaluation of a general purpose automated order accumulation and sortation system used in batch picking, Material Flow 2, 111-131. In: Choe en Sharp (1991). Bozer Y.A., Quiroz M. A. en Sharp G.P., 1987, Simulation for Automated Accumulation and Sortation systems, Niet-gepubliceerd verslag, Material Handling Research Center, Georgia Institute of Technology, Atlanta, Georgia. In: Choe en Sharp (1991). Bowersox D.J., Closs D.J. en Cooper M.B., 2002, Supply Chain Logistics Management, Mc Graw-Hill New York. In: Theys en Herroelen (2005). Bräysy O., 2001, Local Search and Variable Neighborhood Search Algorithms for the Vehicle Routing Problem with Time Windows, Acta Wasaensia, No. 87, 168 p Brynzér H. en Johansson M.I., 1995, Design and performance of kitting and order picking systems, International Journal, volume 41, No. 1-3, 115-125. Caron F., Marchet G. en Perego A., 1998, Routing policies and COI-based storage policies in pickerto-part systems, International Journal of Production Research, volume 36, No. 3, 713-732. Caron F., Marchet G. en Perego A., 2000, Optimal layout in low-level picker-to-part systems, International Journal of Production research, volume 38, No. 1, 101-117. Chen M.-C., Huang C.-L., Chen K.-Y. en Wu H.-P., 2005, Aggregation of orders in distribution centers using data mining, volume 28, 453-460.
Chen M.-C. en Wu H.-P., 2005, An association-based clustering approach to order batching considering customer demand patterns, Omega, volume 33, 333-343. Chew E.P. en Tang L.C., 1999, Travel time analysis for general item location assignment in a rectangular warehouse, European Journal of Operational Research, volume 112, 582-597. Choe K. en Sharp G.P., 1991, Small parts order picking: design and operation. URL:
. Clarke G. en Wright W., 1964, Scheduling of vehicles form a central depot to a number of delivery points, Operations Research, volume 12, 568-581. Coyle J.J., Bardi E.J. en Langley C.J., 2003, The management of business logistics: a supply chain perspective, 7e editie, South-Western, Thomson Learning. Daniels R.L., Rummel J.L. en Schantz R., 1998, A model for warehouse order picking, European Journal of Operational Research, volume 105, 1-17. De Koster R., Le-Duc T. en Roodbergen K.J., 2007, Design and control of warehouse order picking: A literature review, European Journal of Operational Research, volume 182, No. 2, 481-501. De Koster R. en Van der Poort E.S., 1998, Routing orderpickers in a warehouse: A comparison between optimal and heuristic solutions, IIE Transactions, No. 30, 469-480. De Koster M.B.M., Van der Poort E.S. en Wolters M., 1999, Efficient order batching methods in warehouses, International Journal of Production Research, volume 37, No. 7, 1479-1504. Delaney R.V., 2000, 11th Annual “State of Logistics Report”, National Press Club, Washington DC. In: Jane en Laih (2005). Drury J., 1988, Towards more efficient orderpicking, IMM Monographs 1, Institute of Materials Management, Cranfield UK. In: Gademann en Van De Velde (2005). ELA/AT Kearny, 2004, Excellence in Logistics 2004. ELA, Brussels. In: De Koster et al. (2007). Ellis J.L., 2006, Statistiek voor de psychologie, Uitgeverij Boom. Elsayed E.A., 1981, Algorithms for optimal material handling in automatic warehousing systems, International Journal of Production Research, volume 19, No. 5, 525-535. Elsayed E.A. en Lee M.-K., 1996, Order processing in automated storage/retrieval systems with due dates, IIE Transactions, volume 28, No. 7, 567-578. In: Gademann et al. (2001) Elsayed E.A., Lee M.-K., Kim S. en Scherer E., 1993, Sequencing and batching procedures for minimizing earliness and tardiness penalty of order retrievals, International Journal of Production Research, volume 31, No. 3, 727-738. Elsayed E.A. en Stern R.G., 1983. Computerized algorithms for order processing in automated warehousing systems, International Journal of Production Research, volume 21, No. 4, 579-586.
Elsayed E.A. en Unal O.I., 1989, Order batching algorithms and travel-time estimation for automated storage/retrieval systems, International Journal of Production Research, volume 27, No. 7, 10971114. Gademann A.J.R.M., Van Den Berg J.P. en Van Der Hoff H.H., 2001, An order batching algorithm for wave picking in a parallel-aisle warehouse, IIE Transactions, volume 33, 358-398. Gademann N. en Van De Velde S., 2005, Order batching to minimize total travel time in a parallelaisle warehouse, IIE Transactions, volume 37, 63-75. Gans N. en Van Ryzin G., 1999, Dynamic vehicle dispatching: Optimal heavy traffic performance and practical insights, Operations Research, volume 47, No. 5, 675 – 692. Gelders L. en Heeremans D., 1994, het traveling salesman probleem toegepast op order picking, Tijdschrift voor Economie en Management, volume 39, No. 4, 381-388. Gibson D.R. en Sharp G.P., 1992, Order batching procedures, European Journal of Operational Research, volume 58, No.1, 57-67. Goel A. en Gruhn V., 2008, A General vehicle routing problem, European Journal of Operational Research, volume 191, 650-660. Goetschalckx M. en Ratliff D.H., 1988, Order picking in an aisle, IIE Transactions, volume 20, No. 1, 53-62. In: Won en Olafsson (2005). Gu J., Goetschalckx M. en McGinnis L.F., 2007, Research on warehouse operation: A comprehensive review, European Journal of Operational Research, volume 177, 1-21. Hall R.W., 1993, Distance Approximation for routing manual pickers in a warehouse. IIE Transactions, volume 25, No. 4, 76-87. In: Ho en Tseng (2006) Helsgaun K., 2000, An effective implementation of the Lin-Kernighan Traveling Salesman Heuristic, European Journal of Operational Research, volume 126, No. 1, 106-130. Ho Y.-C. en Tseng Y.-Y., 2006, a study on order-batching methods of order-picking in a distribution centre with two cross-aisles, International Journal of Production Research, volume 44, No. 17, 33913417. Hsu C.-M., Chen K.-Y. en Chen M.-C., 2005, Batching orders in warehouses by minimizing travel distance with genetic algorithms, Computers in Industry, volume 56, 169-178. Hwang H., Baek W. en Lee M., 1988, Cluster algorithms for order picking in an automated storage and retrieval system, International Journal of Production Research, volume 26, No.2, 189-204. Hwang H. en Kim D.G., 2005, Order-batching heuristics based on cluster analysis in a low-level picker-to-part warehousing system, International Journal of Production Research, volume 43, No. 17, 3657-3670. Hwang H. en Lee M.K., 1988, Order batching algorithms for a man-on-board automated storage and retrieval system, Engineering costs and production economics, volume 13, 285-294.
Hwang H., Oh Y.H. en Lee Y.K., 2004, An evaluation of routing policies for order-picking operations in low-level picker to part system, International Journal of Production Research, volume 42, No. 18, 3873-3889. Hwang H.S. en Cho G.S., 2006, A performance evaluation model for order picking warehouse design, Computers & Industrial Engineering, volume 51, No. 2, 335-342. Indra-Payoong N. en Pinthong K., 2005, Forming batches of customer orders in a warehouse, Proceedings of the 2005 International conference on simulation and modeling. Jane C.-C. en Laih Y.-W., 2005, A clustering algorithm for item assignment in a synchronized zone order picking system, European Journal of Operational research, volume 166, 489-496. Jewkes E., Lee C. en Vickson R., 2004, Product location, allocation and server home base location for an order picking line with multiple servers, Computers & Operations Research, volume 31, 623-636 Johnson E.M., 1998, The impact of sorting strategies on automated sortation system performance, IIE Transactions, volume 30, No. 1, 67-78. Larson T.N., March H. en Kusiak A., 1997, A heuristic approach to warehouse layout with class based storage, IIE Transactions, volume 29, 337-348. Le-Duc T. en De Koster R. M.B.M., 2007, travel time estimation and order batching in a 2-block warehouse, European Journal of Operational Research, volume 176, 374-388. Lin S. en Kernighan W., 1973, An effective heuristic algorithm for the traveling-salesman problem, Operations Research, volume 21, No 2, 498-516. Little J.D.C., Murty K.G., Sweeny D.W. en Karel C., 1963, An algorithm for the traveling salesman problem, Operations Research, volume 11, 972-989. Makris P.A. en Giakoumakis I.G., 2003, k-Interchange heuristic as an optimization procedure for material handling applications, Applied Mathematical Modelling, volume 27, No. 5, 345-358. Makris P.A., Makri A.P en Provatidis C.G., 2006, energy-saving methodology for material handling applications, Applied energy, volume 83, 1116-1124. Malmborg C.J., 1995, Optimization of cube-per-order index warehouse layouts with zoning constraints, International Journal of Production Research, volume 33, No. 2, 465-482. Meller R.D., 1997, Optimal order-to-lane assignments in an order accumulation sortation system, IIE Transactions, volume 29, No. 4, 293-301. Muppani V.R. en Adil G.K., 2008, Efficient formation of storage classes for warehouse storage location assignment: A simulated annealing approach, Omega, volume 36, 609-618. Novich N.S., 1990, Leading-edge distribution strategies, The Journal of Business Strategy, november december, 48-53. Pan C.-H. en Liu S.-Y., 1995, A comparative study of order batching algorithms, Omega, International Journal of Management Science, volume 23, No. 6, 691-700.
Parikh P.J. en Meller R.D., 2008, Selecting between batch and zone order picking strategies in a distribution center, Transportation Research Part E, volume 44, No. 5, 696-719. Petersen C.G., 1995, Routeing and storage policy interaction in order picking operations, Decision Sciences Institute Proceedings, volume 3, 1614-1616. Petersen C.G., 1997, An evaluation of order picking routing policies, International Journal of Operations & Production Management, Volume 17, No.11, 1098-1111. Petersen C.G. en Aase G., 2004, A comparison of picking, storage and routing policies in manual order picking., International Journal of Production Economics, volume 92, 11-19. Ratliff H.D. en Rosenthal A.S., 1983, Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem, Operations Research, volume 31, No. 3, 507-521. Roodbergen K.J. en De Koster R., 2001a, Routing methods for warehouses with multiple cross aisles, International Journal of Production Research, volume 39, No. 9, 1865-1883 Roodbergen K.J. en De Koster R., 2001b, Routing order-pickers in a warehouse with a middle aisle, European Journal of Operational Research, volume 133, 32-43. Rosenwein M.B., 1994, An application of cluster analysis to the problem of locating items within a warehouse, IIE Transactions, volume 26, No. 1, 101-103. Rosenwein M.B., 1996, A comparison of heuristics for the problem of batching orders for warehouse selection, International Journal of Production Research, volume 34, No. 3, 657-664. Rouwenhorst B., Reuter B., Stockrahm V., van Houtem G.J., Mantel R.J. en Zijm W.H.M., 2000, Warehouse design and control: Framework and literature review, European Journal of Operational Research, volume 122, No. 3, 515-533. Ruben R.A. en Jacobs F.R., 1999, Batch construction heuristics and storage assignment strategies for walk/ride and pick systems, Management Science, volume 45, No. 4, 575-596. Selvarajah E. en Steiner G., 2006, Batch scheduling in a two-level supply chain – a focus on the supplier, European Journal of Operational research, volume 173, 226-240. Silver E.A., 2002, An overview of heuristic solution methods, Working Paper – 2002-15, University of Calgary - Haskayne School of Business, Oktober 2002, URL: < http://www.haskayne.ucalgary.ca/haskaynefaculty/files/haskaynefaculty/overview.pdf > Tang L.C. en Chew E.-P., 1997, Order picking systems: batching and storage assignment strategies, Computers & Industrial Engineering, volume 33, No. 3-4, 817-820. Theys C., Bräysy O, Dullaert W. en Raa B., 2007, Towards a Metaheuristic for Routing Order Pickers in a Warehouse, Evolutionary Methods for Design, Optimization and Control, Neittaanmaki P., Periaux J. en Tuovinen T. (Eds), Barcelona.
Theys C. en Herroelen W., 2005, Kritische studie van de methoden voor het bepalen van de routes voor orderverzamelaars in magazijnen, Eindverhandeling, Katholieke Universiteit Leuven, departement Toegepaste Economische Wetenschappen. Thomas J.D. en Griffin P.M., 1996, Coordinated supply chain management, European Journal of Operational Research , volume 94, issue 1, 11 oktober 1996, 1-15. Tijms H.C., 2008, Optimalisatie in Netwerken, Afdeling Econometrie & Operationele Research, Vrije Universiteit, Amsterdam, URL: < http://www.epsilon-uitgaven.nl/ >, Bewerking uit het boek: Tijms H.C., 2004, Operationele Analyse, 2e druk, Uitgeverij Epsilon. Tompkins J.A., White J.A., Bozer Y.A., Frazelle E.H. en Tanchoco J.M.A., 2003, Facilities Planning, Third Edition, Wiley. Tsai C. –Y., Liou J.J.H. en Huang T.-M., 2008, Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time, International Journal of Production Research, volume 46, No. 22, 6533-6555. Van den Berg J.P., 1999, A literature survey on planning and control of warehousing systems, IIE Transactions, volume 31, 751-762. Van Dierdonck R., 2007, Magazijnbeheer, Syllabus Logistiek Management, hoofdstuk 16. Van Landeghem H., 2007, Advanced methods in production and logistics, logistic technology: warehousing, slides hoorcollege. Vaughan T.S. en Petersen C.G., 1999, The effect of warehouse cross aisles on order picking efficiency, International Journal of Production research, volume 37, No. 4, 881-897. Waters D., 2003, Logistics. An Introduction to Supply Chain Management, Palgrave Macmillan Basingstoke. Wijnen K., Janssens W., De Pelsmacker P. en Van Kenhove P., 2002, Marktonderzoek met SPSS: statistische verwerking en interpretative, Garant, Antwerpen – Apeldoorn. Wolters M., 1996, Het batchen van orders in een magazijn, een vergelijking van heuristieken. Master’s thesis, Universiteit Groningen. Won J. en Olafsson S., 2005, Joint order batching and order picking in warehouse operations, International Journal of Production Research, volume 43, No. 7, 1427-1442. Yu M. en De Koster R., 2008, Performance approximation and design of pick-and-pass order picking systems, IIE Transactions, volume 40, No.11, 1054-1069.
Bijlage 1: Schematische voorstelling van een magazijn Onderstaand magazijn bestaat uit 3 blokken, 4 dwarsgangen, 3 langsgangen, 9 subgangen en 72 opslaglocaties.
51 50 49 48 27 26 25 24 3 2 1 0
. . . . . (d) . . . . . . . . . . (c) .
(a) = subgang (b) = langsgang (c) = depot
55 54 53 52 31 30 29 28 7 6 5 4
. 59 (b) . 58 . 57 . 56 . . 35 . 34 . 33 . 32 . . 11 . 10 . 9 . 8 . .
63 62 61 60 39 38 37 36 15 14 13 12
. 67 (a) . 66 . 65 . 64 . . 43 . 42 . 41 . 40 . . 19 . 18 . 17 . 16 . .
(d) = dwarsgang (e) Een blok is een ruimte in het magazijn begrensd door twee opeenvolgende dwarsgangen
71 70 69 68 47 46 45 44 23 22 21 20
(e)
Bijlage 2: Berekening van het kortste pad tussen twee opslaglocaties We geven grafisch en wiskundig weer wat het kortste pad (MinAfst) is tussen twee willekeurige opslaglocaties in het magazijn. Omwille van de overzichtelijkheid onderscheiden we drie situaties. 2.1 De twee opslaglocaties bevinden zich in hetzelfde blok
A . . . . . .
3 2 1 0
7 6 5 4
11 10 9 8
. . . . . .
15 14 13 12
. . . . . .
19 18 17 16
23 22 21 20
B
In bovenstaand voorbeeld zoeken we het kortste pad tussen opslaglocatie 3 en opslaglocatie 17. De pikker heeft twee verschillende mogelijkheden. Ofwel reist hij via pad A (volle lijn), langs ‘boven’, ofwel neemt hij route B (stippellijn), langs ‘onder’. Wanneer (xi, yi) de coördinaten zijn van opslaglocatie i, yonder de y–coördinaat van de ‘onderste’ dwarsgang van het blok en yboven de y– coördinaat van de bovenste dwarsgang van dit blok, dan kunnen we wiskundig de minimale reisafstand bepalen tussen elke combinatie van 2 opslaglocaties i en j binnen hetzelfde blok: 𝑀𝑖𝑛𝐴𝑓𝑠𝑡 = 𝑥𝑖 − 𝑥𝑗 + 𝑀𝑖𝑛 𝑦𝑖 − 𝑦𝑜𝑛𝑑𝑒𝑟 + 𝑦𝑗 − 𝑦𝑜𝑛𝑑𝑒𝑟 , 𝑦𝑖 − 𝑦𝑏𝑜𝑣𝑒𝑛 + 𝑦𝑗 − 𝑦𝑏𝑜𝑣𝑒𝑛 2.2 De twee opslaglocaties bevinden zich in dezelfde langsgang of subgang
51 50 49 48 27 26 25 24 3 2 1 0
. . . . . . . . . . . . . . . .
55 54 53 52
59 58 57 56
31 30 29 28
35 34 33 32
7 6 5 4
11 10 9 8
. . . . . . . . . . . . . . . .
63 62 61 60
67 66 65 64
39 38 37 36
43 42 41 40
15 14 13 12
19 18 17 16
. . . . . . . . . . . . . . . .
71 70 69 68 47 46 45 44 23 22 21 20
Wanneer de twee opslaglocaties zich in dezelfde langsgang of subgang bevinden (bijvoorbeeld opslaglocatie 67 en 18 bevinden zich in dezelfde langsgang) is de berekening van MinAfst zeer eenvoudig: 𝑀𝑖𝑛𝐴𝑓𝑠𝑡 = 𝑦𝑖 − 𝑦𝑗
2.3 De twee opslaglocaties bevinden zich in een verschillend blok Opslaglocatie 10 en 49 bevinden zich in een verschillend blok en in een verschillende langsgang. De afstand tussen beide is eenvoudig te berekenen en ook grafisch (zie figuur) is het kortste pad eenvoudig te zien. Men zou dit kortste pad ook op een andere manier kunnen bereiken door vanaf opslaglocatie 10 in de eerstvolgende dwarsgang meteen naar links te gaan en op die manier via de eerste langsgang naar opslaglocatie 49 te reizen. Dit is inderdaad ook een juist pad, maar in afstand zal dit hetzelfde zijn. Het doet er dus niet toe welke weg wordt gekozen. 𝑀𝑖𝑛𝐴𝑓𝑠𝑡 = 𝑦𝑖 − 𝑦𝑗 + 𝑥𝑖 − 𝑥𝑗
Bijlage 3: Uitgebreide S-shape voor een magazijn bestaande uit één of meerdere blokken Gebaseerd op Roodbergen en De Koster (2001a). Op onderstaande figuur is een voorbeeld van een S-shape routering weergegeven voor een pikker die de items op opslaglocaties 10, 18, 42, 46, 49, 57 en 67 moet ophalen.
51 50 49 48 27 26 25 24 3 2 1 0
. . . . . . . . . . . . . . . depot .
55 54 53 52
59 58 57 56
31 30 29 28
35 34 33 32
7 6 5 4
11 10 9 8
. . . . . . . . . . . . . . . .
63 62 61 60
67 66 65 64
39 38 37 36
43 42 41 40
15 14 13 12
19 18 17 16
. . . . . . . . . . . . . . . .
71 70 69 68 47 46 45 44 23 22 21 20
De onderstaande procedure voor de S-shape routering voor één of meerdere blokken (met een depot linksonder) komt overeen met figuur 14: Pseudocode S-shape heuristiek uit Theys en Herroelen (2005). De pseudocode is op zijn beurt gebaseerd op Roodbergen en De Koster (2001a). Stap 1: Start aan depot. Zoek meest linkse langsgang met producten. Ga erheen. Zoek verste blok met producten. Ga naar voorste dwarsgang verste blok. Stap2: for (huidig blok = verste blok, huidig blok exists, huidig blok + 1) Zoek in huidig blok meest linkse subgang met producten. Zoek in huidig blok meest rechtse subgang met producten. if (meest linkse subgang met producten is het dichtst) Ga naar meest linkse subgang met producten. while (nog subgangen met producten in blok) if (dit is laatste subgang met producten in blok) Ga naar verste element in subgang. Ga via huidige subgang naar voorste dwarsgang huidig blok. else Doorkruis subgang volledig. Ga naar volgende meest linkse subgang met producten. else if (meest rechtse subgang met producten is het dichtst) Ga naar meest rechtse subgang met producten.
while (nog subgangen met producten in blok) if (dit is laatste subgang met producten in blok) Ga naar verste element in subgang. Ga via huidige subgang naar voorste dwarsgang huidig blok. else Doorkruis subgang volledig. Ga naar volgende meest rechtse subgang met producten. else if (geen producten in het blok) Ga via huidige subgang naar voorste dwarsgang huidig blok. Stap 3: Ga naar depot.
Bijlage 4: Algemene procedure voor de toepassing van een seed algoritme Onderstaand schema is gebaseerd op de procedure voor het seed algoritme, beschreven in Ho en Tseng, 2006.
Bijlage 5: Uitbreiding van de batchingmethode van Clark en Wright (1964) door De Koster et al. (1999) Onderstaande beschrijving van de procedure is gebaseerd op de procedure voor CW (iii) beschreven in De Koster et al.(1999) Stap 0: Elk order uit de orderlijst wordt toegewezen aan een aparte batch. In het begin van de procedure zijn er dus evenveel batches als er orders waren. Ga naar stap 1. Stap 1: Bereken de besparingen voor alle verschillende combinaties van twee batches, gegeven de capaciteit. De besparing wordt berekend door het verschil te nemen tussen de reisafstand indien men de twee batches individueel zou pikken en indien men ze samen zou pikken, gegeven een routeringheuristiek. Bij de reisafstand (of reiskost) wordt eventueel een extra kost bijgeteld indien de orders individueel worden gepikt. Dit stelt dan de vaste kost van een batch voor. Ga naar stap 2. Stap 2: Selecteer het paar dat de grootste besparingen oplevert, enkele positieve besparingen kunnen geselecteerd worden. In het geval van een gelijkspel wordt ad random een paar gekozen. Ga naar stap 3. Stap 3: Ga naar Stap 1 indien in stap 2 twee batches zijn samengevoegd. Indien niet: stop. Het is meteen duidelijk dat bij elke iteratie de berekening van alle mogelijke besparingen minder tijd in beslag zal nemen. Het aantal mogelijke paren van twee batches daalt namelijk sterk naarmate het aantal batches daalt. De besparingenmatrix wordt dus alsmaar kleiner. Daarnaast moet ook voor verschillende paren geen besparing berekend worden aangezien een combinatie om capaciteitsredenen onmogelijk is.
Bijlage 6 / CD- ROM Het zou te omslachtig zijn om bijvoorbeeld de complete programmeercode of de SPSS bestanden af te printen in bijlage. Toch kan de lezer geïnteresseerd zijn in deze extra informatie of andere gegevens in verband met het onderzoek. Om die reden is bij het werkstuk een CD-ROM bijgevoegd waarop extra informatie te vinden is. Belangrijk is dat deze extra documenten de transparantie van het onderzoek waarborgen. Het complete simulatieprogramma, de output en al de SPSS outputbestanden worden namelijk beschikbaar gesteld. Volgende zaken staan in de map BIJLAGE 6 – CD ROM op de CD-ROM
De programmeercode voor de drie experimenten (Microsoft Visual Studio 2005) De onbewerkte outputbestanden voor de drie simulaties (tekstbestanden) SPSS output bestanden voor de drie experimenten (SPSS) Extra betrouwbaarheidsintervallen voor experiment 1 waarbij de methodes geordend zijn naargelang de prestatie (Microsoft Excel) Een groot deel van de wetenschappelijke artikels en andere bronnen waarop de literatuurstudie is gebaseerd (PDF formaat, Microsoft Word, Microsoft Powerpoint)
In elke afzonderlijke map staat een tekstdocument ‘leesMij’ met informatie over de bestanden in die map.
