Optimalisatie algoritme/keuze alternatief algoritme

[T i M]

In een stuk software probeer ik middels een algoritme de beste combinatie te vinden van locaties om een order te picken. Dat lukt goed en snel, behalve als er veel locaties nodig zijn om te voldoen aan de vraag in de order. Op dat moment wordt het onbruikbaar traag en om die reden zoek ik naar een optimalisatie/alternatief algoritme. Zoals uit dit topic blijkt heb ik daar hulp bij nodig.

Het algoritme zoekt uit welke combinatie van locaties gepicked moeten worden voor het kunnen uitleveren van een order.

De variabele zijn als volgt:

• Een order bestaat uit 1 of meerdere artikelen
• Een artikel op de order heeft een bestel hoeveelheid van 1 of meer
• Een locatie in het magazijn heeft een "gewicht". Dit is een nummeriek getal wat iets zegt over de moeilijkheid om te picken. Hoe lager, hoe gunstiger.
• Elk magazijn heeft een "gewicht". Dit is een nummeriek getal wat iets zegt over de toegankelijkheid. Hoe lager, hoe gunstiger.
• Eén artikel kan op verschillende locaties liggen in verschillende magazijnen

Het algoritme dient uit te zoeken welke set van locaties een zo laag mogelijke score oplevert (dit zijn de gewichten geconfigureerd op locatie & magazijn niveau).

Op dit moment heb ik een redelijk eenvoudig backtrack algoritme geimplementeerd wat alle mogelijk combinaties afloopt en uiteindelijk het resultaat met de laagste score teruggeeft. Dit werkt perfect, maar indien er veel verschillende locaties nodig zijn om te voldoen aan de vraag in de order en er staan veel regels in de order dan zijn het aantal combinaties te groot om in redelijk tijd af te lopen. Voorbeeld hiervan is een order waarbij er 25 locaties zijn om te checken en er tenminste 10 locaties nodig zijn om te voldoen aan de vraag. In dat geval is het te maken aantal combinaties 25¹⁰.

Ik ben niet op zoek naar een oplossing, maar vooral tips/suggesties voor alternatieve oplossingsrichtingen. De aanpak nu om simpelweg te bruteforcen gaat niet nooit efficient worden bij een groot aantal combinaties.

[Maks]

Een interessant probleem waar gelukkig wel veel literatuur over te vinden is (omdat het een standaard operations research probleem is). Volgens mij is dit een NP-hard probleem dus daarom is het inderdaad niet haalbaar om dit met een backtrack oplossing te doen.

Als je zoekt op particle swarm of neural network order picking optimization kom je best een eind denk ik. Via * knip * kan je papers downloaden die achter een paywall zitten, denk dat je op basis daarvan wel een idee krijgt wat goed zou kunnen werken. Al gaat de standaard literatuur wel vaak over pad-optmalisatie (TSP) terwijl dat hier niet aan de orde is denk ik? Dat maakt het probleem eigenlijk alleen maar eenvoudiger dus dat is wel mooi.

Daarna ben je wel wat tijd kwijt met een goede implementatie al zijn er gelukkig genoeg libraries in de meeste programmeertalen beschikbaar.

[ Voor 1% gewijzigd door .oisyn op 04-10-2021 14:51 ]

[fopjurist]

T i M schreef op woensdag 22 september 2021 @ 15:27:
Het algoritme dient uit te zoeken welke set van locaties een zo laag mogelijke score oplevert (dit zijn de gewichten geconfigureerd op locatie & magazijn niveau).

Hoe wordt de score precies berekend? Tel je het magazijngewicht twee keer als je twee artikelen uit dat magazijn haalt? Tel je het locatiegewicht twee keer als je twee artikelen uit dezelfde locatie haalt? Komt het regelmatig voor dat een order groter is dan wat er op één beschikbaar is, of hoef je met de capaciteit geen rekening te houden?

[T i M]

Maks schreef op woensdag 22 september 2021 @ 15:37:
Een interessant probleem waar gelukkig wel veel literatuur over te vinden is (omdat het een standaard operations research probleem is). Volgens mij is dit een NP-hard probleem dus daarom is het inderdaad niet haalbaar om dit met een backtrack oplossing te doen.

Als je zoekt op particle swarm of neural network order picking optimization kom je best een eind denk ik. Via * knip * kan je papers downloaden die achter een paywall zitten, denk dat je op basis daarvan wel een idee krijgt wat goed zou kunnen werken. Al gaat de standaard literatuur wel vaak over pad-optmalisatie (TSP) terwijl dat hier niet aan de orde is denk ik? Dat maakt het probleem eigenlijk alleen maar eenvoudiger dus dat is wel mooi.

Daarna ben je wel wat tijd kwijt met een goede implementatie al zijn er gelukkig genoeg libraries in de meeste programmeertalen beschikbaar.

Klopt. Het betreft geen TSP in dit geval dat maakt het inderdaad wat makkelijker. Alvast bedankt voor je tips.

[ Voor 1% gewijzigd door .oisyn op 04-10-2021 14:52 ]

[T i M]

fopjurist schreef op woensdag 22 september 2021 @ 16:07:
[...]

