Permalänk

Traveling Salesman 2d/3d

Hej!

Min arbetsplats rymmer ett lager, där det finns gångar med olika plockplatser på både längden och höjden.

Det är enligt formatet hylla (H), rad (R), och våning (V) utformat som HHRRV och en specifik plats kan skrivas som tex 01057, hylla 01, rad 05, våning 7.

En plockgång kan ha 2 hyllor, 1 på varje sida. I denna gången kör man fram- och tillbaka med truck och hissar sig upp och ner efter plocklistor.

Dessa listor har dock begränsningar. Dom sorteras bara efter rader och tar inte hänsyn till närmsta väg. Om jag inte är ute och cyklar så blir väl problemet genast mer komplicerat när man inför 3 dimensioner, dvs 2 hyllor?

Vad är er syn på detta, går det att lösa utan att göra det till ett större projekt?

Permalänk
Medlem

Jag ser inte riktigt hur det skulle påverka att ha en z koordinat som du ändå bara kan färdas i x och y som hyllorna annars är i vägen och trucken inte kan flyga.
Finns det inte även begränsningar angående att köra med gafflarna uppe av säkerhetsskäl, om man nu skulle kunna spara lite tid genom att inte hissa ner gafflarna inför nästa hylla, om man kan ta flera saker på en tur.

Visa signatur

Someone said that money can't buy everything... That person didn't know where to shop

Permalänk
Medlem

Spontant tror jag inte att det blir mer komplicerat, det som händer borde vara att ditt mått för avstånd baseras på 3d men fungerar på samma sätt (du räknar fortfarande ut avståndet mellan alla punkter). Om någon dimension är jobbigare kan du vikta den för att kompensera.

Visa signatur

RAID is not a backup

Permalänk
Hedersmedlem

Det blir väl bara att man tar höjden i hänseende också. Man kollar ju bara på sträckor, så höjden läggs till på totala sträckan mellan två punkter.

Permalänk

Jag pratar om plocktruck där man höjer upp sig själv och plockar saker i en låda. Trucken åker fram- och tillbaka och man har en hylla precis på sin vänstersida och en hylla precis till höger. Så när man plockar tex 01014 så vore det även optimalt att plocka 02014.

Skickades från m.sweclockers.com

Permalänk
Medlem
Skrivet av RobinJacobsson:

Jag pratar om plocktruck där man höjer upp sig själv och plockar saker i en låda. Trucken åker fram- och tillbaka och man har en hylla precis på sin vänstersida och en hylla precis till höger. Så när man plockar tex 01014 så vore det även optimalt att plocka 02014.

Skickades från m.sweclockers.com

och det gör de andra också. Gör din läxa själv

Permalänk
Skrivet av JeanC:

och det gör de andra också. Gör din läxa själv

Vadå läxa? Och Enity pratar om att höja och sänka gafflar. Så ditt inlägg har ju absolut ingen substans eller värde för min trådstart. Vänligen låt bli att kommentera om du inte har något vettigt att komma med.

Och till er andra, det stämmer ju att det inte borde spela någon roll. _ _ 01 1 är ju av samma värde i sträcka som _ _ 01 1 eftersom man redan är där, så att säga.

Skickades från m.sweclockers.com

Permalänk
Medlem
Skrivet av RobinJacobsson:

Jag pratar om plocktruck där man höjer upp sig själv och plockar saker i en låda. Trucken åker fram- och tillbaka och man har en hylla precis på sin vänstersida och en hylla precis till höger. Så när man plockar tex 01014 så vore det även optimalt att plocka 02014.

Oavsett om det är på övre eller undre hyllan så är det ändå till den platsen som du måste åka. Så den extra axlen är inte relevant för rutten. Det är väl inte så att du skulle åka till en annan gång längre bort och hoppa över en som är nära bara för att du är upphöjd? Eller går det snabbare att komma till en annan gång än att ändra upphöjdhet på trucken.

Ge oss lite tidssiffror

Kan du ändra upphöjdhet medans du kör eller måste du stå stilla. Vad är det för regler runt om beräkningen?

Visa signatur

Hur många datorer är för många?

Permalänk
Skrivet av kelthar:

