UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2009 – 2010
Exacte oplossingsmethode voor order picker routing
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur
David Claus onder leiding van Prof. Birger Raa
2
UNIVERSITEIT GENT FACULTEIT ECONOMIE EN BEDRIJFSKUNDE ACADEMIEJAAR 2009 – 2010
Exacte oplossingsmethode voor order picker routing
Masterproef voorgedragen tot het bekomen van de graad van Master in de Toegepaste Economische Wetenschappen: Handelsingenieur
David Claus onder leiding van Prof. Birger Raa
3
PERMISSION Ondergetekende verklaart dat de inhoud van deze masterproef mag geraadpleegd en/of gereproduceerd worden, mits bronvermelding.
David Claus
4
Voorwoord Het schrijven van deze scriptie is een leerrijke ervaring geweest die mij zowel heeft toegestaan een verder begrip te krijgen over de wereld van de logistiek als over het programmeren van algoritmes. Zonder de hulp van vele mensen had ik deze scriptie nooit tot een goed einde kunnen brengen. Bij deze wens ik ze dan ook allemaal te bedanken.
Mijn promotor professor Birger Raa voor de begeleiding en het te allen tijde opheffen van anders onoverwinnelijke barrières.
Professor Wout Dullaert voor de aanwijzingen en verbeteringen die mij in staat hebben gesteld het werk verder te verbeteren.
Hendrik Slabbinck, assistent aan de UGent, die mij geholpen heeft met verscheidene statistische problemen.
En natuurlijk mijn familie en vriendin voor hun steun en eindeloos begrip.
I
Inhoudsopgave VOORWOORD............................................................................................................ I INHOUDSOPGAVE.................................................................................................... II FIGURENLIJST......................................................................................................... IV TABELLENLIJST...................................................................................................... VI INLEIDING ................................................................................................................. 1 1. Situering............................................................................................................................................................. 1 2.Doelstelling van de scriptie................................................................................................................................ 2 3.Opbouw van de scriptie ..................................................................................................................................... 2
HOOFDSTUK 1: ORDER PICKING : EEN INLEIDING ............................................. 4 a) b) c) d) e)
Opslag....................................................................................................................................................... 4 Zoning....................................................................................................................................................... 6 Batching.................................................................................................................................................... 6 Accumulatie en sorteren van orders.......................................................................................................... 7 Order picker routing ................................................................................................................................. 7
HOOFDSTUK 2 : ORDER PICKER ROUTING: HEURISTIEKEN ........................... 11 1. Heuristieken voor single-blok magazijnen.................................................................................................... 11 a) S-shape heuristiek ................................................................................................................................... 11 b) Return heuristiek..................................................................................................................................... 12 c) Mid-point heuristiek ............................................................................................................................... 13 d) Largest gap heuristiek............................................................................................................................. 13 e) Combined heuristiek ............................................................................................................................... 14 2. Heuristieken voor multi-blok magazijnen .................................................................................................... 15 a) S-shape heuristiek ................................................................................................................................... 15 b) Largest gap heuristiek............................................................................................................................. 16 c) Aisle-by-aisle heuristiek ......................................................................................................................... 16 d) Combined en combined+ heuristieken.................................................................................................... 17 e) Lin-Kernighan Travelling Salesman heuristiek ...................................................................................... 19 3. Voordelen van het gebruik van een optimale methode ten opzichte van een heuristiek........................... 20
HOOFDSTUK 3: ORDER PICKER ROUTING: OPTIMALE METHODEN............... 24 1.Het algoritme van Ratliff en Rosenthal voor single-blok magazijnen ......................................................... 24 2.Het algoritme van Roodbergen en de Koster voor magazijnen bestaande uit 2 blokken .......................... 31
HOOFDSTUK 4: OPTIMALE METHODES: EEN UITBREIDING ............................ 35 1.Voorbereidend werk ........................................................................................................................................ 36 a) Equivalentieklassen ................................................................................................................................ 36
II
b) c) d)
Tabellen om de rijen te vullen (Lj+ tabellen)........................................................................................... 38 Configuraties om van rij j naar rij j+1 over te gaan................................................................................ 38 Tabel om de overgang van rij j naar rij j+1 te maken (van Lj+ naar L(j+1)-) ............................................ 39
2.Uiteindelijke oplossing ..................................................................................................................................... 40
HOOFDSTUK 5: ANALYSE VAN DE UITBREIDING.............................................. 43 1.tijdsverschillen tussen de gebruikte methodes............................................................................................... 44 a) Branch and bound benchmark versus nieuwe methode (zonder clusteren) ............................................ 44 b) Branch en bound methode versus branch and bound methode met clusteren van de orders................... 50 c) Branch en bound methode met clusteren van de orders versus branch and bound methode met clusteren en reduceren ............................................................................................................................................ 52 d) De nieuwe methode zonder clusteren versus de nieuwe methode met clusteren .................................... 54 e) De branch and bound methode met clusteren en reduceren versus de nieuwe methode (zonder clusteren) ................................................................................................................................................................ 55 2.Verschillende methodes opgesplitst naar hun drivers .................................................................................. 56 a) branch en bound methode met clusteren en reduceren ........................................................................... 56 b) de nieuwe methode (zonder clusteren).................................................................................................... 59 3.Vergelijking van beide methoden ................................................................................................................... 63
BESLUIT .................................................................................................................. 66 REFERENTIES ........................................................................................................ VII APPENDIX A : INHOUD CD-ROM......................................................................... - 1 -
III
Figurenlijst Figuur 1.1: Illustratie van 2 gebruikelijke manieren van opslag gebaseerd op ABCclassificatie (de Koster et al. 2007) .................................................................................... 5 Figuur 1.2: Distributie van de tijd van een order picker (Tompkins et al., 2003)...................... 8 Figuur 1.3: multi-blok magazijn met parallelle rijen ................................................................. 8 Figuur 1.4: Termen in verband met order picking ..................................................................... 9 Figuur 2.1: Een voorbeeld van de S-shape heuristiek (Roodbergen, 2001)............................. 12 Figuur 2.2: Een voorbeeld van de return heuristiek (Roodbergen, 2001)................................ 12 Figuur 2.3: Een voorbeeld van de mid-point heuristiek (Roodbergen, 2001).......................... 13 Figuur 2.4: Een voorbeeld van de largest gap heuristiek (Roodbergen, 2001)........................ 14 Figuur 2.5: Een voorbeeld van de combined heuristiek (Roodbergen, 2001).......................... 14 Figuur 2.6: Een voorbeeld van de S-shape heuristiek voor multi-blok magazijnen (Roodbergen, 2001).......................................................................................................... 15 Figuur 2.7: Een voorbeeld van de largest gap heuristiek voor multi-blok magazijnen (Roodbergen, 2001).......................................................................................................... 16 Figuur 2.8: Een voorbeeld van de aisle-by-aisle heuristiek voor multi-blok magazijnen (Roodbergen, 2001).......................................................................................................... 17 Figuur 2.9: Een voorbeeld van de combined heuristiek voor multi-blok magazijnen (Roodbergen, 2001).......................................................................................................... 18 Figuur 2.10: Een voorbeeld van de combined+ heuristiek voor multi-blok magazijnen (Roodbergen, 2001).......................................................................................................... 19 Figuur 2.11: Vergelijking van verschillende heuristieken ten opzichte van de optimale methode met toenemend aantal rijen (Petersen, 1997) .................................................... 20 Figuur 2.12: Vergelijking van verschillende heuristieken ten opzichte van de optimale methode met toenemend aantal aantal te picken items (Petersen, 1997) ......................... 21 Figuur 2.13: Gemiddelde gevonden afstanden van verschillende heuristieken voor verschillende parameter waarden (Theys et al., 2010)..................................................... 23 Figuur 3.1: Voorbeeld van een single-blok magazijn (Ratliff en Rosenthal, 1983) ................ 25 Figuur 3.2: Omzetting van figuur 3.1 tot een graaf pesentatie (Ratliff en Rosenthal, 1983)... 26 Figuur 3.3: De zes mogelijke configuraties voor een rij (Ratliff en Rosenthal, 1983) ............ 28 Figuur 3.4: De vijf mogelijke configuraties om van rij j naar rij (j+1) over te gaan (Ratliff en Rosenthal, 1983)............................................................................................................... 29 Figuur 3.5: Omzetting van een magazijn met twee blokken naar een graaf (Roodbergen en de Koster, 2001).................................................................................................................... 31 Figuur 3.6: Mogelijke configuraties om van rij j naar rij j+1 te gaan in een magazijn met twee blokken (Roodbergen en de Koster, 2001)....................................................................... 34 Figuur 5.1: Boxplot branch and bound benchmark methode ................................................... 45 Figuur 5.2: Boxplot nieuwe methode....................................................................................... 46 Figuur 5.3: Histogram branch and bound methode.................................................................. 47 Figuur 5.4: Histogram nieuwe methode................................................................................... 47 Figuur 5.5: Boxplots nieuwe methode per blok ....................................................................... 48 Figuur 5.6: Boxplots van de branch and bound methode per blok .......................................... 48 Figuur 5.7: Boxplots branch and bound methode na clusteren van de orders ......................... 50 Figuur 5.8: Histogram branch and bound methode na clusteren van de orders ....................... 51 Figuur 5.9: Boxplot "clusteren en reduceren" methode ........................................................... 52 Figuur 5.10: Histogram "clusteren en reduceren" methode ..................................................... 53 Figuur 5.11: Exponentieel verloop van de tijd in functie van het aantal items (Applegate et al.) .......................................................................................................................................... 56 Figuur 5.12: Verloop van de tijd voor een klein aantal orders (Applegate et al.).................... 57 IV
Figuur 5.13: Verloop van de tijd voor verschillende drivers ("clusteren en reduceren" methode)........................................................................................................................... 57 Figuur 5.14: Verloop van de tijd voor verschillende drivers ("nieuwe methode") .................. 59 Figuur 5.15: Lineaire benadering van een exponentiële .......................................................... 60 Figuur 5.16: Beide methodes opgesplitst naar het aantal blokken ........................................... 63
V
Tabellenlijst Tabel 2.1: Gemiddelde loop- en totale tijden voor order pickers (de Koster en Van der Poort, 1998)................................................................................................................................. 21 Tabel 2.2: Procentuele verschillen tussen de optimale methode en de combined+ heuristiek (Roodbergen, 2001).......................................................................................................... 22 Tabel 3.1: Overgang van Lj- naar Lj+ (Ratliff en Rosenthal, 1983) ......................................... 28 Tabel 3.2:Overgang van Lj+ naar L(j+1)- (Ratliff en Rosenthal, 1983) ...................................... 30 Tabel 3.3: Overgang van Lj- naar Lj+y (Roodbergen en de Koster, 2001) ................................ 33 Tabel 3.4: Overgang van Lj+y naar Lj+x (Roodbergen en de Koster, 2001) ........................... 33 Tabel 3.5: Overgang van Lj+x naar Lj- (Roodbergen en de Koster, 2001) ................................ 34
VI
Inleiding
1. Situering Alhoewel automatisering steeds meer de kop opsteekt is order picking een voornamelijk manueel proces. Gezien de nood aan continue verbetering en het streven naar een steeds efficiëntere economie is het minimaliseren van overbodige handelingen een topic met groeiende aandacht. Wanneer de order pickers door het magazijn wandelen, op zoek naar de items op hun picklist, zijn zij dus in se bezig met een nutteloze activiteit (zonder toegevoegde waarde). Elke vermindering van de wandelafstand is dan ook een directe tijdswinst die het bedrijf zal helpen in haar zoektocht naar efficiëntie.
Vandaag de dag wordt aan de hand van heuristieken gezocht naar een efficiënte routing. Dit omwille van verschillende redenen. Zo kan het volgens de Koster, Le-Duc en Roodbergen (2007) zijn dat optimale methoden voor die particuliere layout van het magazijn nog niet bestaan. Ook zijn de meeste heuristieken veel intuïtiever dan optimale methoden. Van optimale trajecten kan bijvoorbeeld afgeweken worden omdat de order picker de logica hiervan niet inziet. Tevens zijn heuristieken soms, meer dan optimale methoden, in staat om opstopping in drukbezochte delen van het magazijn te vermijden. Optimale methoden hebben daarentegen het voordeel korter te zijn en kunnen de wandelafstand dus verkorten.
Onderzoek naar optimale methoden is reeds gebeurd door Ratliff en Rosenthal (1983), en Roodbergen en de Koster (2001b) doch hun optimale methoden beperken zich tot een specifieke (maar veelvoorkomende) layout. Hun methode kan dan ook toegepast worden op respectievelijk magazijnen bestaande uit één blok (voor de betekenis van deze en andere magazijnspecifieke termen in verband met order picking wordt verwezen naar figuur 1.4, p 9) en magazijnen bestaande uit twee blokken.
1
2.Doelstelling van de scriptie Het doel van deze scriptie is dan ook om eerst een korte beschrijving te geven van de bestaande literatuur en oplossingen terzake en vervolgens deze uit te breiden door een algoritme voor te stellen dat is staat is een optimale oplossing te genereren voor magazijnen bestaande uit meerdere blokken. Aangezien het aantal magazijnen dat uit vele blokken bestaan in de praktijk beperkt zijn zal er, bij de analyse van de methode, dan ook enkel aandacht worden geschonken aan magazijnen met een beperkt (realistisch) aantal blokken.
3.Opbouw van de scriptie In het eerste hoofdstuk wordt getracht een omschrijving van het begrip order picking te geven evenals een ontleding in zijn verschillende componenten. Op deze manier wordt eerst een ruimer kader geschetst waarna specifiek op order picking routing kan worden ingegaan. Zo worden de begrippen opslag, zoning, batching en accumulatie en sorteren van orders eerst kort besproken. Teneinde alle onduidelijkheid in de volgende hoofdstukken te minimaliseren wordt op het einde van dit eerste hoofdstuk geopteerd voor een korte uiteenzetting van de nomenclatuur die in deze scriptie wordt gebruikt.
Alvorens dieper in te gaan op de uiteindelijke kern van deze scriptie wordt in het tweede hoofdstuk een kort overzicht gegeven van verscheidene bestaande heuristieken en hun voordelen. Een onderverdeling wordt gemaakt naargelang het heuristieken voor single-blok magazijnen betreft of multi-blok magazijnen. Zo worden ondermeer de S-shape, midpoint en largest gap heuristiek besproken evenals de meer gesofistikeerde combined en combined + heuristieken.
In het volgende hoofdstuk wordt bestaande literatuur in verband met optimale methodes voor order picker routing uitgebreid besproken. Hoewel de bestaande literatuur beperkt is en slechts uit een tweetal papers bestaat is deze informatie cruciaal voor het verdere verloop van de scriptie. Ook in de hierop volgende hoofdstukken zal geregeld naar deze informatie verwezen worden.
2
Teneinde een optimale methode voor order picker routing in multi-blok magazijnen te ontwikkelen werd de methode, besproken in het vorig hoofdstuk, uitgebreid. De verschillen met voorgaand onderzoek worden aangekaart en bondig besproken. Tevens wordt een onderscheidt gemaakt tussen voorbereidend werk, zijnde noodzakelijke tussenstappen, en de uiteindelijke oplossing, het algoritme dat een kortste weg kan vinden in een multi-blok magazijn.
In het vijfde en laatste hoofdstuk wordt tenslotte deze nieuw ontwikkelde methode gebenchmarked met een reeds bestaande doch relatief onvoorspelbare (de rekentijden hebben een hoge variantie, (zie infra, hfst 5)) methode op basis van branch and bound. Op deze manier worden vlakken waar de nieuwe methode beter, even goed of slechter presteert in perspectief gezet. Er wordt een vergelijkende analyse gemaakt waarbij gemiddelde rekentijden en hun varianties worden vergeleken voor de verschillende methodes en voor varianties op deze methodes. Tevens zullen deze methodes meer in detail bestudeerd worden en zullen de rekentijden naar hun bestandsdelen worden opgesplitst om tot betere inzichten te komen waar en wanneer welke methode het best gebruikt wordt.
3
Hoofdstuk 1: order picking : een inleiding Het begrip order picking kan als volgt omschreven worden: het proces van producten uit de opslag halen ten gevolge van een specifieke vraag door een klant. (de Koster et al.,2007). Ook vandaag de dag, waar geautomatiseerde systemen steeds meer de kop opsteken, blijft handmatig order picken de standaard. Tevens kan deze operatie tot 55% van de totale kosten in warehousing uitmaken (Tompkins et al.,1996, Roodbergen en de Koster, 2001b, de Koster et al., 2007) die op zijn beurt tot 20% van de logistieke kosten van een bedrijf omvatten. Order picking wordt beïnvloed door zowel externe als interne factoren. Volgens Goetschalckx en Ashayeri (1989) bestaan deze externe factoren uit de keuze van marketingkanalen, het patroon van de vraag en de bevoorrading, het voorraadniveau, de totale vraag naar het product en de bloei van de economie. Interne factoren bestaan dan weer uit karakteristieken van het systeem (zoals de graad van mechanisering, de beschikbaarheid van informatie en de layout van het magazijn), de organisatie en het operationeel beleid inzake order picking systemen. In de rest van dit hoofdstuk zullen de vijf voornaamste elementen van deze laatste interne factor kort toegelicht worden (cfr. De Koster et al. (2007)).
a)
Opslag
Vaak wordt beslist om niet de volledige stock in de order pick ruimte op te slaan. In plaats daarvan wordt een groot deel van de voorraad in een reserveplaats ondergebracht. Dit om de order pick ruimte te verkleinen en efficiëntere pick tijden te bekomen. Het herbevoorraden van de pick ruimte kan op andere tijdstippen gebeuren. Het blijft echter een delicate zaak om de goede balans te vinden tussen het herbevoorraden van de pick ruimte en de reductie in order pick tijd. Het is daarenboven niet onmogelijk dat bepaalde stock keeping units enkel in de reserveopslag voorkomen (bijvoorbeeld indien zij zelden gevraagd worden of enkel in grote hoeveelheden). Oplossingen voor dit probleem worden gegeven door Frazelle et all.(1994), Hackman en Platzman (1990), Van den Berg en Sharp (1998) en Bartholdi en Hackman (2005). Een andere beslissing over de opslag van goederen is waar ze exact op te slaan. Wanneer een nieuw pallet goederen wordt binnengebracht, moet het dan naar een specifieke locatie gebracht worden of krijgt het gewoon een random plaats toegewezen? Het spreekt vanzelf dat er tussen deze twee extremen een heel spectrum aan mogelijkheden ligt. Zo kan men beslissen
4
een pallet goederen onder te brengen bij de dichtst bijzijnde open plaats, een andere methode van opslag te gebruiken voor de order pick ruimte en de reserve plaats, enzovoorts. Een van deze methodes verdient echter bijzondere aandacht namelijk ABC-classificatie. In dit geval worden de goederen in 3 (of meerdere al naar gelang) klassen onderverdeeld in functie van hun aandeel in de verkoop of hun pickfrequentie. Het is alom bekend dat ongeveer 15% van de opgeslagen producten voor ongeveer 85% van de omzet verantwoordelijk kunnen zijn. Men zal dan deze klasse aan producten A-items noemen, de volgende klasse (bestaande uit deze producten die net iets minder frequent worden gepikt of afhankelijk van de maatstaf een lagere beoordeling krijgen) B-items enzovoort. A-items worden zo dicht mogelijk bij het depot gezet om de pick tijd te verminderen. Deze manier van klassen aanmaken kan tot in het oneindige worden doorgedreven tot voor elk product een klasse is aangemaakt. Deze klassen zijn echter niet statisch en het herberekenen hiervan kan veel tijd in beslag nemen. In de praktijk beperkt men zich voorts tot een drietal klassen. Figuur 1 geeft meer uitleg omtrent de praktische implementatie.
Figuur 1.1: Illustratie van 2 gebruikelijke manieren van opslag gebaseerd op ABC-classificatie (de Koster et al. 2007)
Een laatste aandachtspunt is het feit dat er een relatie kan bestaan tussen verschillende producten. Zo worden bepaalde items vaker samen gekocht en bevinden zij zich dus in hetzelfde order. (Een koffiezetapparaat kan bijvoorbeeld vaak samen met koffiefilters gekocht worden). Er bestaat dus een duidelijk voordeel indien men deze producten vooraf clustert en op nabije locaties opslaat. Op deze manier kan de wandelafstand van de order picker substantieel worden verkort. Verdere informatie over het onderwerp wordt verstrekt door Frazelle en Sharp (1989) en Brynzér en Johansson (1996).
5
b)
Zoning
In plaats van een order in zijn geheel door één order picker te laten ophalen kan men de order pick ruimte in zones verdelen. Elke order picker blijft dan in zijn zone en pickt dat deel van het order dat daar ligt. De voordelen van deze methode zijn een kortere wandelafstand voor de order picker en het feit dat deze persoon zich gemakkelijker met zijn zone zal familiariseren. Het nadeel is natuurlijk dat deze deelorders op het einde van de rit weer samengebracht moeten worden om naar de klant te kunnen worden verstuurd. Om dit op te lossen bestaan er verscheidene alternatieven. In een “pick and pass” systeem zal een order picker telkens in zijn zone een order verder aanvullen alvorens het mandje met de orders en het lijstje met te picken orders door te geven aan de order picker van de volgende zone. Om de grootte van de zones te bepalen (wanneer items enkel uit één rek moeten gepickt worden) kan men bijvoorbeeld gebruik maken van “bucket brigades”. Deze manier balanceert de werklast door de order picker op te dragen het order aan de volgende order picker door te geven wanneer zij elkaar tegen komen. Bij “parallel picking” zal elke order picker tegelijk aan hetzelfde order picken waarna alle bestanddelen worden samengebracht. Literatuur is beschikbaar om uit te vissen welk aantal zones optimaal zou zijn (Le-Duc en De Koster, 2005a ) en welke producten net in welke zones moeten ondergebracht worden (Jewkes, Lee, Vickson, 2004 ).
c)
Batching
Wanneer elk order uit een groot aantal items bestaat dan zal de order picker gedurende zijn ronde slechts één order verzamelen (single picking tour). Het kan echter voorkomen dat orders uit een beperkt aantal items bestaan. In dit geval kan men tijd besparen door orders te groeperen en tijdens één en dezelfde ronde op te halen. Het groeperen van zulke orders noemt men “order batching”. Welke orders samen gepickt zullen worden hangt af van twee criteria. Een eerste criteria is natuurlijk het tijdsinterval waarop deze orders toekomen (time window batching). Men zal namelijk de orders die tijdens dezelfde tijdspanne toekomen in één batch onderbrengen. Deze orders zullen onderverdeeld worden in groepen van orders (of delen van orders) die samen gepickt moeten worden. Afhankelijk van het feit of orders over verschillende order picking toeren mogen uitgesplitst worden of niet kan men orders tijdens het afhalen sorteren of moet dit nadien gebeuren. Men spreekt respectievelijk van “sort-whilepick” en “pick-and-sort”. Verdere oplossingen en literatuur over dit onderwerp worden onder andere gegeven door Tang en Chew (1997), Chew en Tang (1999) en Le-Duc en De Koster
6
(2003, 2007). Het tweede criteria bestaat eruit om deze orders samen te picken die voor een groot deel uit dezelfde items bestaan of uit items die dicht bij elkaar liggen (proximity batching). Op deze manier kan de wandelafstand verkort worden. Heuristieken om dit op te lossen worden gegeven door Gademann, Van den Berg en Van der Hoff (2001), Gademann en Van de Velde (2005), Chen en Wu (2005), Chen, M. C., Huang, Chen, K. I., en Wu. (2005) en Hsu, Chen, K. I., Chen, M. C., (2005).
d)
Accumulatie en sorteren van orders
Indien men zoals vooraf besproken in punt b en c beslist eenzelfde order door verschillende order pickers te laten ophalen is er een manier nodig om deze delen van eenzelfde order weer bij elkaar te voegen. Een veelgebruikte methode is om al deze delen van orders op een circulaire lopende band te plaatsen. Aan deze band zijn een aantal terminals verbonden die één of meerdere orders kunnen bevatten. Een nieuw order kan zo slechts een terminal binnen komen indien alle delen van het voorgaande order deze terminal al zijn binnengekomen. (Het spreekt vanzelf dat een order één en slechts één terminal krijgt toegewezen). Indien dit nog niet het geval is zal het deelorder blijven ronddraaien op de circulair lopende band. Le-Duc en De Koster (2005a) bieden een oplossing om de gezamenlijke order-pick tijd en sorteringstijd te minimaliseren. Verdere literatuur wordt gegeven door Bozer en Sharp (1985), Bozer, Quiroz en Sharp (1988) en Johnson (1998), Johnson en Lofgren (1994), Meller (1997) en Russel en Meller (2003).
e)
Order picker routing
Dit deel zal in de volgende hoofdstukken uitgebreid aan bod komen aangezien dit het onderwerp van dit proefstuk is. Het betreft het optimaliseren van de wandelafstand van de order picker bij het afhalen van een order bestaande uit verschillende items. Hiertoe moeten de op te halen items geordend worden zodat de totaal te doorlopen afstand geminimaliseerd wordt. Onderstaande grafiek geeft de distributie aan van de tijd van een order picker. Zoals aangetoond bestaat deze tijd voor 50% uit wandeltijd (zie figuur 1.2). Dit levert op zichzelf geen toegevoegde waarde en wordt dus best zoveel mogelijk beperkt.
7
Figuur 1.2: Distributie van de tijd van een order picker (Tompkins et al., 2003)
In het vervolg van dit werkstuk zal men uitgaan van een zogenaamde “multi-blok, parallelaisle warehouse” layout. Deze layout betsaat uit één of meerdere blokken, van elkaar gescheiden door “cross-aisles” of tussengangen. Deze blokken bestaan op hun beurt uit een reeks parallelle rijen waarlangs de goederen staan opgeslaan. Een voorbeeld wordt gegeven door onderstaande figuur.
Figuur 1.3: multi-blok magazijn met parallelle rijen
Verschillende variaties kunnen optreden. Zo kunnen de schappen waarvan de order picker items moet nemen dicht genoeg bij elkaar staan om de order picker toe te laten om items te picken zowel links als rechts van hem zonder wezenlijke afstand te moeten afleggen (in het vervolg van dit werkstuk gaan we er van uit dat dit inderdaad het geval is). Een oplossing
8
voor brede rijen wordt gegeven door Goetschalckx en Ratliff (1988b). Een order picker kan ook met een voertuig door het magazijn rijden. In dit geval moeten de ideale stoptijden van de wagen bepaald worden. Een optimale oplossing voor dit probleem wordt eveneens gegeven door Goetsschalckx en Ratliff (1988a). Ook kan het gebeuren dat men items kan deponeren op een lopende band aan de uiteinden van de rijen en dat het dus niet noodzakelijk is om helemaal terug te keren naar het depot (de Koster en Van de Poort, 1998).
Aan de hand van onderstaande figuur zal getracht worden alle relevante termen in verband met order picker routing te verduidelijken om dubbelzinnigheid te vermijden in de volgende hoofdstukken.
Figuur 1.4: Termen in verband met order picking
9
Een blok is dus een verzameling van parallelle rijen en wordt van een ander blok gescheiden door een tussengang (bovenstaand magazijn bestaat uit 3 blokken). Andere gangen zijn de onderste gang en de bovenste gang die respectievelijk het dichtst en het verst van het depot zijn gelegen. Een rij is dus een plaats waar men tussen de schappen heen kan lopen. Bovenstaande figuur bestaat uit 5 rijen. Elke rij bestaat uit een aantal subrijen. Er zijn evenveel subrijen in een rij als er blokken in het magazijn zijn. Elke subrij wordt dan weer gekarakteriseerd door het aantal pickplaatsen (9 per tussenrij in figuur 1.4). Op elke pickplaats kan er dan weer een te picken item liggen (in het zwart aangeduid). Alle te picken items samen (alle in het zwart aangeduide vakjes) vormen een order en moeten dus in één tour opgehaald worden.
Doel van deze thesis is het vinden van een methode die de kortste weg doorheen een magazijn met een willekeurig aantal blokken vindt en alle te picken items afgaat.
10
Hoofdstuk 2 : order picker routing: heuristieken Vaak wordt beslist om gebruik te maken van een heuristiek bij het plannen van de route van de order picker. Volgens de Koster et al. (2007) kan dit omwille van verschillende redenen. Er kan bijvoorbeeld geen optimale methode gekend zijn voor die particuliere layout van het magazijn. Tevens kunnen optimale routes soms onlogisch lijken voor de order pickers met als direct gevolg dat ze van het voorgeschreven traject afwijken. Ten slotte kunnen sommige heuristieken (zoals de S-shape heuristic) vermijden dat sommige gangen te druk bezocht worden en dus verstopping in smalle gangen verminderen. Volgens Roodbergen (2001) moet hier aan toegevoegd worden dat heuristieken gemakkelijker aanpasbaar zijn bij veranderende layout dan methodes die optimale oplossingen genereren. In wat volgt zullen in navolging van Roodbergen (2001) eerst kort een aantal heuristieken voor single-blok magazijnen (magazijnen zonder cross-aisle of tussengang) worden besproken en vervolgens een aantal voor multi-blok magazijnen.
1. Heuristieken voor single-blok magazijnen
a)
S-shape heuristiek
Dit is een van de simpelste maar ook meest gebruikte heuristieken in order picker routing. De bedoeling is dat de order picker elke rij inloopt waar ten minste één order moet gepickt worden en deze vervolgens helemaal tot het einde doorloopt. Na alle rijen op deze manier te zijn afgelopen keert hij terug naar het depot. Onderstaande figuur bevat een voorbeeld van de S-shape heuristiek. De blauw gekleurde vakjes zijn items die de order picker moet afhalen en de stippellijn is de afgelegde weg volgens deze heuristiek. (Roodbergen, 2001)
11
Figuur 2.1: Een voorbeeld van de S-shape heuristiek (Roodbergen, 2001)
b)
Return heuristiek
Bij deze eveneens simpele heuristiek is het de bedoeling elke rij in te lopen waar een item moet gepickt worden en er dan steeds langs dezelfde kant terug uit te lopen. Deze methode zal verkozen worden boven de S-shape heuristiek indien men in de onmogelijkheid verkeert de bovenste gang te gebruiken of indien men met brede rijen te maken heeft en het dus voordeliger is telkens slechts van één kant van de rij items af te halen (Goetschalckx en Ratliff, 1988a). Onderstaande figuur toont een voorbeeld van de return heuristiek. (Roodbergen, 2001)
Figuur 2.2: Een voorbeeld van de return heuristiek (Roodbergen, 2001)
12
c)
Mid-point heuristiek
Bij deze heuristiek verdeelt men het magazijn virtueel in twee delen. Items die zich in het onderste deel van het magazijn bevinden worden bezocht vanuit de onderste gang, de andere items vanuit de bovenste gang. Nooit wordt de virtuele scheidingslijn in het midden van het magazijn overgestoken behalve in de laatste en de eerste rij. Onderstaande figuur beeldt dit uit. (Roodbergen, 2001)
Figuur 2.3: Een voorbeeld van de mid-point heuristiek (Roodbergen, 2001)
d)
Largest gap heuristiek
Deze methode is ongeveer dezelfde als de mid-point heuristiek. Alleen is er hier geen sprake van een virtuele scheidingslijn en wordt voor elke rij de “largest gap” bepaald. Dit is de grootst mogelijke afstand tussen twee individuele items van een rij. Men zal vervolgens deze rij inslaan (langs beide kanten) tot op het punt van deze largest gap. Deze heuristiek vergt dus weliswaar meer rekentijd dan de mid-point heuristiek maar zal in alle gevallen korter (of op zijn minst even lang) zijn. Onderstaande figuur toont de route van de largest gap heuristiek. (Roodbergen, 2001)
13
Figuur 2.4: Een voorbeeld van de largest gap heuristiek (Roodbergen, 2001)
e)
Combined heuristiek
Deze heuristiek maakt gebruik van dynamisch programmeren (het opsplitsen van één complex probleem in meerdere gemakkelijker op te lossen subproblemen) om te kiezen of hij een rij volledig door zal lopen of slechts tot aan het verste item in die rij zal gaan en dan terug zal keren. Deze keuze zal gemaakt worden op basis van de items in de rij maar ook door de startpositie die vervolgens verkregen wordt voor de volgende rij. Onderstaande figuur geeft een voorbeeld van deze heuristiek. (Roodbergen, 2001)
Figuur 2.5: Een voorbeeld van de combined heuristiek (Roodbergen, 2001)
14
2. Heuristieken voor multi-blok magazijnen
a)
S-shape heuristiek
Indien men de S-shape heuristiek voor meerdere blokken toepast moet de order picker eerst naar het verste blok (gemeten van het depot) dat een te picken item bevat, stappen. Daar zal hij de S-shape heuristiek uitvoeren zoals voor een single-blok magazijn. Met dat verschil dat hij bij de laatste subrij van dit blok dat een item bevat terug zal moeten keren naar de tussengang het dichtst bij het depot gelegen. De order picker zal dan naar de meest linkse of meest rechtse (welkeen van de twee het dichtst bij ligt) subrij van het volgende blok dat een nog niet gepickt item bevat stappen en de procedure herbeginnen tot alle items gepickt zijn. Daarna zal hij naar het depot terugkeren. Een meer gedetailleerde beschrijving van deze manier wordt gegeven door Roodbergen (2001). Hieronder staat een figuur dat het bovenstaande verduidelijkt.
Figuur 2.6: Een voorbeeld van de S-shape heuristiek voor multi-blok magazijnen (Roodbergen, 2001)
15
b)
Largest gap heuristiek
Bij deze heuristiek wordt eerst naar het blok dat het verst van het depot verwijderd is (en dat te picken items bevat) gestapt. Vervolgens wordt op dat blok de largest gap heuristiek toegepast identiek als werd uitgelegd bij single-blok magazijnen. Voor het volgende blok zal men dan beginnen vanaf die subrij die het meest links of rechts gelegen (welkeen van de twee het dichtst bij ligt) is en nog een te picken item bevat. Een meer gedetailleerde beschrijving wordt gegeven door Roodbergen (2001). Hieronder wordt een voorbeeld gegeven van deze heuristiek.
Figuur 2.7: Een voorbeeld van de largest gap heuristiek voor multi-blok magazijnen (Roodbergen, 2001)
c)
Aisle-by-aisle heuristiek
Deze heuristiek, besproken in Vaughan en Petersen (1999) stelt voor om elke rij maar éénmaal te doorlopen. Gebruik makend van dynamisch programmeren wordt op deze manier een route getekend. Men zal eerst alle items picken in de eerste rij, vervolgens alle afstanden
16
berekenen indien men via één van de tussengangen, begin- of eindgang naar de volgende rij stapt om daar alle items op te halen en vervolgens alle afstanden berekenen indien men via één van de volgende tussengangen, begin- of hoofdgang naar de volgende rij zou stappen. Op deze manier wordt de weg gekozen die men in de eerste rij aflegt. Deze procedure kan vervolgens voor alle volgende rijen herhaald worden. Een meer gedetailleerde beschrijving wordt gegeven door Roodbergen (2001). Onderstaande figuur verduidelijkt deze heuristiek.
Figuur 2.8: Een voorbeeld van de aisle-by-aisle heuristiek voor multi-blok magazijnen (Roodbergen, 2001)
d)
Combined en combined+ heuristieken
Ook in deze heuristiek wordt gebruik gemaakt van dynamisch programeren. De exacte methode wordt beschreven door Roodbergen (2001). Samenvattend kan men zeggen dat er eerst naar het blok het verst verwijderd van het depot waaruit een item moet worden gepickt, wordt gegaan. Van daaruit wordt elke subrij van dit blok aangedaan waarna men naar het volgende blok gaat om deze procedure te herhalen. Verbeteringen hierop worden gegeven door de combined+ heuristiek. Hierbij stelt men dat men het blok het dichtst bij het depot steeds naar het depot toewerkend moet afgaan. Tevens kunnen bij het bewegen naar het verst 17
verwijderde blok en terug naar het dichtstbijzijnde blok meerdere rijen tegelijk in ogenschouw worden genomen. Onderstaande voorbeelden geven de routes bepaald door de combined en combined+ heuristieken.
Figuur 2.9: Een voorbeeld van de combined heuristiek voor multi-blok magazijnen (Roodbergen, 2001)
18
Figuur 2.10: Een voorbeeld van de combined+ heuristiek voor multi-blok magazijnen (Roodbergen, 2001)
e)
Lin-Kernighan Travelling Salesman heuristiek
Theys, Bräysy, Dullaert en Raa (2010) stellen voor om het probleem te beschouwen als een travelling salesman problem (TSP) en aldus op te lossen. Een eerste stap hiertoe is het berekenen van een symmetrische afstandsmatrix die de afstanden tussen de verschillende op te halen items bevat. Hiertoe kan men eenvoudigweg de Manhattan afstand gebruiken (x1-x2, y1-y2). Voor items die in verschillende rijen maar in hetzelfde blok zitten moet echter een andere methode worden toegepast. Daar bepaalt men op twee manieren de afstand en kiest men de kortste. Na deze eerste stap wordt de symmetrische afstandsmatrix onderworpen aan bestaande TSP-heuristieken. Theys et al. (2010) stellen voor om de Lin-Kernighan Travelling Salesman heuristiek te gebruiken. Zo slagen ze er in om (ten koste van langere maar acceptabele rekentijden) afstanden te vinden die beduidend korter zijn dan voornoemde heuristieken .
19
3. Voordelen van het gebruik van een optimale methode ten opzichte van een heuristiek In het begin van dit hoofdstuk werden verschillende voordelen van heuristieken opgesomd over optimale methodes. Het voordeel dat een optimale methode echter biedt is duidelijk: kortere routes. De vraag blijft natuurlijk in welke mate een optimale methode beter presteert dan de voorgestelde heuristieken. Alvorens in volgend hoofdstuk dieper in te gaan op hoe optimale routes berekend kunnen worden zal hier eerst dieper ingegaan worden op hoeveel korter deze routes nu eigenlijk zijn.
Een eerste inzicht wordt gegeven door Petersen (1997). Hoewel zijn analyse zich beperkt tot magazijnen bestaande uit één blok kunnen hier al belangrijke conclusies getrokken worden. Zo werd geanalyseerd hoe een optimale methode (O) zich verhoudt ten aanzien van de return (R), S-shape (ook wel transversal genoemd, T), midpoint (M), largest gap (LG) en combined (C) heuristiek naarmate het aantal te picken items of het aantal rijen toeneemt. Deze conclusies worden samengevat in de volgende grafieken waaruit de superioriteit van de optimale methode duidelijk blijkt.
Figuur 2.11: Vergelijking van verschillende heuristieken ten opzichte van de optimale methode met toenemend aantal rijen (Petersen, 1997)
20
Figuur 2.12: Vergelijking van verschillende heuristieken ten opzichte van de optimale methode met toenemend aantal aantal te picken items (Petersen, 1997)
Uit beide grafieken blijkt duidelijk dat de return heuristiek het slechtst presteert. Het wordt dan ook aangeraden om deze heuristiek enkel in voornoemde gevallen van brede rijen of het ontbreken van een bovenste gang te gebruiken. Verder blijkt dat de S-shape heuristiek aan kracht wint naarmate het aantal te picken items toeneemt (wat logisch is gezien in zulks geval steeds meer rijen sowieso volledig doorgelopen zullen moeten worden). Wanneer men alleen naar de heuristieken kijkt ziet men dat de combined heuristiek over het algemeen te prefereren is. Concrete cijfers worden gegeven door de Koster en Van der Poort (1998). In onderstaande tabel merkt men eveneens de voordelen van een optimale methode ten opzichte van de Sshape heuristiek. Naarmate het aantal rijen toeneemt worden de verschillen belangrijker.
Tabel 2.1: Gemiddelde loop- en totale tijden voor order pickers (de Koster en Van der Poort, 1998)
21
Aangezien het doel van deze scriptie bestaat uit het vinden van een optimale methode voor magazijnen bestaande uit meerdere blokken zal ook een korte analyse worden gemaakt van de voordelen van optimale methoden in multi-blok magazijnen.
Roodbergen (2001) concludeert dat de combined+ methode in de meeste gevallen alle andere heuristieken zal overtreffen (hierbij werd weliswaar de Lin-Kernighan Traveling Salesman heuristiek niet beschouwd). Voor kleine picklists waren de verschillen tussen de optimale methode en de combined+ heuristiek beperkt (rond de 7% voor picklists van 10 items). Tevens nam het verschil toe met het aantal rijen. Als conclusie stelt Roodbergen dat hoe complexer het probleem wordt hoe meer een optimale methode voordeel kan brengen.
Hieronder wordt een tabel opgenomen die de verschillen tussen de combined+ methode en de optimale methode weergeeft. “length” geeft de lengte van de rijen aan. Naarmate het aantal tussengangen toeneemt, vermindert dus de lengte van de subrijen. De grootste verschillen worden waargenomen daar waar de order picker meer routes zou kunnen inslaan. Een maximaal verschil wordt gemeten van 24,6 % voor vijftien rijen, picklists van dertig items en een rijlengte van 10 meter.
Tabel 2.2: Procentuele verschillen tussen de optimale methode en de combined+ heuristiek (Roodbergen, 2001)
22
In een recentere studie over het onderwerp vonden Theys et al. (2010) dat het gebruik van de Lin-Kernighan Traveling Salesman heuristiek tot nog veel grotere verbeteringen leidde dan de combined+ methode. Zo werd een gemiddelde afwijking van slechts 0.1 % van het optimum gevonden. Onderstaande grafieken verschaffen meer inzicht in de gerealiseerde verbeteringen opgesplitst naar verschillende parameters.
Figuur 2.13: Gemiddelde gevonden afstanden van verschillende heuristieken voor verschillende parameter waarden (Theys et al., 2010)
23
Hoofdstuk 3: order picker routing: optimale methoden Wat optimale methoden voor order picking routing betreft is de literatuur eerder beperkt. Slechts twee methodes zijn bekend.
1)
Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling
Salesman Problem (Ratliff an Rosenthal (1983))
2)
Routing order pickers in a warehouse with a middle aisle (Roodbergen en de Koster
(2001b))
Hierbij is de tweede bespreking een uitbreiding van de eerste. Ratliff en Rosenthal ontwikkelden een algoritme voor een magazijn (met specifieke layout) bestaande uit één blok. Roodbergen en de Koster breidden deze methode uit tot magazijnen bestaande uit 2 blokken (dus met één tussengang). Hieronder zal kort uitgelegd worden wat deze methodes inhouden en hoe men hiermee tot een optimale (kortste) weg komt.
1.Het algoritme van Ratliff en Rosenthal voor single-blok magazijnen Dit algoritme biedt een exacte oplossing voor de eerder besproken single-blok magazijnen. Dit zijn magazijnen bestaande uit een discreet aantal parallelle rijen waarlangs goederen (items) staan opgeslagen. Onderaan het magazijn (langs de kant van het depot) bevindt zich de onderste gang en bovenaan bevindt zich de bovenste gang. In de onderste en bovenste gang zijn per definitie geen goederen opgeslagen. De bedoeling is dus om door deze rijen de kortste weg te vinden, beginnend en eindigend bij het depot, die alle items aandoet (afhaalt). In onderstaande bespreking beperken we ons tot een praktische beschrijving. Voor verdere bewijzen verwijzen we dan ook naar Ratliff en Rosenthal (1983).
De eerste stap van dit algoritme bestaat erin om de layout van het magazijn om te zetten tot een graaf presentatie (zie figuur 3.1. en figuur 3.2.). Hierbij stellen de knopen aangeduid met de letter a de bovenste punten van rijen voor. De knopen aangeduid met de letter b stellen dan weer de onderste punten van deze rijen voor. Beide soorten knopen mogen worden aangedaan
24
door de order picker maar zijn optioneel. De knopen met letter v daarentegen stellen de items uit de eerste figuur voor en moeten dus wel verplicht worden aangedaan (zoniet heeft de order picker niet alle items uit zijn op halen order kunnen afhalen). Ook het depot wordt met de letter v aangeduid aangezien het ook verplicht moet worden meegerekend (start-en eindpunt). Omdat het depot niet in een rij gelegen is maar wel in de graaf moet worden opgenomen (om het model eenvoudig te houden wordt er beslist geen extra tak buiten het magazijn naar het depot toe in rekening te nemen) wordt de afstand tussen het depot (v0 in figuur 3.2.) en de onderste gang nul verondersteld (tak tussen v0 en b4 heeft dus een lengte van nul). Item
Rij
Depot
Onderste gang
Figuur 3.1: Voorbeeld van een single-blok magazijn (Ratliff en Rosenthal, 1983)
Elke boog stelt een op zich onbeperkt aantal takken met dezelfde (de afstand tussen de twee knopen die hij verbindt) lengte voor (omdat één enkele boog meerdere keren kan doorlopen worden). Het is echter duidelijk dat het meer dan tweemaal doorlopen van dezelfde boog niet tot een optimale oplossing zal leiden (men kan een item gaan halen en dan op zijn stappen
25
terugkeren, een volgende maal langs hetzelfde item passeren is inefficiënt). Om deze reden stellen Ratliff en Rosenthal voor om elke boog als een collectie van twee takken met voorgestelde lengte te beschouwen.
Figuur 3.2: Omzetting van figuur 3.1 tot een graaf pesentatie (Ratliff en Rosenthal, 1983)
In de uiteindelijke representatie zal elke knoop een graad nul of een even graad hebben (een order picking tour is een route die vertrekt en aankomt in het depot, men moet dus uit elke knoop waar men toekomt weer vertrekken). Bij het opbouwen van de order picking tour zal men telkens een deel van de graaf beschouwen en van links naar rechts verder werken. Rij na rij zal op deze manier worden afgegaan. Alle knopen (op de knopen a en b van de laatst beschouwde rij na) zullen dus, tijdens de opbouw, weer graad nul of een even graad hebben. Ook zal het voorlopige parcours uit nul (indien er nog geen enkel item gepickt moest worden), één of twee componenten bestaan. Elk van deze componenten zal op zijn minst één van de knopen a of b bevatten uit de laatste rij of uit de laatste rij waar nog een item gepickt moest worden (indien er rechts van de laatste rij geen items meer afgehaald moeten worden).
26
In de tweede stap onderscheiden Ratliff en Rosenthal zeven equivalentieklassen. Dit zijn manieren waarop men een deel van de reeds aangemaakte route kan identificeren. Deze equivalentieklassen bestaan uit 3 delen. De eerste twee stellen de graad van de respectievelijk laatst aangedane a-knoop en de laatst aangedane b-knoop voor. Dit kan dus nul, even (aangeduid door E) of oneven (aangeduid door U) zijn. Het laatste deel toont aan uit hoeveel componenten de oplossing onder constructie bestaat (nul, één of twee componenten). Deze zeven equivalentieklassen zijn:
-(U,U,1C) -(0,E,1C) -(E,0,1C) -(E,E,1C) -(E,E,2C) -(0,0,0C) -(0,0,1C)
De twee laatste klassen bestaan enkel indien er respectievelijk nog geen items gepickt zijn of er geen items meer gepickt hoeven te worden. De kortste van de equivalentieklassen, (0,E,1C), (E,0,1C),(E,E,1C),(0,0,1C) of (0,0,0C) nadat de laatste rij is afgegaan zal de kleinst mogelijke lengte bevatten.
Bij het aanmaken van een minimale tour gaat men als volgt tewerk. Men beschouwt, zoals eerder vermeld, alle rijen één na één. Men begint bij een zogeheten Lj- graaf (de eerste beschouwde graaf is dus L0-). Daar voegt men dan de configuratie van rij j aan toe om naar de Lj+ graaf te gaan. Van daar gaat men dan naar de L(j+1)- graaf door de configuratie om van aj en bj naar a(j+1) en b(j+1) te gaan aan de bestaande graaf toe te voegen. Er zijn volgens Ratliff en Rosenthal slechts 6 mogelijke configuraties voor een rij. Deze worden gegeven door figuur 3.3. Bij configuratie (I) wandelt de order picker volledig door de rij heen. Bij configuratie (II) en (III) zal hij slechts tot het verst gelegen item in die rij gaan. Configuratie (IV) is iets ingewikkelder. Hier zal de order picker langs beide zijden de rij ingaan maar slechts tot aan de plaats waar de grootste afstand tussen twee naast elkaar liggende items wordt waargenomen (cfr. “largest gap”). Een andere manier om de rij binnen 27
te stappen zou suboptimaal zijn. Configuratie (V) en (VI) spreken voor zich. Configuratie (VI) zal echter enkel voorkomen indien geen items gepickt hoeven te worden in deze rij (anders zal de tour niet alle te picken items bevatten).
Figuur 3.3: De zes mogelijke configuraties voor een rij (Ratliff en Rosenthal, 1983)
Onderstaande tabel toont alle mogelijke overgangen van een Lj- naar een Lj+ graaf.
Tabel 3.1: Overgang van Lj- naar Lj+ (Ratliff en Rosenthal, 1983)
Door een configuratie toe te voegen (bovenaan de tabel aangeduid) aan één van de equivalentieklassen (links) wordt een nieuwe equivalentieklasse bekomen in de kruising van de gekozen kolom en rij.
28
Bijkomende opmerkingen hierbij zijn dat de overgang op de vierde rij, vijfde kolom eigenlijk overbodig is (aangezien het hier slechts één klasse betreft zal de gewonnen tijd door deze weg te laten weliswaar minimaal zijn). Inderdaad kan van dezelfde equivalentieklasse naar deze equivalentieklasse overgegaan worden door gebruik te maken van één van de overgangen in de drie voorgaande kolommen. Deze zullen gezien hun configuratie altijd korter zijn. Voor j = 0 begint men weliswaar vanaf equivalentieklasse (0,0,0C). Om nu van Lj+ naar L(j+1)- over te gaan, stellen Ratliff en Rosenthal vijf alternatieven voor. Dezen staan afgebeeld in figuur 3.4.
Figuur 3.4: De vijf mogelijke configuraties om van rij j naar rij (j+1) over te gaan (Ratliff en Rosenthal, 1983)
Er kan weer worden opgemerkt dat de vijfde configuratie enkel mogelijk is indien er geen item meer ligt rechts van rij j. Onderstaande tabel geeft de mogelijke overgangen van Lj+ naar L(j+1)- aan.
29
Tabel 3.2:Overgang van Lj+ naar L(j+1)- (Ratliff en Rosenthal, 1983)
Opnieuw merkt men dat niet elke configuratie aan elke equivalentieklasse kan toegevoegd worden. De voornaamste reden hiervoor is dat elke knoop een even graad moet hebben in de afgewerkte tour. De knopen aj en bj, waar geen takken meer aan zullen toegevoegd worden, moeten dus een even graad hebben (aangeduid in tabel 3.2 door letter a). Tevens zou het toevoegen van een andere configuratie dan configuratie (V) aan equivalentieklasse (0,0,0C) nooit optimaal zijn (aangeduid door letter c). Nog andere overgangen (gekenmerkt door de letter b) kunnen niet gemaakt worden omdat een volledige tour maken dan niet meer tot de mogelijkheden behoort. Ook hier kan een bijkomende opmerking gemaakt worden. De overgangen op de tweede en derde rij van de vierde kolom zullen ook nooit tot een optimum leiden. Het toevoegen van takken naar een plaats waar geen verdere connectie is, is overbodige wandelafstand.
De tabellen worden op volgende wijze gebruikt. Voor elke equivalentieklasse wordt de lengte van de voorlopig gevormde route bijgehouden. Bij elke overgang wordt dus voor elke equivalentieklasse een nieuwe lengte berekend. Bij een overgang kiest men als startpunt deze equivalentieklasse die samen met de lengte van de bijkomende configuratie tot de kortste lengte leiden voor die equivalentieklasse.
Voor het analyseren van een voorbeeldoplossing verwijzen we naar Ratliff en Rosenthal (1983).
30
2.Het algoritme van Roodbergen en de Koster voor magazijnen bestaande uit 2 blokken Dit algoritme is een uitbreiding op het vorige, besproken algoritme van Ratliff en Rosenthal. Het is in staat om optimale oplossingen te bieden voor magazijnen met een tussengang en dus bestaande uit twee blokken met parallelle rijen. De aanpak is identiek en in wat volgt zal dan ook voornamelijk aan de verschillen met voorgaand algoritme aandacht worden geschonken.
De eerste identieke stap is de omzetting van de layout van het magazijn naar een graaf. De aanpak is identiek aan deze gebruikt door Ratliff en Rosenthal. Het enige verschil is natuurlijk de toevoeging van knopen tussen de twee blokken (wat leidt tot de ingebruikname van benamingen aj, bj en cj). Dit is noodzakelijk om aan te geven dat men zich ook in deze tussengang kan voortbewegen. Onderstaande figuur verduidelijkt dit.
Figuur 3.5: Omzetting van een magazijn met twee blokken naar een graaf (Roodbergen en de Koster, 2001)
31
Een zelfde aanpak wordt gehanteerd voor de tweede stap. Men heeft echter geen zeven equivalentieklassen meer maar vijfentwintig. Hier merkt men al dat een toename in het aantal blokken zorgt voor een meer dan evenredige toename van het aantal equivalentieklassen. De equivalentieklassen worden nu niet door slechts drie elementen bepaald maar door vijf elementen (waarvan de laatste in vele gevallen verwaarloosbaar is). De eerste drie elementen stellen de graad van de knopen aj, bj en cj voor (terug nul, even of oneven). Het volgende element stelt het aantal componenten waaruit deze equivalentieklasse bestaat voor (met een minimum van 0 en een maximum van 3). Het laatste element bepaalt welke knopen tot welke component behoren. In de situatie met slechts één blok was dit steeds evident. Inderdaad konden componenten slechts knopen bevatten met een graad verschillend van nul. Bestond een equivalentieklasse uit twee componenten dan behoorden beide knopen, per definitie, tot een verschillende component. In het geval van een tussengang en twee componenten kunnen problemen optreden. Indien slechts één van de knopen een even graad heeft (en de overige knopen dus een oneven graad hebben) is de equivalentieklasse eenduidig bepaald. De som van de graad van alle knopen uit 1 component moet namelijk altijd even zijn (zoniet kan men nooit een volledige tour vormen). Indien de drie knopen echter een even graad hebben maar de reeds gevormde route uit slechts twee componenten bestaat is het onduidelijk welke knopen samen in één component zitten en welke knoop in de andere zit. Hiertoe wordt een vijfde element aan de equivalentieklassebenaming toegevoegd. De knopen die in dezelfde component zitten worden achter elkaar neergeschreven en met een “-“ van de overige knoop gescheiden. De vijfentwintig equivalentieklassen zijn:
(0,0,0,0), (0,0,0,1), (e,e,e,1), (e,e,e,3), (e,0,0,1), (0,e,0,1), (0,0,e,1), (e,e,0,1), (e,0,e,1), (0,e,e,1), (u,u,0,1), (u,0,u,1), (0,u,u,1), (e,u,u,1), (u,e,u,1), (u,u,e,1), (e,e,0,2), (e,0,e,2), (0,e,e,2), (e,u,u,2), (u,e,u,2), (u,u,e,2), (e,e,e,2,a–bc), (e,e,e,2,b–ac), (e,e,e,2,c–ab)
De mogelijke configuraties voor een subrij zijn natuurlijk identiek aan deze geïdentificeerd door Ratliff en Rosenthal (Figuur 3.3.) en zullen hier dan ook niet verder besproken worden. De overgangen van Lj- naar Lj+ worden nu bepaald door twee tabellen. Eén voor het onderste blok en één voor het bovenste blok. Eerst wordt van Lj- overgegaan naar Lj+y, waar +y aanduidt dat de subrij in het onderste blok van rij j wordt gevuld. Daarna komt de overgang van Lj+y 32
naar Lj+x. Hierbij wordt ook de subrij in het bovenste blok van rij j gevuld. Onderstaande tabellen tonen de mogelijke overgangen aan.
Tabel 3.3: Overgang van Lj- naar Lj+y (Roodbergen en de Koster, 2001)
Tabel 3.4: Overgang van Lj+y naar Lj+x (Roodbergen en de Koster, 2001)
33
Dezelfde beperkingen als bij de tabellen van Ratliff en Rosenthal zijn ook hier van kracht. De volgende stap is de overgang van Lj+x naar L(j+1)-. Hiervoor is kennis van de mogelijke configuraties die tot deze overgang kunnen leiden noodzakelijk. Roodbergen en de Koster vonden 14 zulke configuraties. Ze staan opgesomd in figuur 3.6.
Figuur 3.6: Mogelijke configuraties om van rij j naar rij j+1 te gaan in een magazijn met twee blokken (Roodbergen en de Koster, 2001)
Nogmaals identiek aan het algoritme van Ratliff en Rosenthal kan hieruit een tabel (infra, p32) gedistilleerd worden die de mogelijke overgangen van Lj+x naar Lj- vastlegt. Met deze middelen is het mogelijk om een optimale route te bepalen in magazijnen met twee blokken.
Tabel 3.5: Overgang van Lj+x naar Lj- (Roodbergen en de Koster, 2001)
34
Hoofdstuk 4: optimale methodes: een uitbreiding Een logische volgende stap is natuurlijk om ditzelfde algoritme nogmaals uit te breiden, dit maal voor een magazijn met drie blokken of dus twee tussengangen. In wat volgt werd deze aanpak gebruikt en werd een methode ontwikkeld, voortbouwend op het algoritme van Ratliff en Rosenthal, om de kortste route te vinden in een magazijn met n blokken (n zijnde een natuurlijk getal). Om praktische (programmatorische) redenen zal het programma eigenlijk beperkt blijven tot het berekenen van problemen tot maximaal acht blokken. Een simpele modificatie kan dit echter verhelpen. Aangezien men in de praktijk echter zelden een magazijn met meer dan acht blokken tegenkomt werd deze modificatie niet daadwerkelijk uitgevoerd. Tevens moet vermeld worden dat de rekentijden van het voorbereidend werk (infra, p 36-39) exponentieel kunnen toenemen.
Het aanmaken en testen van zulk een algoritme verloopt in verschillende stappen. Eerst is er wat het voorbereidend werk genoemd zal worden. Dit zijn magazijnspecifieke zaken die slechts éénmaal berekend moeten worden. Bij veranderende layout zal men deze zaken opnieuw moeten doorworstelen maar het is veilig om te zeggen dat dit eerder uitzonderlijke omstandigheden zijn. Voor het voorbereidend werk is de rekentijd dus van ondergeschikt belang (hoewel extremen nog steeds voor problemen kunnen zorgen). Ten slotte zijn er de eigenlijke problemen die opgelost moeten worden. Hierbij geeft men een aantal te picken items in, in het syteem, samen met een paar magazijnspecifieke variabelen. Het ontwikkelde programma zal dan de kortste afstand doorheen het magazijn berekenen. Voor dit deel is rekentijd wel van groot belang. Hieronder volgt een bondige beschrijving van het gerealiseerde werk, uitgesplitst naar voorbereidend werk en uiteindelijke oplossing.
35
1.Voorbereidend werk
a)
Equivalentieklassen
Net als bij Ratliff en Rosenthal (1983) en Roodbergen en de Koster (2001) was een eerste vereiste het berekenen van de equivalentieklassen. Er werd gekozen voor een aanpak waar eerst alle mogelijke klassen werden aangemaakt waarna overbodige klassen uit de lijst werden verwijderd. Zoals vooraf besproken (zie Hfst 3) bestaat elke equivalentieklasse uit drie delen.
Deel 1
Het eerste deel bestaat uit n+1 elementen (met n het aantal blokken). Deze elementen stellen de graad van de knoop van de bovenste gang, onderste gang en tussengangen van de laatst afgelopen rij voor. Deze graad kan even zijn (waarvoor uit praktische overwegingen het cijfer 2 in plaats van de letter E wordt gebruikt), oneven (1), of nul (0). Deel één bestaat dus uit 3 tot de nde verschillende mogelijkheden. Men kan echter onmiddellijk sommige van deze delen schrappen. Uit het voorgaande bleek namelijk dat slechts equivalentieklassen waarvan de som van de graad van de knopen even (of nul) is tot een oplossing kunnen leiden. Door hiermee rekening te houden kan ruwweg de helft van de gegenereerde deeloplossingen geschrapt worden.
Deel 2
Het volgende element is het aantal componenten waaruit de equivalentieklasse bestaat. Dit is een cijfer tussen 0 en n+1 (0 kan enkel in één geval voorkomen: wanneer het eerste deel van de equivalentieklasse enkel uit nullen bestaat, n+1 kan enkel voorkomen wanneer het eerste deel van de equivalentieklasse uit 2’s bestaat). Ook hier zijn er weliswaar beperkingen die in acht genomen moeten worden. Men kan maximaal zoveel componenten hebben als de som van de cijfers uit het eerste deel gedeeld door twee. Elke component moet namelijk een even graad hebben en men kan niet meer componenten hebben dan gangen (anders komt men nooit tot één aaneengesloten route).
36
Deel 3
Het laatste element van de equivalentieklasse toont (net als bij Roodbergen en de Koster, 2001) aan welke knopen uit de laatst behandelde rij in welke component thuishoren. Opnieuw gebruiken we cijfers in plaats van letters. Zo wordt de knoop in de onderste gang aangeduid door het cijfer 1 en deze in de bovenste gang door het cijfer n+1. Verder is de aanpak vrij identiek als in hoofdstuk 3. Om alle mogelijke combinaties af te lopen werd gebruik gemaakt van
de
“permutation
generator”
klasse
van
Michael
Gilleland
(http://www.merriampark.com/perm.htm). Dit algoritme is op zijn beurt gestoeld op het boek van Kenneth H. Rosen (Discrete Mathematics and Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 282-284). Niet alle permutaties zullen echter tot een nieuwe equivalentieklasse leiden. Zo is de volgorde van de knopen in de componenten zelf en de volgorde van de componenten onderling van geen belang. Hier werd dan ook rekening mee gehouden in het ontwikkelde algoritme. Enkel zinvolle nieuwe equivalentieklassen werden uiteindelijk bewaard. Op deze manier werd het geheugengebruik van de computer danig beperkt. (Om maar een idee te geven: indien alles zomaar aan een lijst equivalentieklassen werd toegevoegd bekwam men voor vijf blokken ongeveer 3,500,000 equivalentieklassen. Na het invoeren van de besproken beperking waren dit minder dan 70,000 equivalentieklassen) Toch is een waarschuwing hier op zijn plaats. Zoals Gilleland stelt neemt het aantal permutaties snel toe naarmate het aantal elementen dat men permuteerd toeneemt. Zo heeft een lijst met twintig elementen twintig faculteit (20!) permutaties. Dit zijn er 2,432,902,008,176,640,000. Het spreekt dus vanzelf dat dit programma zijn beperkingen heeft.
Uiteindelijk moesten een aantal equivalentieklassen die toch nog onmogelijk waren maar door de voorgaande barrières waren geslopen (door beperkingen van het ontwikkelde programma) eruit worden gefilterd.
Het is duidelijk dat het aantal equivalentieklassen snel toeneemt naarmate het aantal blokken toeneemt. Hoewel men ze voor elke layout van een magazijn maar éénmaal moet berekenen kunnen de rekentijden toch een beperking vormen. Daar waar men voor vier blokken al na luttele seconden output verkrijgt duurt het al meer dan één minuut voor vijf blokken. Voor zes
37
blokken wordt de rekentijd dan weer op een paar dagen (afhankelijk van de kracht en kloksnelheid van de gebruikte computer) geschat.
b)
Tabellen om de rijen te vullen (Lj+ tabellen)
Voor magazijnen bestaande uit één blok was slechts één tabel benodigd om de configuratie van de subrijen (en de bijhorende overgang naar een andere equivalentieklasse) te bepalen (Ratliff en Rosenthal, 1983). Voor magazijnen bestaande uit twee blokken waren dit twee tabellen. Eén per blok. Voor magazijnen bestaande uit meerdere blokken is dit dus eenvoudig door te trekken. Er is één tabel benodigd per blok. Deze tabellen worden berekend op basis van de equivalentieklassen berekend in de vorige stap. Voor elke equivalentieklasse zijn er namelijk zes overgangen mogelijk (identiek met figuur 3.3, p 28).
Bij het berekenen van deze tabellen moet rekening gehouden worden met het veranderen van de graad van de elementen van het eerste deel van de equivalentieklassen door toevoegen van een configuratie uit figuur 3.3. Tevens kan het aantal componenten en welke kopen tot welke componenten behoren veranderen. Configuratie (I) en (V) kunnen bijvoorbeeld ofwel het aantal componenten onveranderd laten (de bovenste knoop of de onderste knoop waren al een deel van dezelfde component) ofwel één component toevoegen aan de equivalentieklasse (geen van beide knopen waren al deel van een component) ofwel de equivalentieklasse met één component doen dalen (door twee afzonderlijke componenten te connecteren). Net als bij voorgaande algoritmes zullen ook hier bepaalde overgangen niet mogelijk zijn.
c)
Configuraties om van rij j naar rij j+1 over te gaan
Het is niet voldoende equivalentieklassen te berekenen voor magazijnen met n blokken. Men moet ook de configuraties bepalen waarmee men van de ene rij naar de andere overgaat. Dit aantal is van op voorhand te bepalen via de eenvoudige formule (3 tot de macht n+1 gedeeld door 2) afgerond naar boven. Inderdaad zijn er voor elke knoop drie mogelijkheden. Men kan van deze naar de volgende knoop gaan maar slechts in één richting. Of men kan naar de volgende knoop gaan en later terugkeren in tegenovergestelde richting. Ten slotte kan men ook beslissen dit pad helemaal niet te gebruiken. Aangezien deze keuze voor elk van de n+1 knopen gemaakt kan worden heeft men dus 3 tot de n+1ste mogelijkheden. Hiervan zijn de 38
helft echter overgangen die nooit tot een optimale oplossing kunnen leiden. De som van de graad van al deze knopen moet namelijk even zijn om eerder vermelde redenen. Dit geeft dus 3 tot de macht n+1 gedeeld door 2. 3 tot de macht n+1 is echter steeds een oneven getal en moet dus naar boven afgerond worden (om de mogelijkheid waar men niet langer naar de volgende rij overstapt in rekening te nemen). Men kan dit zelf eenvoudig nagaan voor een geval van één knoop waar er dus drie mogelijkheden zijn, slechts twee zullen een mogelijke overgang weergeven. Een eenvoudig programma is dus in staat deze mogelijkheden snel op te sommen. Voor elke extra blok zullen het aantal te beschouwen overgangen dus ongeveer toenemen met een factor drie.
d) Tabel om de overgang van rij j naar rij j+1 te maken (van Lj+ naar L(j+1)-) Deze laatste tabel wordt weer op identieke wijze geconstrueerd als in de besproken literatuur. Voor elke equivalentieklasse worden de mogelijke overgangen beschouwd (berekend in puntje 1.c van dit hoofdstuk) en aan de hand hiervan worden nieuwe equivalentieklassen gebouwd. De graad van de nieuwe knopen (overgang van rij j naar rij j+1 dus de knopen op rij j+1 worden beschouwd) wordt voor honderd procent bepaald door de gekozen overgang. Welke knopen tot welke component behoren, wordt bepaald door de interactie tussen de oorsprongsequivalentieklasse en de gekozen overgang.
Niet elke combinatie van een equivalentieklasse met een overgang zal tot een nieuwe equivalentieklasse leiden. Zo moet men opletten dat geen volledige component ongeconnecteerd wordt achtergelaten (in welk geval men nooit tot één gesloten tour zal komen), dat men geen connectie legt met een knoop met graad nul (suboptimaal, zie supra, p 30) en dat elke knoop uit de vorige rij (rij j ) een even graad bekomt.
39
2.Uiteindelijke oplossing Hier is het uiteindelijk de bedoeling om een specifiek probleem op te lossen. Een aantal items worden samen met een paar magazijnspecifieke kenmerken ingegeven om een optimale route te bepalen. Weliswaar moeten eerst een aantal andere gegevens ingelezen worden. Dit zijn:
-een opsomming van alle equivalentieklassen (Hfst 4: 1.a) -Lj+ tabellen (Hfst 4: 1.b) -de configuraties om van de ene rij naar de volgende over te gaan (Hfst 4: 1.c) -Lj- tabel (Hfst 4: 1.d) Aangezien deze zaken enkel veranderen als ook de layout van het magazijn verandert is het voldoende ze slechts één maal in te lezen (bv. bij het opstarten van de computer) om er vervolgens alle mogelijke problemen mee op te lossen. Zodoende wordt er met de tijd nodig om deze (soms lijvige) bestanden in te lezen geen rekening gehouden.
De oplossing werd bekomen door, identiek aan Ratliff en Rosenthal (1983) en Roodbergen en de Koster (2001) eerst alle subrijen van eenzelfde rij op te vullen (gebruik makend van de Lj+ tabellen, en de berekening van de zes mogelijke configuraties uit figuur 3.3), een overgang te maken naar de volgende rij (gebruik makend van de Lj- tabel en de rijovergangen) en daar weer opnieuw te beginnen tot alle rijen afgelopen zijn.
De manier van het overlopen van de tabellen kan echter ingekort worden. Indien men voor elke equivalentieklasse de volledige te overlopen tabel beschouwt en dus telkens men deze klasse tegenkomt bepaalt hoe lang zij is om ze met de andere mogelijkheden te vergelijken zal men een hoog aantal zoekverichtingen moeten doen (naast de noodzakelijke berekeningen indien de oorsprongsklasse wel degelijk de gezochte klasse is). Voor een Lj+ tabel: (aantal equivalentieklassen) maal (aantal equivalentieklassen) maal (zes mogelijke rijconfiguraties). Zolang het aantal equivalentieklassen beperkt blijft zal ook de rekentijd verwaarloosbaar zijn. Zo zijn dit een luttele 3750 vergelijkingen per Lj+ tabel (of dus per te vullen subrij) voor magazijnen bestaande uit twee blokken (en dus 25 equivalentieklassen). Voor magazijnen met vijf blokken die 4089 equivalentieklassen hebben zijn dit echter 100,319,526 vergelijkingen per op te vullen subrij. Hetzelfde geldt voor de Lj- tabel: (aantal equivalentieklassen) maal (aantal equivalentieklassen) maal (aantal mogelijke overgangen). Voor twee blokken met 40
slechts 5 overgangen en 25 equivalentieklassen zijn dit 3125 vergelijkingen (per overgang van rij j naar rij j+1). Opnieuw stijgt dit dramatisch wanneer het aantal blokken stijgt. Voor vijf blokken met 4089 equivalentieklassen en 365 overgangen zijn dit echter 6,102,771,165 vergelijkingen.
De rekentijden lopen op deze manier dus snel op naarmate het aantal blokken stijgt. Het is gemakkelijk te zien dat voor vijf blokken een oplossing nooit binnen de gewenste tijd (onder de minuut) zal gevonden worden.
Een eenvoudige verbetering kan het aantal berekeningen echter ongelooflijk verlagen. Omdat deze tabellen (Lj+ tabellen en Lj-) op voorhand gekend zijn en men dus op voorhand weet welke equivalentieklasse waar in de tabel te vinden is, is het opzoeken hiervan overbodig werk. Veel beter is het (voor elk van deze tabellen) een nieuwe tabel op te stellen. Hierin kan men per equivalentieklasse noteren wat de oorsprongsequivalentieklassen en de overgangen of rijconfiguraties zijn die tot deze klasse leiden. Opnieuw is dit een berekening die maar éénmaal per magazijnlayout gemaakt hoeft te worden. Hierdoor vervallen, zoals gezegd, de latere vergelijkingen. Inderdaad zullen zowel voor de Lj+ tabellen als de Lj- tabel het aantal vergelijkingen verdwijnen en zal men slechts met gerichte berekeningen te maken hebben. Bij een magazijn bestaande uit vijf blokken zijn dit voor elke subrij slechts 24,534 berekeningen (deze berekeningen moesten bovendien ook in het eerste systeem gemaakt worden). Voor de overgang van rij j naar rij j+1 zijn het nog slechts 1,492,485 berekeningen. Dit leidt tot een oplossing in luttele seconden.
Een andere mogelijkheid tot verbetering bestaat uit het gebruik van de layout van het magazijn ter simplificering van het probleem. Het is namelijk zo dat er maar zes mogelijke configuraties zijn voor een subrij (gegeven door figuur 3.3). Bepaalde orders zullen dus items bevatten die de route niet zullen beïnvloeden. Deze items kunnen dan best uit de orderpicklijst verwijderd worden om de rekentijden te verminderen. Voor elke subrij moeten namelijk de lengte van de zes configuraties berekend worden. Om deze te berekenen wordt de volledige lijst met te picken items afgelopen op zoek naar deze items die in dat blok in die rij zitten. Op basis van deze items kan dan weer voor elke configuratie een lengte bepaald worden. Hoe minder items elke keer moeten afgelopen worden, hoe korter de rekentijd. De kost hiervan is echter het feit dat een extra programma ter analysering van de overbodige items moet gebruikt
41
worden. Overbodige items kunnen voorkomen worden omdat slechts maximaal vier items per subrij van belang zijn.
Deze zijn:
-Het eerste item dat in een rij gepickt moet worden
-De twee items rond de “largest gap” van een rij
-Het laatste item dat in een rij gepickt moet worden
Andere items van dezelfde subrij zullen geen invloed hebben op de routing van de order picker. Er moet echter voor gezorgd worden dat de “largest gap” de “largest gap” blijft. Zoniet riskeert men een suboptimale route te krijgen. Het kan hiervoor noodzakelijk zijn om een aantal virtuele orders bij te plaatsen in de lijst om dit te blijven garanderen (concreet komt dit neer op het plaatsen van een virtueel item om de “largest gap -1” plaatsen). Dit zal echter steeds voor minder of evenveel items zorgen per rij.
Volgend hoofdstuk is gewijd aan de analyse van de op deze manier bekomen resultaten.
42
Hoofdstuk 5: analyse van de uitbreiding Om de resultaten van de in vorig hoofdstuk besproken methode te analyseren, is een tweede methode noodzakelijk ter benchmarking. Hiertoe wordt het idee van Theys, Bräysy, Dullaert en Raa (2010), besproken onder punt e van hoofdstuk 2, gebruikt. Hiertoe is het noodzakelijk een afstandsmatrix op te stellen van de te picken items. Deze afstandsmatrix zal dan niet meer aan de Lin-Kernighan Travelling Salesman heuristiek onderworpen worden maar aan een branch and bound methode die de optimale oplossing zal vinden. Voor zulke methode is reeds software beschikbaar. De ontwikkeling van een nieuw algoritme is dan ook niet meer aan de orde. Op de site:
wordt deze software vrij ter beschikking gesteld. Ook voor deze methode werden de overbodige items achterwege gelaten. (in het vervolg van dit werkstuk zal naar het weglaten van onbelangrijke items verwezen worden met de term “clusteren” aangezien voor deze methode alle belangrijke items per subrij moeten geclusterd worden)
Ook werd geprobeerd om betere resultaten te bekomen voor deze tweede methode door routes die op voorhand onmogelijk zijn uit te schakelen. Een groot getal werd ingeven in de afstandsmatrix daar waar het duidelijk was dat het ene item niet na het andere bezocht zou kunnen worden zodat de software deze wegen niet verder uitpluist (deze methode wordt aangeduid met de term “clusteren en reduceren” omdat naast het clusteren van de orders ook wordt overgegaan tot een reductie van het te beschouwen aantal paden). Onmogelijke paden zijn deze waar:
-
men van een item rond de largest gap naar een item uit een andere subrij gaat verschillend van het onderste of bovenste item van die subrij
-
men van één van de virtueel bijgeplaatste orders naar een item uit een andere subrij gaat
-
men van het onderste of bovenste item uit een subrij naar een ander item dan het onderste of bovenste item uit een andere subrij gaat (naar een ander item uit dezelfde subrij gaan, blijft weliswaar nog steeds mogelijk)
43
Voor het onderzoeksopzet werden ad random 800 orders aangemaakt. In wat volgt zullen eerst verschillen in resultaten tussen de verschillende methodes besproken worden. Vervolgens zal de benodigde tijd om tot een oplossing te komen ontleed worden naar zijn “drivers” of elementen die voor de bekomen tijd zorgen.
Deze “drivers” zijn:
-
Het aantal blokken (voor het onderzoeksopzet heeft men zich beperkt tot magazijnen tussen de 2 en de 5 blokken)
-
Het aantal op te halen items (tussen 25 en 125) waarvan het eerste item telkens vast was en de plaats van het depot aanduidde
-
Het aantal rijen (tussen de 10 en de 20)
-
Het aantal plaatsen waar items kunnen opgestapeld liggen per rij (eveneens tussen de 10 en de 20)
-
De afstand tussen twee opeenvolgende rijen of blokken (tussen de 2 en de 5)
-
Het al dan niet toepassen van ABC classificatie
1.tijdsverschillen tussen de gebruikte methodes
a) Branch and bound benchmark versus nieuwe methode (zonder clusteren) Vooreerst werd getest of de tijd tussen de zelf uitgewerkte methode en deze waartegen gebenchmarkt wordt verschillend is (momenteel wordt nog geen rekening gehouden met het al dan niet clusteren van de orders). Onderstaande samenvatting van de gepaarde t-test toont aan dat dit inderdaad het geval is (voor het laten lopen van de testen werd de SAS 9.2 omgeving gekozen).
44
The TTEST Procedure Difference:
Tijd branch and bound benchmark – tijd nieuwe methode
N
Mean
Std Dev
Std Err
Minimum
Maximum
800
4.6919
26.6725
0.9430
-3.2385
514.3
Mean 4.6919
95% CL Mean 2.8408
Std Dev
6.5429
26.6725
DF
t Value
Pr > |t|
799
4.98
<.0001
95% CL Std Dev 25.4265
28.0478
De conclusies die men hieruit kan trekken zijn, voor de beperkingen met betrekking tot het onderzoeksopzet, dat de nieuw ontwikkelde methode beter presteert. Gemiddeld bestaat er een verbetering van bijna vijf seconden per order. De echte verbetering is echter veel groter en kan slechts begrepen worden wanneer naar het minimum en maximum verschil wordt gekeken tussen beide methodes. Zo heeft de nieuw ontwikkelde methode, in het slechtste geval, amper drie seconden slechter gepresteerd dan benchmark. Deze benchmark presteerde echter beduidend slechter in zijn worst case scenario. Een goede vijfhonderdveertien seconden verschil konden gemeten worden.
Figuur 5.1: Boxplot branch and bound benchmark methode
45
Figuur 5.2: Boxplot nieuwe methode
Zoals duidelijk blijkt uit bovenstaande boxplots is de nieuwe methode aan veel minder variantie onderworpen dan de branch and bound benchmark methode. Hoewel de gemiddeldes en medianen niet wezenlijk van elkaar verschillen zijn het de extremen die voor grote verschillen zorgen. Het is voor een order picker inderdaad geen probleem om een paar seconden op zijn order te moeten wachten (in de tijd dat de order picker voor hem zijn order ontvangt of afdrukt is het volgende order al berekend). Indien echter langer dan een minuut moet worden gewacht, heeft men steeds meer met verloren tijd (waste) te maken. Extremen zoals de branch and bound methode soms kan geven zijn dan ook uit den boze. De nieuwe methode kan voor alle 800 orders echter steeds een kortste weg vinden in minder dan 4 seconden. In dit opzicht is deze methode dan ook een grote verbetering.
Onderstaande histogrammen komen tot eenzelfde conclusie. Wel is het duidelijk dat de tijden niet normaal verdeeld zijn.
46
Figuur 5.3: Histogram branch and bound methode
Figuur 5.4: Histogram nieuwe methode
Een opmerking is hier echter op zijn plaats. Het is duidelijk dat de nieuwe methode veel stabielere uitkomsten genereert. Maar het is ook duidelijk dat de tijden snel zullen stijgen naarmate het aantal blokken zal stijgen (zoals uitgelegd in vorig hoofdstuk). Onderstaande boxplots verschaffen een beter inzicht.
47
Figuur 5.5: Boxplots nieuwe methode per blok
Figuur 5.6: Boxplots van de branch and bound methode per blok
Het is duidelijk wat de prijs voor stabiliteit is. Naarmate het aantal blokken toeneemt, zullen de rekentijden exponentieel toenemen. Zolang het aantal blokken van een magazijn beperkt blijft is er geen probleem (en in de meeste praktische gevallen is dit inderdaad het geval). Voor de branch and bound methode zijn het aantal blokken, zoals verwacht kon worden, van geen belang. Uitschieters komen in alle gevallen voor.
Om de hypothese dat de standaarddeviaties verschillend zijn voor beide methodes te testen werd Bartlett’s test gebruikt. Deze toont aan dat de standaarddeviaties inderdaad significant verschillend zijn. De standaarddeviatie voor de branch and bound methode blijkt tot bijna vijfentwintig maal groter te zijn dan deze van de nieuwe methode.
48
The ANOVA Procedure Bartlett's Test for Homogeneity of time Variance Source
DF
Chi-Square
Pr > ChiSq
Class
1
3926.2
<.0001
The ANOVA Procedure Level of Class
N
Tijd nieuwe methode Tijd branch and bound benchmark
-------------time-----------Mean Std Dev 800 800
0.77474505 5.46660028
1.1391337 26.5779004
Een gevolg van het feit dat de gegevens niet normaal verdeeld zijn en de standaarddeviaties met een grote factor van elkaar verschillen is dat de eerst berekende t-test mogelijks ongeldige uitkomsten geeft. Gezien het grote aantal observaties en het feit dat voor elke methode evenveel observaties gebruikt werden geeft de robuustheid van de t-test echter garantie voor de getrokken conclusies (zo wordt algemeen aanvaard dat men zich voor meer dan vijftig observaties geen zorgen moet maken zelfs al zijn er duidelijke afwijkingen van de assumpties voor gelijke variantie en normaliteit).
49
b) Branch en bound methode versus branch and bound methode met clusteren van de orders Om uit te maken of er een verschil in gemiddelde tijd bestaat tussen beide methodes werd nogmaals gebruik gemaakt van een gepaarde t-test. Onderstaande samenvatting toont aan dat er inderdaad een gemiddelde verbetering werd geboekt van bijna vijf seconden per order. Ook hier schijnen de uitschieters danig beperkt te worden (al zijn de extreme verschillen met een maxima van ongeveer zevenentwintig seconden wel groter dan bij de nieuwe methode). The TTEST Procedure Difference:
tijd branch and bound – tijd met clusteren
N
Mean
Std Dev
Std Err
Minimum
Maximum
800
4.6340
26.4282
0.9344
-27.3752
513.6
Mean 4.6340
95% CL Mean 2.7998
Std Dev
6.4681
26.4282
DF
t Value
Pr > |t|
799
4.96
<.0001
95% CL Std Dev 25.1936
27.7909
Boks plots en histogrammen leveren een dieper inzicht.
Figuur 5.7: Boxplots branch and bound methode na clusteren van de orders
50
Figuur 5.8: Histogram branch and bound methode na clusteren van de orders
Door het clusteren van de orders kunnen een groot aantal items geschrapt worden van de lijst. Vooral voor orders bestaande uit veel items is de kans groot dat het aantal te bezoeken knopen verminderd wordt. Op deze manier worden net de extremen aangepakt. Hoge tijden blijven voorkomen (tot boven de vijftig seconden) maar zijn al heel wat acceptabeler.
Ook hier is een variantieanalyse op zijn plaats. Volgens Bartlett’s test zijn de standaardafwijkingen inderdaad significant kleiner. The ANOVA Procedure Bartlett's Test for Homogeneity of time Variance Source
DF
Chi-Square
Pr > ChiSq
Class
1
2327.2
<.0001
The ANOVA Procedure Level of Class Tijd branch and bound met clusteren Tijd branch and bound
N
-------------time-----------Mean Std Dev 800 800
0.83264020 5.46660028
3.1379636 26.5779004
Of deze methode de voorkeur krijgt op de nieuw ontwikkelde methode zal later onderzocht worden.
51
c)
Branch en bound methode met clusteren van de orders versus branch and bound methode met clusteren en reduceren
Een volgende vraag die zich dan stelt is of de branch and bound methode nog verder verbeterd kan worden en of extremen verder beperkt kunnen worden. Zoals aangegeven in het begin van dit hoofdstuk werd gebruik gemaakt van een “clusteren en reduceren” methode. Statistisch onderzoek leverde de conclusie dat het verschil tussen deze resultaten en voorgaande niet significant zijn (zie onderstaande test). The TTEST Procedure Difference:
tijd clusteren – tijd clusteren en reduceren
N
Mean
Std Dev
Std Err
Minimum
Maximum
800
0.0987
2.4671
0.0872
-16.3723
39.9988
Mean 0.0987
95% CL Mean -0.0725
Std Dev
0.2700
2.4671
DF
t Value
Pr > |t|
799
1.13
0.2579
95% CL Std Dev 2.3519
2.5944
Het minimum en maximum in voorgaande test doen echter wel het vermoeden rijzen dat een verbetering op vlak van extremen is geboekt.
Figuur 5.9: Boxplot "clusteren en reduceren" methode
52
Figuur 5.10: Histogram "clusteren en reduceren" methode
De laatste stap van deze analyse is opnieuw de test voor gelijke variantie van Bartlett. Opnieuw is het verschil tussen de standaardafwijkingen significant. Hoewel de methode met clusteren en reduceren gemiddeld niet veel beter presteert dan eenvoudigweg clusteren heeft het wel een significante invloed op de variantie van de uitkomsten. Aangezien dat het grootste probleem blijkt te zijn voor de branch and bound methode is deze aanvulling zeker de moeite om verder onderzocht te worden. In wat volgt zal dan ook niet langer met de methode van het “clusteren” rekening gehouden worden maar wel met deze van het “clusteren en reduceren” (die weliswaar op zich een uitbreiding is op het “clusteren”). The ANOVA Procedure Bartlett's Test for Homogeneity of time Variance Source
DF
Chi-Square
Pr > ChiSq
Class
1
131.3
<.0001
The ANOVA Procedure Level of Class Tijd clusteren en reduceren Tijd clusteren
N 800 800
-------------time-----------Mean Std Dev 0.73389451 0.83264020
2.08038419 3.13796359
53
d) De nieuwe methode zonder clusteren versus de nieuwe methode met clusteren De vraag blijft of de nieuwe methode verder verbeterd kan worden door ook hier het clusteralgoritme toe te passen en het aantal orders te verminderen. Analyse van figuur 5.5 (supra, p 48) maakte echter al duidelijk dat het grootste probleem van deze methode de exponentiële toename van de rekentijden zijn naarmate het aantal blokken toeneemt. De verwachting is dan ook dat de vermindering van het aantal orders slechts tot een bijzonder kleine verbetering zal leiden. Onderstaande t-test lost onze verwachtingen in. De verbetering blijkt niet significant te zijn. The TTEST Procedure Difference:
Nieuwe methode met clusteren – Nieuwe methode
N
Mean
Std Dev
Std Err
Minimum
Maximum
800
0.00321
0.0745
0.00263
-0.3133
1.1537
Mean
95% CL Mean
0.00321
-0.00196
Std Dev
0.00838
95% CL Std Dev
0.0745
0.0710
DF
t Value
Pr > |t|
799
1.22
0.2233
0.0783
Hoewel de standaardafwijking van de nieuwe methode bijzonder klein is, wordt ter volledigheid ook hier Bartlett’s test opgenomen. Zoals verwacht is er geen statistisch significant verschil. In wat volgt wordt deze laatste methode dan ook niet meer beschouwd. The ANOVA Procedure Bartlett's Test for Homogeneity of time Variance Source
DF
Chi-Square
Pr > ChiSq
Class
1
0.2247
0.6355
The ANOVA Procedure Level of Class
N
Tijd nieuwe methode met clusteren Tijd nieuwe methode
-------------time-----------Mean Std Dev 800 800
0.77795399 0.77474505
1.12018359 1.13913373
54
e) De branch and bound methode met clusteren en reduceren versus de nieuwe methode (zonder clusteren) De laatste vergelijking die gemaakt hoeft te worden is dan uiteindelijk de beste methode die gebruik maakt van branch and bound ten opzichte van de nieuwe methode (zonder clusteren aangezien dit geen verbetering bracht). Onderstaande t-test toont aan dat beide methodes even goed presteren. Er is geen wezenlijk verschil merkbaar. The TTEST Procedure Difference:
nieuwe methode met clusteren en reduceren- nieuwe methode
N
Mean
Std Dev
Std Err
Minimum
Maximum
800
-0.0892
2.3736
0.0839
-3.5048
27.2872
Mean -0.0892
95% CL Mean -0.2540
Std Dev
0.0755
95% CL Std Dev
2.3736
2.2627
DF
t Value
Pr > |t|
799
-1.06
0.2880
2.4960
Het is dus de variantieanalyse en Bartlett’s test die zullen uitmaken welke methode het best gebruikt wordt. Uit onderstaande output blijkt dat de standaardafwijkingen inderdaad verschillend zijn voor beide methodes en dat de nieuwe methode er in slaagt deze zowat te halveren. Op basis van deze conclusies zou men dan ook steeds aanraden de nieuwe methode te gebruiken. Hier past echter een nuancering. Bij voorgaande analyse werd slechts rekening gehouden met gemiddeldes genomen over verschillende situaties. Het is echter niet ondenkbaar dat één van beide methodes beter presteert in bepaalde gevallen daar waar de andere methode in andere gevallen betere resultaten kan geven. Dit zal het onderwerp vormen van het volgende deel van dit hoofdstuk.
The ANOVA Procedure Bartlett's Test for Homogeneity of time Variance Source
DF
Chi-Square
Pr > ChiSq
Class
1
273.7
<.0001
The ANOVA Procedure Level of Class
N
Nieuwe methode 800 Methode met clusteren en reduceren
-------------time-----------Mean Std Dev
800
0.77474505 1.139133 0.73389451 2.08038419
55
2.Verschillende methodes opgesplitst naar hun drivers
a)
branch en bound methode met clusteren en reduceren
Een eerste analyse betreft de branch and bound methode met clusteren en reduceren. Hier werd gebruik gemaakt van “concorde” een programma dat een optimale oplossing vindt op basis van “branch and bound” en dat te vinden is op <www.tsp.gatech.edu/concorde/>. Hoewel dus moeilijk kan onderzocht worden hoe het aantal blokken of rijen een impact hebben op de totale rekentijd kan dit wel voor het aantal items per order. Applegate, Bixby, Chvátal en Cook tonen in hun boek “The Travelling Salesman Problem, 2006” aan dat de rekentijd exponentieel stijgt met het aantal items.
Figuur 5.11: Exponentieel verloop van de tijd in functie van het aantal items (Applegate et al.)
Aangezien echter van een groot aantal items wordt uitgegaan (tussen de paar honderd en de tweeduizendvijfhonderd) kan men zonder grote fout zeggen dat voor kleine orders onder de honderdvijftig items een lineaire functie een goede benadering is. Tevens wordt vermeld dat voor kleine orders (tussen 0 en 400 items) alle optimale oplossingen onder de tien seconden gevonden worden (op een computer met kloksnelheid van 2.4 GHz). Weliswaar werd in dit geval uitgegaan van geografische locaties waar de kortste afstand tussen twee punten altijd wordt gegeven door de Manhattan afstand. Het is omwille van deze reden (en omwille van de lagere kloksnelheid van de gebruikte computer) dat hogere tijden kunnen gevonden worden in dit proefstuk. Onderstaande grafiek toont nogmaals het verloop van de tijd ten opzichte van het aantal items, ditmaal voor kleinere orders.
56
Figuur 5.12: Verloop van de tijd voor een klein aantal orders (Applegate et al.)
Alvorens te beslissen of een lineaire methode van analyse op zijn plaats is zal voor elke driver het verband met de tijd worden geschat op basis van de vermelde steekproef van 800 orders.
Figuur 5.13: Verloop van de tijd voor verschillende drivers ("clusteren en reduceren" methode)
57
Het is moeilijk om op het zicht verbanden vast te leggen (op de driver ABC na) ABC die schijnbaar een lineair verband houdt met de tijd. Er is echter geen reden om te beslissen dat een lineair model geen goede oplossing (of minstens een goede benadering) zou geven. In wat volgt zal dan ook gebruik gemaakt worden van lineaire regressies om de impact van de drivers te analyseren. Er werd besloten om achterwaartse regressie toe te passen. Dit houdt in dat alle variabelen aan het model worden toegevoegd, men het model regresseert, en men ten slotte de minst significante term verwijdert. Dit proces herhaalt men tot enkel de significante termen overschieten. Parameter Intercept blocks orders ABC blocks*aisleLength orders*ABC ABC*aisleLength
Estimate
Error
t Value
Pr > |t|
-1.149101870 -0.353245637 0.028293233 2.539444910 0.027733823 -0.023042254 -0.115975617
0.35690120 0.14782088 0.00340199 0.78556506 0.00896571 0.00480599 0.04626574
-3.22 -2.39 8.32 3.23 3.09 -4.79 -2.51
0.0013 0.0171 <.0001 0.0013 0.0020 <.0001 0.0124
Op deze manier werden bovenstaande resultaten berekend. Deze kunnen vertaald worden naar de onderstaande formule.
Tijd branch and bound met clusteren en reduceren = -1.1491 + (-0.3532 + 0.0277*subrijlengte)*blokken + 0.0283*items + (2.5394 -0.0230*items -0.1160*subrijlengte)*ABC Indien men enkel naar de hoofdtermen kijkt merkt men dat ABC-classificatie een onverwacht positief effect heeft op de tijd. Het lineair verband dat tevoren werd vastgesteld was echter negatief. Dit wordt echter duidelijk wanneer ook naar de interactietermen gekeken wordt. Hoe meer items, hoe meer ABC-classificatie een invloed heeft. Ook subrijlengte blijkt in combinatie met ABC-classificatie een invloed te hebben. Zoals verwacht stijgt de rekentijd met het aantal items. Zelfs in het geval van ABCclasificatie zal een bijkomend item voor een bijkomende gemiddelde rekentijd van 0.005 seconden zorgen. Ook de totale rijlengte (blokken * subrijlengte) blijkt van belang te zijn.
Wel moet er gewaarschuwd worden dat de “sum of squares” uitgelegd door het model beperkt is. Hieruit volgt dan ook een “R square” van amper 14%.
58
b)
de nieuwe methode (zonder clusteren)
Wat deze methode betreft kunnen bepaalde veronderstellingen al van op voorhand gemaakt worden. Zo verwacht men een exponentiële toename van de rekentijd naarmate het aantal blokken stijgt. Dit omdat het aantal equivalentieklassen exponentiëel toeneemt met het aantal tussengangen. Ook wordt een lineair verband verwacht met het aantal rijen. Voor elke rij moeten namelijk een aantal operaties steeds opnieuw uitgevoerd worden ( zie hoofdstuk 4). Om meer inzicht te verkrijgen in de invloed van deze drivers op de tijd werden onderstaande grafieken opgesteld.
Figuur 5.14: Verloop van de tijd voor verschillende drivers ("nieuwe methode")
59
Zoals verwacht wordt er inderdaad een exponentiëel verband gevonden voor het aantal blokken en een duidelijk lineair verband voor het aantal rijen. Tevens kunnen in elke grafiek (op de blokken grafiek na) meerdere patronen (of wolken) onderscheiden worden. Deze stellen de verschillende tijden voor verschillende blokken voor. Het is hier al duidelijk dat het aantal blokken een beslissende invloed heeft.
Hoewel een lineair model hier niet op zijn plaats is wegens het exponentieel verloop van de tijd in functie van het aantal blokken zal hier toch eerst een lineaire regressie toegepast worden. Deze zal ons helpen om een benaderende formule te vinden. Deze formule zal dan ook slechts benaderend zijn in het gebied van de steekproef. Eenmaal men met meer dan 5 blokken te maken heeft zal de fout te groot worden. Naarmate het aantal equivalentieklassen verantwoordelijk is voor de rekentijd kan onderstaande grafiek een beeld vormen van de onderschatting die door dergelijk model zou worden gemaakt (het aantal equivalentieklassen voor zes blokken berust op een schatting).
Figuur 5.15: Lineaire benadering van een exponentiële
Ook hier wordt achterwaartse regressie toegepast. Dezelfde initiële hoofd- en interactietermen werden beschouwd. Tenslotte werd tot volgende conclusie en formule gekomen. Parameter Intercept aisles aisles*blocks aisles*interaisle
Estimate
Standard Error
t Value
Pr > |t|
-.0186881710 -.1541490172 0.0557199442 0.0034749407
0.11462212 0.01034632 0.00128456 0.00154254
-0.16 -14.90 43.38 2.25
0.8705 <.0001 <.0001 0.0245
60
Formule : Tijd nieuwe methode = (-0.1541+0.0557*blokken + 0.0035*tussenrijlengte)*rijen Indien men opnieuw alleen de hoofdtermen beschouwt, krijgt men weer de verkeerde indruk dat het aantal rijen een negatief effect heeft op de tijd. Het is pas wanneer men de combinatie met het aantal blokken in ogenschouw neemt dat het effect duidelijk is. Zo zal voor vijf blokken elke additionele rij de gemiddelde rekentijd met ongeveer 0.1 seconde doen stijgen. Hoewel het interactieeffect tussen de tussenrijlengte en het aantal rijen significant is, is het niet relevant te noemen. Deze factor zal dan ook slechts een fractie van een seconde verschil verklaren.
Ook is het de moeite op te merken dat een groter deel van de sum of squares door het model kan worden uitgelegd. Daar waar de R square voor het model uit punt a nog geen 15 % bedroeg, bedraagt het hier meer dan 70%. Aangezien de afhankelijke variabelen van beide modellen verschillend zijn kan men niet besluiten dat het laatste model superieur is. Toch menen we dat de rekentijden van de nieuwe methode gemakkelijker te achterhalen zullen zijn dan bij de branch and bound methode met clusteren en reduceren.
Tevens werden het Akaike Information Criterion (AIC) en het Schwartz Information Criterion (SIC) berekend. Deze kunnen, in tegenstelling tot de R square, ook gebruikt worden om de voorspellende waarde van het model buiten de gegevens van de steekproef te testen. Beide waarden zijn respectievelijk 0.38 en 0.39.
Men ziet echter snel in dat bovenstaande formule approximatief is. De verwachte tijden voor vijf blokken en rijen tussen de tien en twintig zouden tussen de twee en vier seconden moeten liggen daar waar ze volgens deze formule tussen de één en twee seconden moeten liggen.
Een diepgaandere analyse dringt zich dus op. Daarom zal in het vervolg van dit punt een niet lineaire regressie gebruikt en geanalyseerd worden. Het nadeel van niet lineaire technieken is dat ze niet steeds tot een optimum leiden en dus waar mogelijk vermeden moeten worden. De duidelijke aanwezigheid van een exponentiële term dwingt ons echter tot het gebruik hiervan.
61
Voor de gekozen niet lineaire techniek werd de “Gauss-Newton” methode gekozen omwille van zijn snelle convergentie. Verschillende modellen werden getest en aangepast voor multicollineariteit en uiteindelijk werd tussen deze het model uitgekozen met een zo hoog mogelijk verklarende waarde (R square waarde van meer dan 78 %). Er werd eveneens op gelet dat convergentie bereikt werd.
Ook hier werden het Akaike Information Criterion en het Schwartz Information Criterion berekend. Deze bedragen respectievelijk 0.28 en 0.29. Deze lagere waarden tonen aan dat dit model te verkiezen is boven het voorgaande lineair model.
Ratrossfull = a**(blocks) + d*aisles + aaa
Voor bovenstaand model werden volgende parameters gevonden (ook hier werd eerst aan achterwaartse regressie gedaan).
Parameter a d aaa
Estimate
Approx Std Error
1.3556 0.0497 -3.0387
0.00351 0.00646 0.1035
Approximate 95% Confidence Limits 1.3487 0.0370 -3.2419
1.3625 0.0623 -2.8355
Dit leidt tot volgende formule.
Formule : Tijd nieuwe methode = 1.3556^(blokken) + 0.0497*rijen - 3.0387
De analyse van deze formule is vanzelfsprekend. Doch valt op dat de enige term die de benodigde tijd doet stijgen een exponentiële van het aantal blokken is. De tweede term is (zeker naarmate het aantal blokken stijgt) bijna verwaarloosbaar. Zoals verwacht zijn geen andere termen dan het aantal rijen en het aantal blokken significant. Als men op basis van deze formule de benodigde tijd schat voor vijf blokken en tussen de tien en twintig rijen komt men uit tussen de twee en drie seconden. Aangezien dit ongeveer is wat men ook op basis van de waarnemingen verwachtte, kan besloten worden dat bovenstaand model een redelijke benadering geeft.
62
3.Vergelijking van beide methoden De vraag dringt zich natuurlijk op in welk geval welke methode moet gebruikt worden. Enerzijds kunnen de opgestelde formules gebruikt worden. Anderzijds moet ook rekening gehouden worden met de grotere variantie gepaard gaande met de branch and bound (met clusteren en reduceren) methode. Zoals aangetoond (supra, p 55) is de standaarddeviatie van deze laatste bijna dubbel zo groot als die van de nieuw ontwikkelde methode.
Het bleek echter al meermaals dat de differentiërende factor het aantal blokken bleek te zijn. Hieronder worden dus nog een laatste maal beide methoden vergeleken opgesplitst naar het aantal blokken. Figuur 5.16 herhaalt en vergelijkt beide methodes opgesplitst naar het aantal blokken.
Figuur 5.16: Beide methodes opgesplitst naar het aantal blokken
63
Ook de analyse van de variantie verschilt waarschijnlijk met de hoeveelheid blokken. Hieronder worden dan ook de belangrijkste conclusies samengevat. Voor alle vier de beschouwde gevallen waren de resultaten significant. Ook hier past evenwel een waarschuwing. Op het geval met vijf blokken na was de R square en dus de mate waarin het model de resultaten kan interpreteren bijzonder laag (onder de 10% en soms zelfs onder de 5 %). The ANOVA Procedure Level of Class
N
Nieuwe methode 5 blokken Branch and bound 5 blokken
-------------Time-----------Mean Std Dev 200 200
2.67648094 0.53361934 0.67078410 1.64518643
The ANOVA Procedure Level of Class
N
Nieuwe methode 4 blokken Branch and bound 4 blokken
-------------Time-----------Mean Std Dev
200
200 0.35989829 0.07577973 0.92008047 2.31908240
The ANOVA Procedure Level of Class
N
Nieuwe methode 3 blokken Branch and bound 3 blokken
-------------Time-----------Mean Std Dev 200 200
0.05029396 0.01076823 0.75630056 2.65077077
The ANOVA Procedure Level of Class Nieuwe methode 2 blokken Branch and bound 2 blokken
N
-------------Time-----------Mean Std Dev
200
200 0.01230703 0.00459930 0.58841290 1.48500983
Het is duidelijk dat de variantie van de benodigde tijd van de nieuw ontwikkelde methode stijgt naarmate het aantal blokken stijgt (hoewel deze voor de onderzochte gevallen beperkt bleef). Dezelfde conclusie kan echter niet uitgebreid worden naar de branch and bound methode met clusteren en reduceren. Zoals verwacht, en kan worden afgelezen in voorgaande boxplots, blijft deze methode ten allen tijde relatief onbetrouwbaar.
Desalniettemin zijn er gevallen waar het gebruik van deze methode aan te raden is. Naarmate het aantal blokken stijgt, zal het onmogelijk worden om de nieuwe methode te gebruiken. In
64
zulke gevallen zal de methode van “clusteren en reduceren” toch een goede oplossing garanderen.
65
Besluit De nieuwe methode die ontwikkeld werd in deze scriptie is een uitbreiding op het algoritme van Ratliff en Rosenthal (1983) en Roodbergen en de Koster (2001b). Hierin wordt gezocht naar een optimale routing voor order pickers. Het aantal situaties waar het algoritme kan toegepast worden werd drastisch uitgebreid. Dit was mogelijk door het ontwikkelen van een algoritme dat het discreet tellen van equivalentieklassen (unieke manieren om de afgelegde weg te karakteriseren) overbodig maakte. Tevens konden alle noodzakelijke elementen, ter berekening van een optimale route, vanaf deze equivalentieklassen ook aangemaakt worden. Ten slotte werd de rekentijd van de methode ingeperkt door overbodige berekeningen achterwege te laten.
Voornoemde methode werd vergeleken met een andere optimale methode ter benchmark, gebaseerd op branch and bound. Ook hier werden eerst verbeteringen aangebracht (mogelijk door de specifieke layout van het probleem). Zo werden overbodige items verwijderd en werden ook onmogelijke routes achterwege gelaten. Factor van vergelijking betreft dan ook de rekentijden. Hoewel deze laatste methode vaak tot betrekkelijk goede resultaten kan komen is de variantie te hoog en vaak onaanvaardbaar in de praktijk. De nieuw ontwikkelde methode scoort beter wat dit betreft. Aanvaardbare rekentijden werden gevonden voor alle situaties uit het proefopzet.
Het reeds door voorvermelde auteurs aangekaarte probleem van exponentieel stijgende rekentijden naarmate het aantal blokken toeneemt, blijft echter bestaan. Computers met een voor vandaag de dag standaard kloksnelheid zijn echter in staat om voor de meeste praktische gevallen uitkomst te bieden. Voor andere situaties kan worden teruggevallen op de branch and bound methode of op verschillende bestaande heuristieken.
66
Referenties -
Applegate, D.L.,Bixby, R.E.,Chátal, V., Cook, W.,2006. The Traveling Salesman Problem Hfst 16, 489-529.
-
Applegate, D., Bixby, R., Chvátal, V., Cook, W., 2008. Concorde TSP Solver. URL
. (15/11/2009).
-
Bartholdi, J.J., Hackman, S.T., 2006. Warehouse and Distribution Science. Release 0.80. URL
. (10/09/2009).
-
Bozer, Y.A., Sharp, G.P., 1985. An empirical evaluation of general purpose automated order accumulation and sortation system used in batch picking. Material Flow 2, 111– 113.
-
Bozer, Y.A., Quiroz, M.A., Sharp, G.P., 1988. An evaluation of alternative control strategies and design issues for automated order accumulation and sortation systems. Material Flow 4, 265–282.
-
Brynzér, H., Johansson, M.I., 1996. Storage location assignment: using the product structure to reduce order picking times. International Journal of Production Economics 46, 595–603.
-
Chen, M.C., Huang, C.L., Chen, K.Y., Wu, H.P., 2005. Aggregation of orders in distribution centers using data mining. Expert Systems with Applications 28 (3), 453– 460.
-
Chen, M.C., Wu, H.P., 2005. An association-based clustering approach to order batching considering customer demand patterns. Omega International Journal of Management Science 33 (4), 333–343.
-
Chew, E. P., Tang, L.C., 1999. Travel time analysis for general item location assignment in a rectangular warehouse. European Journal of Operational Research 112, 582–597.
-
de Koster, R., Le-Duc, T., Roodbergen, K.J., 2007. Design and control of warehouse order picking: A literature review. European Journal of Operational Research 128, 481-501.
-
De Koster, R., Van der Poort, E.S., 1998. Routing orderpickers in a warehouse: A comparison between optimal and heuristic solutions. IIE Transactions 30, 469–480.
-
Frazelle, E.H., Hackman, S.T., Passy, U., Platzman, L.K., 1994.The forward–reserve problem. In: Ciriani, T.C., Leachman,R.C. (Eds.), Optimization in Industry 2. Wiley, New York,pp. 43–61. VII
-
Frazelle, E.A., Sharp, G.P., 1989. Correlated assignment strategy can improve orderpicking operation. Industrial Engineering 4, 33–37.
-
Gademann, A.J.R.N., Van den Berg, J.P., Van der Hoff, H.H., 2001. An order batching algorithm for wave picking in a parallel-aisle warehouse. IIE Transactions 33, 385–398.
-
Gademann, N., Van de Velde, S., 2005. Batching to minimize total travel time in a parallel-aisle warehouse. IIE Transactions 37 (1), 63–75.
-
Gilleland, M., Permutation Generator. URL . (02/05/2010).
-
Goetschalckx, M., Ashayeri, J., 1989. Classification and design of order picking systems. Logistics World (Juni), 99-106.
-
Goetschalckx, M., Ratliff, D.H., 1988a. An efficient algorithm to cluster order picking items in a wide aisle. Engineering Costs and Production Economy 13, 263–271.
-
Goetschalckx, M., Ratliff, D.H., 1988b. Order picking in an aisle. IIE Transactions 20, 531–562.
-
Hackman, S.T., Platzman, L.K., 1990. Near optimal solution ofgeneralized resource allocation problems with large capacities.Operations Research 38 (5), 902–910.
-
Hsu, C.M., Chen, K.Y., Chen, M.C., 2005. Batching orders inwarehouses by minimizing travel distance with genetic algorithms.Computers in Industry 56 (2), 169– 178.
-
Jewkes, E., Lee, C., Vickson, 2004. Product location, allocation and server home base location for an order picking line with multiple servers. Computers & Operations Research 31, 623–626.
-
Johnson, M.E., 1998. The impact of sorting strategies on automated sortation system performance. IIE Transactions 30, 67–77.
-
Johnson, M.E., Lofgren, T., 1994. Model decomposition speeds distribution center design. Interfaces 24 (5), 95–106.
-
Le-Duc, T., De Koster, R., 2003. An approximation for determining the optimal picking batch size for order picker in single aisle warehouses. In: Meller, R., Ogle, M.K., Peters, B.A., Taylor, G.D., Usher, J. (Eds.), Progress in Material Handling Research: 2002, pp. 267–286.
-
Le-Duc, T., De Koster, R., 2005a. Determining the optimal number of zones in a pickand-pack order picking system. Report ERS-2005-029-LIS, RSM Erasmus University, the Netherlands. VIII
-
Le-Duc, T., De Koster, R., 2007. Travel time estimation and order batching in a 2block warehouse. European Journal of Operational Research 176 (1), 374–388.
-
Meller, R.D., 1997. Optimal order-to-lane assignments in an order accumulation/sortation system. IIE Transactions 29 (4), 293–301.
-
Petersen, C.G., 1997. An evaluation of order picking routing policies. International Journal of Operations & Production Management 17 (11), 1098–1111.
-
Ratliff, H.D., Rosenthal, A.S., 1983. Orderpicking in a rectangular warehouse: A solvable case of the traveling salesman problem. Operations Research 31 (3), 507– 521.
-
Roodbergen, K.J., De Koster, R., 2001a. Routing methods for warehouses with multiple cross aisles. International Journal of Operations Research 39 (9),1865-1883.
-
Roodbergen, K.J., De Koster, R., 2001b. Routing order pickers in a warehouse with a middle aisle. European Journal of Operations Research 133, 32-43.
-
Roodbergen, K.J.,2001. Layout and Routing Methods for Warehouses. Ph.D. Thesis, RSM Erasmus Universiteit Rotterdam, The Netherlands.
-
Rosen, K. H., 1991.Discrete Mathematics and Its Applications, 2nd edition. NY: McGraw-Hill, 282-284.
-
Russell, M.L., Meller, R.D., 2003. Cost and throughput modelling of manual and automated order fulfilment systems. IIE Transactions 35 (7), 589–603.
-
Tang, L.C., Chew, E.P., 1997. Order picking systems: batching and storage assignment strategies. Computer & Industrial Engineering 33 (3), 817–820.
-
Theys, C., Bräysy, O., Dullaert, W., Raa, B.,2010. Using a TSP heuristic to routing order pickers in warehouses. European Journal of Operations Research 200, 755-763.
-
Tompkins, J.A.,White, J.A., Bozer, Y.A., Frazelle, E.H.,Tanchoco, J.M.A.,Trevino, 1996. Facilities Planning. Wiley, New York.
-
Tompkins, J.A., White, J.A., Bozer, Y.A., Frazelle, E.H., Tanchoco, J.M.A., 2003. Facilities Planning. John Wiley & Sons, NJ.
-
Van den Berg, J.P., Sharp, G.P.G.A.J.R.N., Pochet, Y., 1998. Forward–reserve allocation in a warehouse with unit-load replenishments. European Journal of Operational Research 111, 98–113.
-
Vaughan, T.S., Petersen, C.G., 1999. The effect of warehouse cross aisles on order picking efficiency. International Journal of Production Research 37 (4), 881–897.
IX
Appendix A : Inhoud CD-rom In deze bijlage wordt de inhoud van bijgevoegde Cd-rom toegelicht.
Volgende papers kunnen teruggevonden worden in de map “papers”:
Paper 1: de Koster, R., Le-Duc, T., Roodbergen, K.J., 2007. Design and control of warehouse order picking: A literature review. European Journal of Operational Research 128, 481-501.
Paper 2: Theys, C., Bräysy, O., Dullaert, W., Raa, B.,2010. Using a TSP heuristic to routing order pickers in warehouses. European Journal of Operations Research 200, 755-763.
Paper 3: Petersen, C.G., 1997. An evaluation of order picking routing policies. International Journal of Operations & Production Management 17 (11), 1098–1111.
Paper 4: Roodbergen, K.J.,2001. Layout and Routing Methods for Warehouses. Ph.D. Thesis, RSM Erasmus Universiteit Rotterdam, The Netherlands.
Paper 5: Ratliff, H.D., Rosenthal, A.S., 1983. Orderpicking in a rectangular warehouse: A solvable case of the traveling salesman problem. Operations Research 31 (3), 507– 521.
Paper 6: Roodbergen, K.J., De Koster, R., 2001b. Routing order pickers in a warehouse with a middle aisle. European Journal of Operations Research 133, 32-43.
Onder de map “kladblokbestanden” kunnen de volgende bestanden teruggevonden worden:
Excelbestand: Alle resultaten opgenomen in een excelbestand.
Type O, P, Q en R bevatten kladblokbestanden voor magazijnen met respectievelijk 5, 4, 3 en 2 blokken.
-1-
Deze zijn onderverdeeld naar:
Orders en ordersd: Bevat de kladblokbestanden met de te picken items in twee verschillende inputformaten.
Ordersclustered, 2 en 3: Bevat de kladblokbestanden met te picken items na clusteren in drie verschillende formaten.
DistanceMatrix: Bevat de kladblokbestanden van de afstandsmatrices.
DistanceMatrixclustered: Bevat de kladblokbestanden van de afstandsmatrices na clusteren.
DistanceMatrix2clustered: Bevat de kladblokbestanden van de afstandsmatrices na clusteren en reduceren.
In de map “programma’s” kunnen de volgende programma’s gevonden worden:
Clusterorders: Dit programma kan op basis van een orderpicklijst alle overbodige items verwijderen (zoals aangegeven in hoofdstuk 5).
Distance_matrix: Dit programma kan een afstandsmatrix opstellen op basis van een orderpicklijst.
Thesis_recursief: Dit programma kan alle equivalentieklassen aanmaken na ingave van het aantal blokken waaruit het magazijn bestaat.
Aislechange: Dit programma bepaald alle manieren om van rij j naar rij j+1 over te gaan. TablesLplus: Dit programma maakt een eerste versie aan van de Lj+ tabellen aan op basis van de equivalentieklassen. NaarLmin: Dit programma maakt de Lj- tabel aan op basis van de equivalentieklassen en de kolomovergangen.
-2-
Unification: Teneinde verbeteringen aan te brengen op voorgaande output moet deze eerst gestandaardiseerd worden. Benodigd zijn dus de kolomovergangen, de equivalentieklassen en de Lj- en Lj+ tabellen. Lpluselimination: Een eerste verbetering op de Lj+ tabellen op basis van de equivalentieklassen en de output van het vorige programma.
SearcherLplus: Een tweede verbetering op basis van de equivalentieklassen, kolomovergangen en voorgaande output van de Lj+ en Lj- tabellen. Finaalimproved2: Dit programma berekent tenslotte de optimale afstand op basis van voorgaande output en een orderpicklijst.
Random2: Dit programma maakt random orders aan.
ABC2: Dit programma maakt random orders aan op basis van ABC-classificatie
In de map statistiek zitten de volgende bestanden:
T-testen: Hierin zijn alle gebruikte gepaarde T-testen voor verschillen opgenomen.
Anova procedures: Hierin zijn alle gebruikte Anova procedures opgenomen.
Regressies: Hierin zijn zowel de lineaire als niet-lineaire regressies opgenomen.
In de map scriptie is de scriptie zelf opgenomen.
-3-