Hoe wordt de score precies berekend? Tel je het magazijngewicht twee keer als je twee artikelen uit dat magazijn haalt? Tel je het locatiegewicht twee keer als je twee artikelen uit dezelfde locatie haalt? Komt het regelmatig voor dat een order groter is dan wat er op één beschikbaar is, of hoef je met de capaciteit geen rekening te houden?

Het magazijngewicht telt maximaal 1 keer. De locatie telt één keer per product, ongeacht het aantal stuks. Er wordt nu rekening gehouden met capaciteit. Het komt regelmatig voor dat op één locatie niet genoeg voorraad ligt voor het aantal in de order. In dat geval moeten er meerdere locaties gepicked worden, of een andere locatie met wel voldoende voorraad. Afhankelijk van de score wordt die keuze uiteindelijk gemaakt.

[fopjurist]

Het probleem is NP-moeilijk want Vertex Cover is een bijzonder geval. Je kunt een instantie van Vertex Cover in polynomiale tijd vertalen naar jou probleem: laat (V,E) de verzameling van knopen en kanten, dan kies je E voor de artikelen en V voor de magazijnen. Elk artikel e ∈ E is beschikbaar in de twee magazijnen {i,j} ∈ e. Magazijnen hebben kosten 1, locaties hebben kosten 0. Er is een vertex cover van grootte k dan en slechts dan als je alle artikelen kunt ophalen tegen kosten k.

Dat betekent dat een algoritme dat polynomiaal schaalt niet bestaat tenzij (P=NP), al is het best mogelijk dat er een algoritme bestaat dat kleine gevallen goed op kan lossen (waarbij 'klein' in de praktijk al je orders kan omvatten). Je zou zo'n algoritme kunnen proberen te vinden. Ik zal je twee praktische suggesties geven:

1. Formuleer het probleem als een geheeltallig optimalisatieprobleem. Er zijn programma's beschikbaar die zulke problemen efficiënt oplossen, of anders in de praktijk tenminste een niet-optimale maar goede oplossing geven. Er zijn gratis programma's beschikbaar maar de betaalde oplossingen zijn aanmerkelijk sneller.

2. Maak zelf een algoritme dat niet altijd de optimale oplossing geeft maar probeert om de beste oplossing te vinden in de beschikbare tijd. Zulke algoritmes werken meestal door uit te gaan van een bepaalde startoplossing (geheel willekeurig gegenereerd of ook met slimmigheidjes) en die oplossing via kleine veranderingen te verbeteren (local search). Bij kleine veranderingen kun je denken aan het toevoegen of verwijderen van een magazijn, of allebei tegelijk.

[Matis]

Interessant vraagstuk

Ik zit op mobiel dus kan niet eenvoudig typen, maar is het een idee om dit in een Spatial database te gieten?
https://www.sciencedirect...mathematics/spatial-query

En dan ieder stock item op de kaart te leggen en de afstand tot het centrum het gewicht te laten zijn?

Daarnaast hoeft je volgens mij niet de hele order in één keer af te lopen, maar kun je beginnen per orderregel.
Dat reduceert de aantal permutaties enorm.

[ Voor 30% gewijzigd door Matis op 22-09-2021 21:05 ]

[Voutloos]

Matis schreef op woensdag 22 september 2021 @ 21:03:
Daarnaast hoeft je volgens mij niet de hele order in één keer af te lopen, maar kun je beginnen per orderregel.
Dat reduceert de aantal permutaties enorm.

Wellicht zit je dan nog vrij ver van de optimale oplossing omdat de volgorde van je orderregels random is.
Dan zou je een goedkope manier moeten hebben om als voorbereiding de regels te ordenen. Bijvoorbeeld producten die maar op 1 locatie liggen eerst zou enorm helpen als magazijngewichten relatief zwaar meetellen tov locatiegewichten. Je heuristiek stuurt je wel bepaalde locale maxima in.
Alternatief: Per regels is niet meer exponentieel, de totale berekening zou dusdanig mee kunnen vallen dat je het per-regel-algo een aantal keer kan proberen met random regel volgordes.

Wat misschien ook een interessante uitkomst heeft: Het bestaande uitputtende algoritme geeft de optimale oplossing. Stel nou dat je de berekening ophakt in batches van x regels waarvan je weet dat je het nog wel past in redelijke tijd, zou het best kunnen dat er een redelijk goede totaalscore is. En ook dan zou je de volgorde/batches misschien goedkoop kunnen sturen, bijvoorbeeld eerst enkel een batch voor het magazijn welke de meeste producten kan voorzien.

[ Voor 7% gewijzigd door Voutloos op 22-09-2021 22:43 ]

[Anoniem: 80910]

Misschien levenstheim loslaten op de gevallen, maar dan zul je iets moeten doen met letters

[Voutloos]

Totaalscore is een getal, dus scores vergelijken is al eenvoudig.
En veel Levenshtein implementaties zijn ook hilarisch traag.

[T i M]

Matis schreef op woensdag 22 september 2021 @ 21:03:
Daarnaast hoeft je volgens mij niet de hele order in één keer af te lopen, maar kun je beginnen per orderregel.
Dat reduceert de aantal permutaties enorm.