Oavsett om det är på övre eller undre hyllan så är det ändå till den platsen som du måste åka. Så den extra axlen är inte relevant för rutten. Det är väl inte så att du skulle åka till en annan gång längre bort och hoppa över en som är nära bara för att du är upphöjd? Eller går det snabbare att komma till en annan gång än att ändra upphöjdhet på trucken.

Ge oss lite tidssiffror

Kan du ändra upphöjdhet medans du kör eller måste du stå stilla. Vad är det för regler runt om beräkningen?

Det är ca 7 m högt med 9 platser på höjden. Man kan höja samtidigt som man åker framåt. Det är bara 2 gångar, en på vänster sida och en på höger om trucken, så man åker bara fram och bakåt, och höjer sig själv.

Skickades från m.sweclockers.com

Permalänk
Avstängd

Det enklaste vore väl att betrakta båda sidorna av gången som samma, så att listan är sorterad efter gång, djup i gången och höjd i gången. Alltså att H1 och H2 blir G11 respektive G12 eller liknande.

Vill du ha något mer avancerat så jobbar jag på ett företag som bygger bland annat den typen av lösningar med auto-truckar, men det kostar förstås en del. Men då kan man optimera så att höjning sker samtidigt som framkörning exempelvis.

Permalänk
Medlem
Skrivet av RobinJacobsson:

Det är ca 7 m högt med 9 platser på höjden. Man kan höja samtidigt som man åker framåt. Det är bara 2 gångar, en på vänster sida och en på höger om trucken, så man åker bara fram och bakåt, och höjer sig själv.

Skickades från m.sweclockers.com

