Sorteermethoden

[Dorgaldir]

Hey,

ik zit met een denkoefening en volgens mij bestaat er een algoritme voor, enkel kan ik echt niet op de naam komen en via sorteer methoden blijf ik bij dingen zoals bubble sort, maar daar heb ik weinig aan.

De situatie is als volgend: je hebt een magazijn met X aantal locaties en Y aantal producten.
De producten geraken met der tijd meer en meer door elkaar, locaties worden wel per doos gescand dus er is geweten welk product waar zit.
Door de verspreiding van de producten moeten de orderpickers veel rond lopen. dus wil men een script dat van een bepaald product alle dozen opzoekt op de verschillende locaties en dan een berekent op welke manier dit product efficienter kan gestockeerd worden. (samenvoegen van 2 locaties naar 1 als beide niet vol zijn, 2 kleine locaties samenvoegen in 1 grote als ze wel vol zijn,...)

Er moet dus uit wat informatie de beste optie samengesteld worden. En als ik me niet vergis bestaan daar algoritmes voor, maar ik kan ze niet vinden, dus als iemand weet hoe dat deze noemen of hoe ik dat kan vinden zodat ik die kan bekijken en op basis van die info verder kan met dit script, dan zou ik heel dankbaar zijn

[storeman]

Volgens mij kan een insteek het "travelling salesman problem" zijn, hiervoor bestaan verschillende oplossingen. Google er eens op, zou ik zeggen.

[Dorgaldir]

Daar heb ik al wat aan
Als je de juiste termen hebt is het zoeken op google best simpel, maar ik kwam echt niet op een bewoording die google begreep

[TheNephilim]

Herkenbaar! Je weet wel ongeveer wat je moet hebben, maar niet hoe het heet

[Woy]

Ik denk ook aan het "Bin Packing" probleem als ik je beschrijving zo lees. Misschien nog i.c.m. wat TSP voor de afstanden inderdaad.

Overigens heb je het in je beschrijving over het feit dat er telkens naar 1 product gekeken wordt. Ik denk dat er uiteindelijk meer winst gehaald kan worden als er naar meerdere producten tegelijk gekeken wordt. Het probleem wordt daar natuurlijk wel een stuk complexer mee.

[ Voor 54% gewijzigd door Woy op 23-04-2014 10:32 ]

[PrisonerOfPain]

storeman schreef op woensdag 23 april 2014 @ 09:35:
Volgens mij kan een insteek het "travelling salesman problem" zijn, hiervoor bestaan verschillende oplossingen. Google er eens op, zou ik zeggen.

Traveling salesman gaat op als je zelf geen controle hebt over de locaties van de producten. Waarschijnlijk kun je met wat kennis van de layout en de frequency of use van de producten al een heel eind komen. Gewoon zorgen dat de meest frequente producent dicht bij elkaar staan en wellicht dingen een beetje uit spreiden om contentie te voorkomen.

[Loy]