Dat gaat niet helemaal werken in de praktijk. Een van de zaken die we proberen te optimaliseren is dat je maar naar 1 magazijn hoeft ipv meerdere.

Van alle reacties ga ik eerst even in de theorie duiken om te zien of er interessante opties tussen zitten.

[Matis]

Ik heb er vanochtend nog eens over nagedacht tijdens het hardlopen en ik wil je de volgende tips meegeven.

Ikzelf heb een stuk software ontwikkeld, echter dan voor boeken. Momenteel hebben we 24 miljoen exemplaren verdeeld over 4 leveranciers.
Wat wij, voor ieder boek doen, is een voorkeursleverancier bepalen. Deze voorkeursleverancierbepaling doen wij op basis van een aantal businesrules, jij zou ze (simpelweg) op het gewicht van de voorraad locatie(s) kunnen doen.
Wanneer de voorraadposities, prijzen, productbeschikbaarheid etc etc wijzigt van een product, wordt voor dit product opnieuw de voorkeursleverancier bepaald. Dat gebeurt near-realtime.

Wanneer we een order ontvangen, kijken we per orderregel (artikel) eerst of de voorkeursleverancier kan leveren. Zo ja, dan plaatsen we daar de bestelling. Als deze de order niet of niet in zijn geheel kan leveren, gaan we on-the-fly op zoek naar een tweede beste leverancier. enz enz. Tussendoor boeken we dan ook fictief de beschikbare voorraad voor die leverancier af.

Op die manier kunnen we heel snel een voorselectie maken op de beste leverancier voor dat product en de beschikbaarheid er van.

De vraag die jij jezelf moet stellen is dan ook: Wil ik altijd 100% zeker te weten het aller-aller-allerbeste advies geven, of is 95% ook "goed genoeg".
Bovenstaande percentages zijn arbitrair gekozen. Ik hoop je daarmee wel inzicht te geven hoe moeilijk jij het het voor jezelf wilt maken.

Ik vind het overigens een fascinerend vraagstuk, want ik sukkel zelf soms ook met deze (theoretische) kwesties

[ Voor 6% gewijzigd door Matis op 24-09-2021 11:28 ]

[P_Tingen]

Weet niet of je het inmiddels opgelost hebt, maar een paar jaar geleden had ik een vergelijkbaar probleem. In het kort: we moesten tabak verzamelen voor een recept. Een recept bestaat typisch uit 10-27 verschillende kwaliteiten tabak. Van elke kwaliteit hebben we gemiddeld zo'n 10 balen op voorraad. Dit kan liggen in verschillende pakhuizen, verspreid over de wereld. Mocht een kwaliteit niet voorhanden zijn, dan is er een alternatieve kwaliteit gedefinieerd. Een gemiddeld recept heeft zo'n 15 kwaliteiten tabak wat dus zo'n 15^10 mogelijkheden oplevert met uitschieters tot orders van grootte meer. De opdracht is om een set van tabaksbalen te vinden die valt binnen minimum en maximum teer- en nicotine-eisen, niet meer dan x% aan suikers bevat en zo mogelijk de oudste tabak eerst gebruikt, het liefst verspreid over zo weinig mogelijk pakhuizen.

We hebben dat uiteindelijk met een combinatie van brute force en slimmigheden opgelost in een c# applicatie. We sorteren de tabaksbalen op volgorde van leeftijd/kwaliteit en laten dan brute force een programma alle mogelijke combinaties bepalen die er mee mogelijk zijn. Dit proces levert zijn combinaties aan een tweede proces die alle aangeleverde combinaties ordent op "geschiktheid". In ons geval betekende dat, dat we combinaties die uit 1 pakhuis geleverd kunnen worden het liefste hebben. Daarbinnen het liefste de combinaties die gemaakt kunnen worden zonder gebruik te maken van alternatieven en daar weer binnen de combinaties met gemiddeld gezien de oudste tabak.

Dit hele proces is tijd-gebonden. We rekenen maximaal 5 seconden en pakken dan de combinatie die op dat moment bovenaan in de ranglijst staat. Onze "combinator" was in staat zo'n 50 miljoen combinaties per seconde te berekenen (24 parallelle processen op een 24-core machine schiet wel op), het tweede proces, de classificator had het uiteraard minder druk.

Dit principe was een behoorlijke verbetering tov de oude procedure, die zo'n 50000 combinaties kon doorrekenen in een half uur.

Ben benieuwd wat de status is van je project.

[T i M]

Inmiddels is het probleem opgelost. We hebben ons gefocust op het minimaliseren van de hoeveelheid data die we aan het algoritme geven.

In het voorstadium waren we in staat om al een voorselectie te doen van locaties. Wat we in feite doen is de mogelijke combinaties per magazijn samenstellen. Vervolgens start het algoritme met backtracken op basis van warehouse. Ipv enkel kijken naar locaties (en dan pas het magazijn "gewicht") kan het algoritme nu al heel snel een volledig magazijn uitsluiten en dat verlaagt het aantal te maken combinaties enorm.