Varför tar du upp att det finns flera rader om trucken eller vad vi nu ska kalla det bara kan vistas på en rad?`
För det är så jag tolkar det du skriver nu och då är det ju bara två axlar att ta hänsyn till.
Anledningen att jag skrev gafflar i mitt förra inlägg var helt enkelt för att jag tolkade lager + truck som gaffeltruck.

Visa signatur

Someone said that money can't buy everything... That person didn't know where to shop

Permalänk
Medlem
Skrivet av RobinJacobsson:

Trucken åker fram- och tillbaka och man har en hylla precis på sin vänstersida och en hylla precis till höger. Så när man plockar tex 01014 så vore det även optimalt att plocka 02014.

Det låter som någon har gjort bort sig när de konfigurerade affärssystemet/lagersystemet. Om det är ett större lager borde det vara ganska lätt att räkna hem kostnaden för att ta in en konsult som fixar till det, så att plocklistorna sorteras bättre. Om man blir tvungen att göra om numreringen kan det ju bli lite besvärligt, men även det borde en medelmåttig konsult kunna ordna i ett vettigt system.

Permalänk
Medlem

Det finns ingen generell lösning. Jag skulle skriva ett program som provade olika lösningar. Man kan "straffa" lösningar som är dyra. Till slut blir kombinationer reducerade. Själv har jag använt Bellmans optimalitetsprincip för att hitta bästa, snabbaste vägen i ett nät med många noder.

Skickades från m.sweclockers.com

Permalänk
Skrivet av KAD:

Det låter som någon har gjort bort sig när de konfigurerade affärssystemet/lagersystemet. Om det är ett större lager borde det vara ganska lätt att räkna hem kostnaden för att ta in en konsult som fixar till det, så att plocklistorna sorteras bättre. Om man blir tvungen att göra om numreringen kan det ju bli lite besvärligt, men även det borde en medelmåttig konsult kunna ordna i ett vettigt system.

Problemet är att systemet inte ligger lokalt och det finns inte kunskap för att tillämpa detta.

Jag uppmärksammade att våra teamleaders spenderar onödigt mycket tid på att göra scheman, så jag utvecklade en mjukvara som placerar anställda mot olika avdelningar med olika kriterier, man får inte hamna på samma avdelning som förra genereringen tex. Och alla avdelningar rymmer olika antal medarbetare. Detta gjorde jag genom att tilldela första anställda med lägst kompabilitet en avdelning, och fortsätta "uppåt" i kompabilitetsordning, för att till slut stå med den som har tillgång till flest avdelningar för en större chans att genereringen ska gå ihop. Misslyckas detta så kör jag en ny generering, tills alla blivit tilldelade en plats.

Jag anser mig själv ha tillräckligt med kunskap för att kunna identifiera problemen på lagret och leta vettiga lösningar, men där stannar det nog i detta fallet. Problemet är enligt mig att det inte ens finns kunskap så att man vet vad som går att genomföra och vad som inte går att genomföra, därför har det aldrig utvecklats. Idag genererar man en lista som sorteras från ena hållet till det andra på endast en axel.

Permalänk

Såhär ser det ut, båda sidorna plockas från insidan och den "röda mattan" är spåren där trucken går fram och tillbaka.
Dom lila och röda markeringarna kan representera en plocksekvens som en lista genererat.

Permalänk

Jag har funderat, och det är som max 16-20 olika artiklar i en plocksekvens. Borde inte en brute force algoritm fungera för att generera närmsta väg? Jag har räknat ut hastighet i x- och y-led och om man gör en array som en 2d karta och sätter "1" på dom platser som plocklistan omfattar? Sedan borde jag väl kunna räkna ut avstånd med Pythagoras sats med mina x- och y- värden? Och tilldela varje hel sekvens den sammanlagda sträckan och sen välja den sekvens som ger lägst värde?

Skickades från m.sweclockers.com

Permalänk
Hedersmedlem

Beror ju helt på dina krav. Vad är värsta fallet och hur lång tid är det okej för beräkningen att ta? 20 artiklar i den jobbigaste konfigurationen som går.

Att implementera en lite mer anpassad algoritm kan nog vara ett kul projekt annars. Kan du göra din brute-force snabbt kanske det kan vara en start och något att jämföra med.

Permalänk

Ja, jag har aldrig gjort någon mer anpassad algoritm som tex genetisk eller Bellman. Vore kul om det fanns lite läromaterial på svenska att tillgå, eller om man vill dela med sig och förklara kod här.

20^3 är ju 8000, det borde väl inte anses vara tungt nog att loopa igenom och kalkylera avstånden?

Skickades från m.sweclockers.com

Permalänk
Hedersmedlem

Varför 20^3?

Permalänk
Medlem

Du har 20! (fakutetet av 20) att räkna på och det blir för 20 objekt

2 432 902 008 176 640 000 mätningar om du kör brute force...

för 50 objekt så det bli 3,04140932....*10^64 mätningar och i praktiken omöjligt att köra brute force på inom rimlig tid. Man måste fuska på olika smarta sätt och 2004 lyckades man att räkna ut kortaste avståndet för att besöka Sveriges samtliga 24978 orter (som blev ca 72500 km) och konststycket i det hela är att bevisa att det _är_ den kortaste sträckan...

Brute force kan man göra på upp till 10-12 objekt men redan vid 14 objekt börja det bli riktigt tungt att prova alla alternativen (~87 miljarder alternativ)

kort sagt det är en NP-komplett problem där antalet beräkningar (och dess tidsåtgång) ökar exponentiellt med antal objekt

Det finns ett antal olika algoritmer som inte ger perfekt resultat men 'tillräckligt bra' för att få det hanterbart inom rimlig beräkningstid och är en forskningsämne i sig i att ytterligare förbättra då detta har industriell betydelse och inte bara en intellektuell utmaning

Söker man på TSP, handelsresande problemet, Travelling salesman problem så hittar man en hel del skrivet om det och också olika strategier.

Permalänk
Skrivet av Shimonu:

Varför 20^3?

Det kanske blir färre än så, jag räknade på 20 st artiklar att plocka. Men när jag testade med 3 artiklar att plocka så verkar jag få det till såhär:

Detta tex symboliserar min hylla sett från sidan, där x = artiklar som ska plockas och 0 = hyllplats som förblir orörd.
0 x 0
x 0 0
0 0 x

Olika kombinationer till plocksekvenser (x,y):
2,0
0,1
1,2

2,0
1,2
0,1

0,1
2,0
1,2

0,1
1,2
2,0

1,2
0,1
2,0

1,2
2,0
0,1

=3 * 2 = 6 kombinationer

Och med 4 artiklar:

Hylla:
0 x 0 x
x 0 0 0
0 0 x 0

Kombinationer (x,y)

2,0
0,1
1,2
3,2

2,0
0,1
3,2
1,2

2,0
1,2
3,2
0,1

2,0
1,2
0,1
3,2

2,0
3,2
1,2
0,1

2,0
3,2
0,1
1,2

... = 4 * 6 = 24 kombinationer på 4 artiklar

Så på 3 artiklar får jag 6 st möjliga rutter, och på 4 artiklar får jag 24 möjliga rutter. I verkligheten börjar man ju från 0,0 men det borde inte spela någon roll i detta sammanhanget. Så jag räknade nog lite fel i all hast förut på jobbet, men jag ser nog inte riktigt vad 20 artiklar skulle generera för antal kombinationer.

Permalänk
Skrivet av xxargs:

Du har 20! (fakutetet av 20) att räkna på och det blir för 20 objekt

2 432 902 008 176 640 000 mätningar om du kör brute force...

(...)

Söker man på TSP, handelsresande problemet, Travelling salesman problem så hittar man en hel del skrivet om det och också olika strategier.

Okej, ja jag drog rätt slutsats men såg inte mönstret att det hamnade inom fakultet 20!

Jag har kikat lite på Traveling Salesman men jag kan för att vara helt ärlig inte helt förstå hur jag ska implementera detta i en kod.
Finns det mer info om TSP på svenska?

Permalänk
Medlem

Saken är att väldigt mycket _är_ skrivet på engelska...

Engelska är ett språk man måste försöka lära sig när man läser tekniklitteratur - min väg var också knagglig i början men efterhand så går det lättare - google translate kan hjälpa mycket men samtidigt ha i bakhuvudet att det kan bli väldigt fel... så ibland får man ha hjärnan inkopplad och förstå om det är rimligt eller inte och dubbelkolla...

Svenska delen om detta är tex. https://sv.wikipedia.org/wiki/Handelsresandeproblemet som jag gissar att du redan funnit och läst, i sökmotorn (och följer man olika länkar och referenser i framförallt engelska wiki brukar det inte dröja så länge innan kod eller pseudokod, referenser till olika libbar och mattepaket dyker upp för att beskriva olika processer) så kommer man finna en del kurslitteratur från våra svenska högskolor i ämnet och en del är användbart, andra mindre - man får helt enkel räkna med att spendera lite tid åt att söka, sovra för hitta guldbitarna i olika pdf som kanske gör att man kommer vidare (när du blivit van vid detta och förstått upplägget så förstår du snart varför man hatar youtube - i pdf kan man snabbt 'spola' fram till intressanta stycken, i youtube måste man sitta och titta på skiten och bränna en massa tid innan de klämmer fram de eventuella 7 bild-frames (som dessutom är suddiga) och två orden som faktisk är intressanta för det du söker efter) Det är en konst att kunna söka effektivt och inte spendera tid på fel saker när man letar information...

- Internet och google är en gulgruva i att hitta information, med tanke på att jag växte upp i en tid när man var som mest informationshungrig så fanns inget av det och det bästa man kunde hitta var på biblioteken, gärna då universitetsbibliotek - några år gammalt och ännu äldre...

Sök-skillet blir också allt bättre efterhand man fördjupa sig i ämnet eftersom många av artiklarna också har referenser (och Wikipedia, framförallt den engelska har ofta rätt bra ingångar vidare till annan litteratur och därifrån referenser vidare vilket gör att det kan ryka hela helgen att läsa sådant innan man kommer tillbaka igen sas.)

Slutligen inget av detta fixas på en kafferast - skall man bli bättre på något så måste man spendera tid på detta och det kan ingen annan göra åt dig...

Permalänk

Okej, så det finns inga färdiga koder som går igenom en 2d-array/karta och hittar en bra väg i tex PHP? Är koden/tillämpningarna så unika för varje scenario att det inte finns en given färdig lösning för just mitt problem?

Skickades från m.sweclockers.com

Permalänk
Quizmästare Gävle 2022

@RobinJacobsson:

Har ni köpt/ leasar truckparken av någon av de större trucktillverkarna så skulle jag kolla med dem. De har bra verktyg för simuleringar av optimal plock och placering av artiklar.

Såt brukar man inte sällan snacka sig till vid affären

Visa signatur
Permalänk
Avstängd
Skrivet av RobinJacobsson:

Okej, så det finns inga färdiga koder som går igenom en 2d-array/karta och hittar en bra väg i tex PHP? Är koden/tillämpningarna så unika för varje scenario att det inte finns en given färdig lösning för just mitt problem?

Skickades från m.sweclockers.com

Kolla på Dijkstras algoritm.

Men jag tror ni gör det alldeles för komplicerat med traveling salesman och så, om jag förstår problemet rätt så är det inte så svårt att lösa. Hyllor är ganska strukturerade så det borde gå med enkel logik.

Säg att positionsinformationen består av hylla följt av en koordinat för rutsystemet som hyllan utgör, typ: (hylla) a: (djup) x: (höjd) y. Exempelvis 1:12:8. En gång har då två hyllor förstås, en på varje sida. Sen är ju frågan om man ska optimera på höjd eller djup i gången. För att förenkla kan man ju tänka sig att gångarna är enkelriktade vilket är ganska vanligt om det är ont om plats och många samtidiga operationer, vilket innebär optimering på djup: x. Så: För alla a (och b, hyllan på andra sidan gången) så ska du ta alla y för en given x innan du går vidare till nästa x. Så gruppera på a och b, gång alltså, först. Sen gruppera och ordna efter x och därefter y. Vill du optimera mer så borde varannan x sortera efter y i omvänd ordning så att du åker upp på en x och sen ner på nästa så slipper du åka ner mellan varje x. Eller har jag missförstått problemet?

Permalänk
Medlem
Skrivet av snajk:

Kolla på Dijkstras algoritm.

Men jag tror ni gör det alldeles för komplicerat med traveling salesman och så, om jag förstår problemet rätt så är det inte så svårt att lösa. Hyllor är ganska strukturerade så det borde gå med enkel logik.

Säg att positionsinformationen består av hylla följt av en koordinat för rutsystemet som hyllan utgör, typ: (hylla) a: (djup) x: (höjd) y. Exempelvis 1:12:8. En gång har då två hyllor förstås, en på varje sida. Sen är ju frågan om man ska optimera på höjd eller djup i gången. För att förenkla kan man ju tänka sig att gångarna är enkelriktade vilket är ganska vanligt om det är ont om plats och många samtidiga operationer, vilket innebär optimering på djup: x. Så: För alla a (och b, hyllan på andra sidan gången) så ska du ta alla y för en given x innan du går vidare till nästa x. Så gruppera på a och b, gång alltså, först. Sen gruppera och ordna efter x och därefter y. Vill du optimera mer så borde varannan x sortera efter y i omvänd ordning så att du åker upp på en x och sen ner på nästa så slipper du åka ner mellan varje x. Eller har jag missförstått problemet?

Jag tolkar problemet som att man vill spara tid genom att köra så kort sträcka som möjligt, för jag antar att lyftanordningen inte är jättesnabb.
Men utan några siffror så blir det ju inte helt lätt att gissa vad som är värt att göra eller inte.

Visa signatur

Someone said that money can't buy everything... That person didn't know where to shop

Permalänk
Skrivet av Enity:

Jag tolkar problemet som att man vill spara tid genom att köra så kort sträcka som möjligt, för jag antar att lyftanordningen inte är jättesnabb.
Men utan några siffror så blir det ju inte helt lätt att gissa vad som är värt att göra eller inte.

Att röra sig X går ca dubbelt så snabbt som att röra sig Y.
Men materialet står ju där det står, rent fysiskt. Och det är inte enkelriktat, man kör en plocktruck fram och tillbaka, upp och ner tills man plockat alla artiklar på listan. Jag vill optimera så att rör sig mellan alla artiklar under en så liten sträcka som möjligt.

En plocklista kan se ut som följande (hylla, x, y)

1,2,1
1,3,1
1,3,6
2,3,6
2,4,5
1,5,2
1,6,2
2,6,2
2,9,1

Så om man betraktar detta ur en 2d x, y vinkel så vill man hitta en "cirkulär", närmsta väg utan att nödvändigtvis besöka samma plats två gånger.

Och man utgår från- och slutar på (z,0,0)
Skickades från m.sweclockers.com

Permalänk
Hedersmedlem

Kika på A*(A-star), vill minnas den inte är jättekomplex.

Permalänk

Om jag inte missminner mig så hittar A* en väg mellan två punkter. Inte en väg som passerar ett antal punkter och minimerar sträckan.

Om man når både hyllan till höger (1) och hyllan till vänster (2) om man stannar vid x,y har du just reducerat problemet till två dimensioner. Har vi inte en lösning på det? Hmm, travelling salesman, kanske? Den enda skillnaden är att din karta står upp.