Wat je volgens mij zoekt is niet zo zeer een sorteermethode maar meer een clusteringsmethode, die alle dezelfde producten bij elkaar zet.
Daarbij moest ik meteen denken aan een java-applet die ik ooit gezien heb (java-applets, dus way back en ik kan 'm ook niet vinden helaas). Daarin struinden mieren random rond, als we iets tegenkwamen 1 item meenamen en weer dropten als ze een item van dezelfde soort tegenkwamen. Langzaam komen dus alle item van dezelfde soort bij elkaar.

Doordat het mieren simuleert heet het een Ant Colony Optimization en het zag er uit als dit: YouTube: Cache Consensus: Trial 1 / 3.

[KopjeThee]

Dorgaldir schreef op woensdag 23 april 2014 @ 09:31:
...magazijn met X aantal locaties en Y aantal producten....
...Door de verspreiding van de producten moeten de orderpickers veel rond lopen...

Het lijkt me dat je met een optimalisatie probleem te maken hebt. Maar het is mij nog niet helemaal duidelijk wat er precies geoptimaliseerd moet worden.

Ik kan mij voorstellen dat het probleem als volgt is:
Minimaliseer de gemiddelde tijd dat orderpickers voor een order door het magazijn lopen, door het rangschikken van de producten in het magazijn.

Dan kan je je nog afvragen of orderpickers ook meerdere orders tegelijk mogen bij elkaar zoeken.

Verder lijkt het me van belang dat je ook niet te vaak wilt herrangschikken, omdat dan die kosten te ver gaan oplopen.

Voor een optimalisatie techniek zou ik zoeken op "local search" en "simulated annealing". En misschien nog veel meer van toepassing:
Wikipedia: Apriori algorithm vaak gebruikt voor Wikipedia: Affinity analysis
Je gaat eigenlijk al je oude orders doorlopen om te zien wat klanten vaak tegelijk kopen, en plaats producten die vaak samengaan dichter bij elkaar. Gevoelsmatig zou dat al dichtbij een goede oplossing voor je optimalisatieprobleem moeten komen.

[ Voor 3% gewijzigd door KopjeThee op 23-04-2014 13:35 ]

[Dorgaldir]

Veel boeiende en handige informatie al

Ik zal het nog even wat verduidelijken wat ik nu probeer te doen, het gehele project bevat veel meer maar nu ben ik specifiek bezig het het her rangschikken van de producten.

Door de manier waar momenteel op gewerkt word moet er een manier komen om te automatisch te berekenen welke producten te verspreid zijn en beter samengevoegd kunnen worden. bvb producten die verspreid zijn over 2 locaties maar waarvan er eigenlijk zo weinig dozen van zijn dat ze beter op 1 locatie staan.
De producten moeten niet zo zeer samen staan op nabijgelegen locaties, er komt ook een onderdeel waarin dat de optimale route word berekend, van voor naar achter door het magazijn en meenemen wat je tegenkomt ipv te gaan zoeken. Het is gewoon de bedoeling dat op 1 locatie maar 1 product ligt en dat de ruimte die we hebben zo efficient mogelijk gebruikt word zodat er altijd het maximum aantal lege locaties zijn en niet een hoop half volle locaties.

[HuHu]

Ik denk dat je verschillende losse problemen hebt die je één voor één kunt oplossen en dan later samenvoegen.

Producten liggen te verspreid. Maar hoe bepaal je dat? Daar moet je een maat voor vinden. Diameter van de kleinste cirkel waar ze in passen?

Locatiebepaling: producten moeten naar 1 locatie. Welke? Alles naar waar nu de grootste voorraad ligt? Of naar een nieuwe locatie waar genoeg plek is? Hoeveel mag er verplaatst worden? Maximum aantal lege locaties is niet per se een handige oplossing, want verplaatsen kost ook tijd/geld/kracht.

Routeberekening: wat moet waarheen? Hoe? Wie? Wil je dat je verschillende sorteerders en orderpickers hebt, of dat de orderpickers tussendoor producten ook sorteren/groeperen?

Splits je probleem in kleine stukjes en los die eerst op.

[ Voor 4% gewijzigd door HuHu op 23-04-2014 13:49 ]

[KopjeThee]

Dorgaldir schreef op woensdag 23 april 2014 @ 13:38:
... welke producten te verspreid zijn en beter samengevoegd kunnen worden. bvb producten die verspreid zijn over 2 locaties maar waarvan er eigenlijk zo weinig dozen van zijn dat ze beter op 1 locatie staan...

Waarom? Wat ben je hier aan het optimaliseren?

De producten moeten niet zo zeer samen staan op nabijgelegen locaties, er komt ook een onderdeel waarin dat de optimale route word berekend, van voor naar achter door het magazijn en meenemen wat je tegenkomt ipv te gaan zoeken.

Dan nog ben je beter af qua tijd als producten die je vaak samen hebt dicht bij elkaar staan. Waarom zou je van voor tot achter je magazijn doorgaan als je ook alles al bij elkaar kunt zetten wat je vaak samen nodig hebt?

Het is gewoon de bedoeling dat op 1 locatie maar 1 product ligt en dat de ruimte die we hebben zo efficient mogelijk gebruikt word zodat er altijd het maximum aantal lege locaties zijn en niet een hoop half volle locaties.

Het is maar de vraag of het efficiënt is om 1 product maar op 1 locatie te hebben. Waarom is dit een doel? Voor het overzicht hoeft het niet, want dat was er toch al. Of is het ruimtebesparing?

[HuHu]

1 product op 1 locatie is ook niet altijd handig inderdaad. Het handigste (lijkt me) is als veel verkochte producten vooraan staan en producten die vaak samen worden gekocht naast elkaar. Dan kan het ook handig zijn om een vaak verkocht product te verspreiden over meerdere locaties, om dat het orderpicken te versnellen.

[KopjeThee]

HuHu schreef op woensdag 23 april 2014 @ 14:09:
1 product op 1 locatie is ook niet altijd handig inderdaad. Het handigste (lijkt me) is als veel verkochte producten vooraan staan en producten die vaak samen worden gekocht naast elkaar. Dan kan het ook handig zijn om een vaak verkocht product te verspreiden over meerdere locaties, om dat het orderpicken te versnellen.

Het zou denk ik beter zijn als het probleem iets concreter wordt, nu is het vrij abstract. Een veel verkocht product op meerdere plaatsen opslaan kan mogelijk ook wachtrijen op 1 specifieke locatie voorkomen. Ik heb geen idee of zoiets aan de orde is.

[MicGlou]

KopjeThee schreef op woensdag 23 april 2014 @ 19:51:
[...]

Het zou denk ik beter zijn als het probleem iets concreter wordt, nu is het vrij abstract. Een veel verkocht product op meerdere plaatsen opslaan kan mogelijk ook wachtrijen op 1 specifieke locatie voorkomen. Ik heb geen idee of zoiets aan de orde is.

Ik dacht exact hetzelfde... dit topic leek mij wel interessant want ik ben redelijk thuis in warehouse management. Maar na het lezen van de diverse reacties van de TS ben ik een beetje in de war geraakt.

Ik krijg in eerste instantie het idee dat de TS vooral wilde optimaliseren om het orderpicken efficiënter te maken. Hij krijgt daar een aantal uitstekende tips voor, maar iets later gooit de TS het volgens mij weer over een andere boeg. Want dan spreekt de TS over het optimaliseren van de vrij beschikbare locaties, oftewel er moet meer ruimte komen. Dat zijn toch twee compleet verschillende dingen die in de praktijk niet altijd goed met elkaar stroken... hangt bijvoorbeeld heel veel af van de producten (omvang/gewicht), hoeveelheden... de omvang van het project ansich is cruciale informatie.

Dus Dorgaldir... maak het idd is wat concreter, waar gaat het om? Gewichten, formaten, hoeveelheden... hoe groot is het magazijn, om hoeveel pallets/locaties gaat het?

[Bolukan]

De optimale strategie is afhankelijk van het patroon in je picking orders en welke goederen met welke kenmerken hoe hard lopen. Daar zijn hele boeken vol mee geschreven.Niet om reclame te maken, maar om voorgaande aan te tonen dat er niet een logische oplossing is zonder achtergrondinfo, heb ik een verhaal of nog een voor je gegoogled.

[ Voor 24% gewijzigd door Bolukan op 23-04-2014 20:41 ]

[Dorgaldir]

MicGlou schreef op woensdag 23 april 2014 @ 20:23:
[...]

Dus Dorgaldir... maak het idd is wat concreter, waar gaat het om? Gewichten, formaten, hoeveelheden... hoe groot is het magazijn, om hoeveel pallets/locaties gaat het?

Het gaat een beetje om beiden. Maar in eerste instantie over het herschikken van de producten. het is namelijk zo (had ik misschien wel duidelijker kunnen vermelden) dat we locaties tekort komen voor producten omdat deze ingenomen worden door andere producten.
Locaties worden ook toebedeeld door een script dat nu al in gebruik is.

Alle producten zitten in dozen, en daar zijn maar 2 formaten van, grote en kleine, de grote zijn 2X de kleine. Dus als op een locatie 20 grote kunnen staat, kunnen er ook 40 kleine staan.
We hebben grote locaties van 20 grote dozen, en kleine locaties van 8 grote dozen

Het is de bedoeling dat op 1 locatie maar 1 product staat, om het orderpicken van grote orders te vergemakkelijken.

Maar door de manier van werken geraken producten teveel verspreid, bvb van product X zijn er 15 dozen, maar ipv dat die p 1 locatie staan van 20 dozen staan die bvb op 2 locaties (10 op locatie a, en 5 op locatie b)
Dit zou nu een simpel voorbeeld zijn want het totaal aantal dozen is kleiner dan het aantal doos plaatsen op een locatie, maar er zijn zo producten met 100+ dozen die nu op 7 of 8 locaties staan en die dus maar eigenlijk 5 locaties zouden mogen gebruiken. Of producten die nog zeldzaam waren en in eerste instantie op kleine locaties stonden maar waar nu 30 dozen van zijn en die verspreid staan over 4 kleine locaties ipv 2 grote. (we proberen zo veel mogelijk hetzelfde type locaties bij een product te houden, afhankelijk van het aantal dozen in stock, zo kan een vroeger populair product nog wel op een grote locatie staan maar eigenlijk nog maar 4 dozen bevatten, dat zou dan weer terug moeten naar een kleine locatie)

Momenteel zitten we door de verspreiding van al die producten met te weinig kleine locaties zodat we die niet kunnen toewijzen aan een andere nieuwe producten.

We proberen de producten ook een beetje bij elkaar te zetten, elke gang heeft zo zijn voorkeurs merk. Maar bij plaatsgebrek word gewoon de volgende gang genomen, dus dit is niet vast, dit is ook niet nodig want dat zal opgevangen worden door de route die de orderpickers zullen krijgen in een later stadium (nu krijgen ze gewoon de lijst met locaties) zodat ze niet moeten zoeken.

Het is nogal complex en het zijn inderdaad veel verschillende dingen door elkaar en er zit ook wat druk achter want ze hadden dit liefst klaar alvorens mijn 2 weken vaderschaps verlof beginnen eens mijn hoogzwangere vrouw bevalt (nog een week, max 2). Dus ik zit zelf ook wel onder wat zenuwen en stress, vandaar de onduidelijke uitleg denk ik

[HuHu]

Is het niet mogelijk om gewoon handmatig een logische indeling te maken? Maak een lijstje welke producten te verspreid staan, kijk waar er plek is en begin met schuiven. Heb je geen computerprogramma voor nodig.

[Dorgaldir]

Het zou door de mensen in het magazijn elke week opnieuw gedaan moeten worden voor een aantal producten, en we willen niet dat er mensen zich bezig houden met de locaties en de dozen, dat moet allemaal via een script bepaald worden om zo de mensen te ontlasten en menselijke fouten te vermijden.

Orders zijn orders

[Orion84]

Dit klinkt een beetje hetzelfde als het defragmenteren van een harde schijf (al dan niet incl. optimalisatie door veelgebruikte bestanden op een snel deel van de schijf te zetten).

Producten die verspreid staan over meerdere locaties is vergelijkbaar met grote bestanden die versnipperd over de schijf staan. Onderbezette locaties zijn het equivalent van ruimtes tussen bestanden op de schijf (die ieder voor zich te klein zijn om een nieuw groot bestand te kunnen bevatten, maar samen wel een boel ruimte vertegenwoordigen).

Zijn daar geen algoritmes voor te vinden die met wat aanpassingen toe te passen zijn op je magazijn?

Hier wordt dezelfde parallel getrokken: http://garethharris.com/controlmodels/warehouse-example.html

Hier een paper dat juist de andere kant op gaat: http://dspace.mit.edu/openaccess-disseminate/1721.1/5938
Door producten juist wel te spreiden heb je meerdere opties om een product in een pick-route te verwerken, waardoor je die routes beter kan optimaliseren. In de referenties van dat paper staan wellicht nog wel papers die nuttig kunnen zijn (voor zover je ze kan vinden).

[ Voor 64% gewijzigd door Orion84 op 24-04-2014 14:42 ]

[Coca-Cola]

Dorgaldir schreef op donderdag 24 april 2014 @ 14:16:
Het zou door de mensen in het magazijn elke week opnieuw gedaan moeten worden voor een aantal producten, en we willen niet dat er mensen zich bezig houden met de locaties en de dozen, dat moet allemaal via een script bepaald worden om zo de mensen te ontlasten en menselijke fouten te vermijden.

Orders zijn orders

offtopic:
Ik las: 'om zo de mensen te ontslaan'

[Dido]

storeman schreef op woensdag 23 april 2014 @ 09:35:
Volgens mij kan een insteek het "travelling salesman problem" zijn, hiervoor bestaan verschillende oplossingen. Google er eens op, zou ik zeggen.

offtopic:
"Oplossing" en "TSP" in 1 zin kan misleidend zijn.