Permalänk
Hedersmedlem
Skrivet av Ingetledigtnamn:

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.

A* kan ändå användas för att räkna ut kortaste vägen mellan alla punkter. Dijkstra's är i princip ett specialfall av A*.

Att bygga upp ett minimum spanning tree kan nog vara en bra väg och sen traversera det.

Phew, var länge sen man tittade på sånt här.

Permalänk
Skrivet av Ingetledigtnamn:

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.

Precis, man kan plocka från båda sidor vid ett stopp så problemet är att betrakta som 2 dimensionellt.

Skickades från m.sweclockers.com

Permalänk
Medlem

det handlar om att tänka lite i topologi

När man är mellan hyllraderna - betrakta problemet som om hyllorna vält åt sidan med översta hylla längst bort från mittgången från resp sida och problemet är då 2-dimmesionellt eftersom att åka fram och tillbaka i mittgången är en kostnad och att sträcka sig efter närmast hylla (golvhyllan) tar mindre tid än att sträcka sig flera rader längre ut (högsta hyllan).

till detta har man parametrar om att röra sig i gången och sträcka ut/in (höja sänka) går att göra samtidigt - lika så att förflytta sig när man sträckt ut sig max (köra mellangången med pallgaffeln högst upp) och hur fort respektive del kan röra sig ( dvs ger olika resultat om att köra i gången, stanna vid position - därefter höja gaffeln plocka ut/in, sänka gaffeln igen och sedan röra sig igen till ny position endast när gaffeln är nere igen eller om man kan köra flera moment samtidigt (dvs. diagonala förflyttningar))

Permalänk
Skrivet av xxargs:

... eller om man kan köra flera moment samtidigt (dvs. diagonala förflyttningar))

Man står i trucken så den har inga gafflar.
Man kan köra fram/bak- och höja/sänka sig själv samtidigt, hastigheten att höja sig v(y) är ca 1/2 mot vad det är att röra sig fram/bak v(x).

Egentligen kan man ju strunta i att det är 2 hyllor och bara behandla strängen ex 010101 och 020101 som "samma" stopp (zzxxyy).

Mitt problem är att hitta rätt algoritm och implementera koden. Jag har grundläggande kunskaper i PHP, nosat lite på oop men inte tillräckligt för att kunna det.

Skickades från m.sweclockers.com

Permalänk
Medlem

@RobinJacobsson: Kanske ska du titta på att optimera var ni lagrar sakerna så du minimerar på det sättet istället för att leta kortaste/snabbaste väg? Fast de kanske är för jobbigt att organisera om lagret? Annars så tror jag du/ni kommer tjäna mer på det att i de flesta fallen så finns det som ska plockas ihop närma varandra än att försöka få ihop en kort väg att förflytta sig.

Permalänk
Medlem

@RobinJacobsson:
Du kan få fram den optimala rutten hyffsat effektivt så länge max antal artiklar verkligen är 16-20. Det finns en dynamisk programmering algoritm som heter Held-Karp som löser tsp på O(n^2 * 2^n) tid. För 20 artiklar vilket blir 21 hörn i grafen (artiklar + start/slut hörn(0,0)) så får jag en körtid på ~5 sekunder men redan vid 23 artiklar / 24 hörn tar det ~1 minut.

Du har helt rätt att vilken sida av gången man plockar ifrån inte spelar någon roll för hur själva rutten genereras utan bara är intressant sen när själva plocklistan skrivs ut.

För att generera indata till Held-Karp algoritmen tar du din lista med plockplatser och tar bort hyllkoordinaten så du får en lista med (x,y) koordinater. tex (4,7) (5,1) (16,0) (18,1) lägg till punkten (0,0) först i listan eftersom den också ingår i rutten. Utifrån den listan skapar du en närhetsmatris (adjacency matrix). Loopa över sampliga punkter två gånger och fyll matrisen (2d array) med kostnaden mellan punkterna.

p0 p1 p2 p3 p4 p0 0 14 5 16 18 p1 14 0 12 14 14 p2 5 12 0 11 13 p3 16 14 11 0 2 p4 18 14 13 2 0

Som kostnadsfunktion använde jag

((x1 - x2).abs * costX) max ((y1 - y2).abs * costY)

(costX=1,costY=2). Den riktning som tar längst tid bestämmer alltså tiden det tar att förflytta sig mellan två punkter.

Sortering av punkterna ger rutten: (0,0)->(4,7)->(5,1)->(16,0)->(18,1)->(0,0) kostnad: 57
Held-Karp ger rutten: (0,0)->(4,7)->(18,1)->(16,0)->(5,1)->(0,0) kostnad: 46

Jag testade att slumpa 100 plocklistor med 16-20 artiklar, 9 våningar, 50 rader och dubbelt så lång tid att förflytta sig mellan våningar jämfört med rader. Optimal rutt tar då i snitt ~70% av tiden den sorterade rutten tar.

Börja med att söka på Held-Karp + ett programmeringsspråk du är bekväm med. Kör den på riktiga plocklistor från din arbetsplats och jämför för att se hur mycket tid ni skulle tjäna. Riktiga data kanske ser väldigt annorlunda ut jämfört med en slumpad simulering. Eftersom det är en människa som styr trucken kan det också vara intressant om en mer ologisk plocklista leder till mer misstag och man tappar lite tid på det sättet?

Behöver du längre listor än 22-23 artiklar så kan du inte använda Held-Karp.

A*, dijkstra osv kommer inte lösa ditt problem. Tsp är ett np-fullständigt (nondeterministic polynomial) problem. Det finns alltså ingen känd lösning för tsp som kan köras på polynomiell tid (O(n^k)). A* osv har algoritmer med polynomiell körtid.

Permalänk

Wow, bra info. Din tanke med ologisk plocklista i relation till fler misstag kan utforskas, och det är ju uppenbart att en ologisk plocklista genererar längre plocktid. I värsta fall behöver jag inte ha den perfekta rutten, en tidsförbättring på 70% är ju initialt en klar förbättring, även om inte hela momentet från start till slut innebär endast plockning. Beställning av tomma lådor, skriva ut plocklistor osv ingår ju också så det blir ju inte 70% effektiv förbättring, men ändå en klar förbättring i mina ögon.

En annan sak, precis när man når vån 4 så stannar trucken till för att inta ett typ av läge så man kan hissa sig ännu högre, den tiden mätte jag till motsvarande att höja sig 2 våningar. Så jag antar att man kan lägga till en tom rad på vån 5 för att simulera den extra sträckan (tiden) det tar att anpassa trucken för förlängd höjning.

Skickades från m.sweclockers.com

Permalänk
Medlem

Som tidigare nämnts i tråden så tror jag det finns betydligt effektivare lösningar för att snabba upp plock än att "hitta kortaste väg i ett tvådimensionellt koordinatsystem". Normalt brukar man skapa plockplatser på de nedersta hyllplatserna (för de mest frekventa produkterna) och sedan ha "buffertplatser" för påfyllning av plockplatserna, samt mindre frekventa artiklar högre upp i ställagen. Annars är ju den nya heta trenden att jobba med automatiska lagerhissar, där de olika hyllplatserna istället körs ner till plockarna, som då alltid jobbar på samma höjd. Men det är ju lite av en större investering.

Permalänk

Ja, företaget omsätter ju miljarder så jag får väl lov att anse att det är av den större modellen. Det finns även automatiska hissar av olika typer, men med just den här plockmetoden har man valt att använda mänsklig plockning och man försöker anpassa fysiska platserna så gott det går, men som jag skrev tidigare finns vissa begränsningar som att tex tungt material längst ner, vissa artiklar går på flera plocklistor osv så optimeringen där tycker jag att vi för tillfället kan förbise och bara fokusera på själva plockrundan utifrån dom koordinater som ges.

Och tilläggas bör, att det finns tekniker som jobbar med optimeringen av tex hur materialet skall placeras osv. Däremot verkar det vara lite brist på kompetens just vad man kan åstadkomma i mjukvaruform som tex algoritmer osv.

Skickades från m.sweclockers.com

Permalänk

Jag har hittat en held-karp algoritm i PHP som jag har fått igång. Men jag är lite osäker på hur jag ska tolka matrixen, jag antar att 0, 1, 2, 3, 4 motsvarar dom noder jag tänkt besöka, dvs antalet stopp som listan kräver. Vad jag inte riktigt förstår är hur jag ska tolka avstånden, kan någon se över detta och förklara tack?

Jag behöver alltså ta hänsyn till att det går dubbelt så snabbt att röra sig i X-led än i Y-led och när man kommer förbi 3:e våningen (Y-led) så stannar trucken till, vilket jag antar att man då kan sätta till en "tom" rad mellan 3 och 4 som tidsmässigt motsvarar den tid det tar att stanna upp?

<?php function every_combinations($set, $n = NULL, $order_matters = true) { if($n == NULL) $n = count($set); $combinations = []; foreach($set AS $k => $e) { $subset = $set; unset($subset[$k]); if($n == 1) $combinations[] = [$e]; else { $subcomb = every_combinations($subset, $n - 1, $order_matters); foreach($subcomb AS $s) { $comb = array_merge([$e], $s); if($order_matters) $combinations[] = $comb; else { $needle = $comb; sort($needle); if(!in_array($needle, $combinations)) $combinations[] = $comb; } } } } return $combinations; } #map $matrix = array( 0 => array(0, 2, 9, 10, 5), // distance between node 0 and node 0 (0), distance between node 0 and node 1 (2), ... 1 => array(1, 0, 6, 4, 4), // distance between node 1 and node 0 (1), distance between node 1 and node 1 (0), ... 2 => array(15, 7, 0, 8, 1), 3 => array(6, 3, 12, 0, 8), 4 => array(6, 3, 12, 0, 8), ); function held_karp($matrix) { $nb_nodes = count($matrix); # Maps each subset of the nodes to the cost to reach that subset, as well # as what node it passed before reaching this subset. # Node subsets are represented as set bits. $c = []; # Set transition cost from initial state for($k = 1; $k < $nb_nodes; $k++) $c["(".(1 << $k).",$k)"] = [$matrix[0][$k], 0]; # Iterate subsets of increasing length and store intermediate results # in classic dynamic programming manner for($subset_size = 2; $subset_size < $nb_nodes; $subset_size++) { $combinaisons = every_combinations(range(1, $nb_nodes - 1), $subset_size, false); foreach($combinaisons AS $subset) { # Set bits for all nodes in this subset $bits = 0; foreach($subset AS $bit) $bits |= 1 << $bit; # Find the lowest cost to get to this subset foreach($subset AS $bk) { $prev = $bits & ~(1 << $bk); $res = []; foreach($subset AS $m) { if(($m == 0)||($m == $bk)) continue; $res[] = [$c["($prev,$m)"][0] + $matrix[$m][$bk], $m]; } $c["($bits,$bk)"] = min($res); } } } # We're interested in all bits but the least significant (the start state) $bits = (2**$nb_nodes - 1) - 1; # Calculate optimal cost $res = []; for($k = 1; $k < $nb_nodes; $k++) $res[] = [$c["($bits,$k)"][0] + $matrix[$k][0], $k]; list($opt, $parent) = min($res); # Backtrack to find full path $path = []; for($i = 0; $i < $nb_nodes - 1; $i++) { $path[] = $parent; $new_bits = $bits & ~(1 << $parent); list($scrap, $parent) = $c["($bits,$parent)"]; $bits = $new_bits; } # Add implicit start state $path[] = 0; return [$opt, array_reverse($path)]; } #run held carp held_karp($matrix); #create variables of return value $data = held_karp($matrix); $distance = $data[0]; $path = $data[1] ; #output result $path_string = implode(' -> ', $path) . ' -> ' . $path[0] ; echo "Path = " . $path_string . " with a distance of " . $distance ; // Path = 0 -> 2 -> 3 -> 1 -> 0 with a distance of 21 ?>

Permalänk

Nu har jag kommit en bit på vägen efter med att "översätta" mina koordinater till en array med avstånd. Men jag vet fortfarande inte riktigt hur jag ska skapa själva avstånden, tar gärna hjälp av någon som har lite bättre insikt. Mitt föregående inlägg är alltså en helt annan kod, den här koden är endast för att skapa $matrix med avstånden mellan noderna i ovanstående inlägg.

$map är tänkt att representera en visuell tabell där användaren kan mata in koordinater, kanske från en databas i framtiden eller i den här koden som jag visar nedanför:

<?php $map = array( 8 => array(1, 0, 0, 0, 0, 0, 0, 0, 1, 1), 7 => array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 6 => array(0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 5 => array(1, 0, 0, 0, 0, 0, 0, 0, 0, 0), 4 => array(0, 0, 0, 0, 1, 0, 0, 0, 0, 0), 3 => array(0, 0, 0, 0, 1, 0, 0, 0, 0, 1), 2 => array(0, 1, 0, 0, 0, 0, 0, 0, 0, 0), 1 => array(0, 0, 0, 1, 0, 0, 0, 0, 1, 0), 0 => array(1, 0, 0, 0, 0, 0, 0, 0, 0, 0) ); $array = []; //Loop all $map[y] index for($y = 0; $y < count($map); $y++) { echo "<h1>Y: ".$y."</h1><br>"; //Loop all $map[][x] index for($x = 0; $x < count($map[$y]); $x++) { echo "X: ".$x."<br>"; //If current index is = 1, create array with first node at index 0 if($map[$y][$x] == 1) { echo "Node found on X =". $x." and Y = ".$y."<br>"; //Create distances between nodes here //Get distance from Pythagoras $pyth_pow = pow($x, 2) + pow($y, 2); $pyth_sum = sqrt($pyth_pow); } } echo "<br>"; } ?>

Permalänk
Medlem

@RobinJacobsson:
Utifrån hur jag tolkar din beskrivning av hur trucken kan röra sig är avstånd fel värde att lagra i matrisen. Avstånd fungerar bara om truckens hastighet är konstant i alla riktningar. Om vi ger trucken en hastighet av 1m/s horisontellt så kan den röra sig 0.5m/s vertikalt och sqrt(1^2 * 0.5^2) = ~1.12m/s diagonalt.

Det du vill lagra är en kostnad för hur lång tid det tar mellan de olika positionerna. Den riktning som tar längst tid styr helt kostnaden. Jag antar att om man tex ska upp en våning och framåt fem hyllor så höjer man trucken en våning under tiden man förflyttar sig de två första hyllorna framåt, efter det förflyttar man sig bara i x-led tre hyllor till.

Om den extra kostnad som tillkommer nånstans runt 3-4 våningen är mellan två våningsplan så är det enkelt löst genom att med en if-sats kontrollera om man passerar den positionen i kostnadsfunktionen:

if (min($row1, $row2) <= 3 && max($row1, $row2) >= 4) ...

Jag har aldrig rört php men gissade syntax/funktioner utifrån det du postat och nåt liknande det här borde kunna skapa en lista men positioner och en kostnadsmatris:

function genPoints($input) { $width = count($input[0]); $height = count($input); $points = []; for($row=0; $row < $height; $row++) { for($col=0; $col < $width; $col++) { if($input[$row][$col] == 1) { $points[] = [$row, $col]; } } } return $points; } function cost($from, $to) { list($row1, $col1) = $from; list($row2, $col2) = $to; return max(abs($row1 - $row2) * 2, abs($col1 - $col2)); } function genGraph($points) { $sz = count($points); $matrix = []; for($from=0; $from < $sz; $from++) { for($to=0; $to < $sz; $to++) { $matrix[$from][$to] = cost($points[$from], $points[$to]); } } return $matrix; } $points = genPoints($map); $graph = genGraph($points);

Tyvärr är antagligen php för långsamt för att köra Held-Karp på en graf med uppåt 21 noder men du kan alltid testa och se hur lång tid det tar. Om du inte kan välja något annat språk så är det nog ide att titta på andra algoritmer som inte löser tsp optimalt men ändå oftast kan ge en förbättring. Enklast möjliga är nearest-neighbour. Den går ut på att man hela tiden flyttar sig till närmsta position med lägst kostnad och sen tillbaka till utgångsläget. Med nearest-neighbour hamnar jag i snitt på ~80% av tiden det tar för den sorterade rutten men ibland kan nearest-neighbour ge en något längre rutt.

Permalänk
Avstängd

Lite nyfiken

Hur många hyllrader är det att plocka från?
Hur många olika produkter finns det?
Vikten på produkterna, går det alltid att bära och plocka för hand?

Man kan hel- eller halvautomatisera detta eller köra manuell plockning som ni gör idag. Allt är bara beroende av vad det får kosta och hur mycket det är värt i arbetsmiljö och liknande.

Visa signatur

Chassi: Fractal Design Define R3 Black, Mobo: ASUS Z170 Pro Gaming, CPU: Intel i7 6700K, kylning CM Hyper 212 EVO, RAM: 32 GB Hyper X 3000 mhz, GPU: Nvidia MSI 1080 Gaming X, PSU: XFX Core Edition Pro 750W, Mus: Logitech G700, Tgb: Corsair Raptor K30, OS: Win10

Permalänk
Skrivet av Stefflo:

Lite nyfiken

Hur många hyllrader är det att plocka från?
Hur många olika produkter finns det?
Vikten på produkterna, går det alltid att bära och plocka för hand?

Man kan hel- eller halvautomatisera detta eller köra manuell plockning som ni gör idag. Allt är bara beroende av vad det får kosta och hur mycket det är värt i arbetsmiljö och liknande.

Det är en av världens största fordonstillverkare, så allt går inte att bära för hand, men i detta plockmomentet är allt anpassat för att plockas för hand dock. Det är tusentals artiklar, men i just detta momentet handlar det om 10 rader x 9 våningar på varje sida om trucken.

Skickades från m.sweclockers.com

Permalänk
Skrivet av jclr:

@RobinJacobsson:
Utifrån hur jag tolkar din beskrivning...

Tusen tack, kanoninfo! Ska kolla detta senare.
Men om jag inte printar ut något så borde det väl behandlas som vilken kod som helst, eller har jag fel? Märkte att ett annat script blev segt när jag körde det via jobbet, men behandlades supersnabbt på min dator. Trodde det berodde på att jag printade ut resultat löpande i loopen och att det påverkade prestandan.

Skickades från m.sweclockers.com

Permalänk
Avstängd
Skrivet av RobinJacobsson:

Det är en av världens största fordonstillverkare, så allt går inte att bära för hand, men i detta plockmomentet är allt anpassat för att plockas för hand dock. Det är tusentals artiklar, men i just detta momentet handlar det om 10 rader x 9 våningar på varje sida om trucken.

Skickades från m.sweclockers.com

Ok, för den typen av kunder skulle jag säga att man inte ens ska hålla på med handplock utan direkt gå på ett fullautomatiserat system. Jag har en del känningar som absolut kan titta på detta mer professionellt om det kan vara av intresse.
Nu är denna video från ett mycket större lager men något åt det hållet skulle jag satsa på och då istället få en packstation dit produkterna kommer till dig. Videon är bara något som visar min tanke utan att ens veta vem det ens är som gjort lagret i videon.
https://www.youtube.com/watch?v=MWccj05Hb1E

Visa signatur

Chassi: Fractal Design Define R3 Black, Mobo: ASUS Z170 Pro Gaming, CPU: Intel i7 6700K, kylning CM Hyper 212 EVO, RAM: 32 GB Hyper X 3000 mhz, GPU: Nvidia MSI 1080 Gaming X, PSU: XFX Core Edition Pro 750W, Mus: Logitech G700, Tgb: Corsair Raptor K30, OS: Win10

Permalänk

@Stefflo: Jag arbetar där, det är ingen kund. Jag är relativt långt ner på näringskedjan, så jag kan inte påverka finansiella beslut eller anpassa verksamheten på det sättet. Däremot har jag en position att jag kan identifiera behoven och i begränsade fall även lösa vissa problem. Detta är ett av dom. Den stora optimeringen görs ju genom att placera materialet rätt fysiskt. Och även utveckla plockmomentet och standardisera saker. Men jag såg en möjlighet att optimera det ännu lite mer, det är därför jag skriver här om tips för att åstadkomma detta.

Permalänk
Avstängd
Skrivet av RobinJacobsson:

@Stefflo: Jag arbetar där, det är ingen kund. Jag är relativt långt ner på näringskedjan, så jag kan inte påverka finansiella beslut eller anpassa verksamheten på det sättet. Däremot har jag en position att jag kan identifiera behoven och i begränsade fall även lösa vissa problem. Detta är ett av dom. Den stora optimeringen görs ju genom att placera materialet rätt fysiskt. Och även utveckla plockmomentet och standardisera saker. Men jag såg en möjlighet att optimera det ännu lite mer, det är därför jag skriver här om tips för att åstadkomma detta.

Jo, jag förstod att du hade det som arbetsplats och på ett sånt stort företag så borde det finnas det som många företag nu kallar för 5S, att man jobbar med ständiga förbättringar, städning, systematisering och liknande och där brukar även finnas ett forum där även folk på högre nivåer ska lyssna på sina medarbetare. Om det nu inte gör det så är det helt rätt av dig att försöka ta tag i detta på egen hand och göra ditt jobb så lätt som möjligt med små medel.
Tyvärr har jag som jag inte skrev de kunskaperna som krävs för att plocka fram det du vill så hoppas att de andra här på swec. kan hjälpa till.

Visa signatur

Chassi: Fractal Design Define R3 Black, Mobo: ASUS Z170 Pro Gaming, CPU: Intel i7 6700K, kylning CM Hyper 212 EVO, RAM: 32 GB Hyper X 3000 mhz, GPU: Nvidia MSI 1080 Gaming X, PSU: XFX Core Edition Pro 750W, Mus: Logitech G700, Tgb: Corsair Raptor K30, OS: Win10

Permalänk

@Stefflo: Kul att du nämner det då jag precis fått ny tjänst inom det området, jag kommer att ansvara för- och coacha i just 5S/lean/det interna produktionssystemet. Det kanske var lite därför jag blev attraktiv för den tjänsten, för att jag uppmärksammar och arbetar på dom problemen på eget initiativ.

  1. Jag har fått igång koden, men det verkar som att när jag anger 2 noder så räknar den bara 1 avstånd, jag misstänker att det kan ha att göra med att den räknar någon array från 0 medan den tolkas som 1 någon annanstans?

    $input = array( 0 => array(0, 0, 0, 0, 0), 1 => array(0, 0, 0, 0, 0), 2 => array(0, 0, 0, 0, 0), 3 => array(1, 0, 0, 0, 0), //en plockplats på rad 3 4 => array(1, 0, 0, 0, 0), //en plockplats på rad 4 );

    genererar: Path = 0 -> 1 -> 0 with a distance of 4

    Och när jag bara anger EN nod så får jag felmeddelande:
    min(): Array must contain at least one element in C:\wamp64\www\hk.php on line 120

    Line 120:

    list($opt, $parent) = min($res);

  2. Jag upptäckte också att jag bara fick heltal i avstånd av din kod, vilket verkar lite konstigt när man borde åka raka vägen mellan punkterna, så jag skrev om din funktion, vänligen kolla så att jag har gjort rätt!

    function cost($from, $to) { list($row1, $col1) = $from; list($row2, $col2) = $to; //Min kod (Pythagoras) return sqrt(pow(abs($row2 - $row1) * 2, 2) + pow(abs($col2 - $col1), 2)); //Din kod return max(abs($row1 - $row2) * 2, abs($col1 - $col2)); }

    Dock så verkar det inte som att den räknar med sträckan från 0 till första noden och från sista noden till 0, jag får bara avståndet mellan de 2 noderna jag angett efter lite tester jag gjort.

  3. En annan tanke, varifrån räknar den 0 nu? För om den räknar ifrån array[0][0] så blir ju hela den "visuella" matrisen spegelvänd i det läget som den presenteras i koden nu.

  4. Och jag kommer att behöva göra om plocklistan tex
    01024
    01034
    01056
    01083
    02083
    02014

    till

    $array[2][4]
    $array[3][4]
    $array[5][6]
    $array[8][3]
    $array[8][3]
    $array[1][4]

Permalänk
Avstängd
Skrivet av RobinJacobsson:

@Stefflo: Kul att du nämner det då jag precis fått ny tjänst inom det området, jag kommer att ansvara för- och coacha i just 5S/lean/det interna produktionssystemet. Det kanske var lite därför jag blev attraktiv för den tjänsten, för att jag uppmärksammar och arbetar på dom problemen på eget initiativ.

Man får väl säga grattis då och lycka till, tror säkert att du kommer lyckas. det gäller att vilja ta förs sig och vissa arbetsplatser ger tillbaka genom att låta folk byta tjänst inom företaget medans vissa bara ser på vilken utbildning personen i fråga har. Se bara till att vara nyfiken, frågvis och lyssna på dina kollegor. Många har bra idéer men tyvärr är det inte alls som törs berätta om det i grupp.
Lycka till och hoppas du får ordning på ert plocklager.

Visa signatur

Chassi: Fractal Design Define R3 Black, Mobo: ASUS Z170 Pro Gaming, CPU: Intel i7 6700K, kylning CM Hyper 212 EVO, RAM: 32 GB Hyper X 3000 mhz, GPU: Nvidia MSI 1080 Gaming X, PSU: XFX Core Edition Pro 750W, Mus: Logitech G700, Tgb: Corsair Raptor K30, OS: Win10

Permalänk

Nu har jag ingen aning om hur koden du hittade funkar, men jag skulle tro att din array skall innehålla avstånden mellan punkterna. I en 4x4-matris skulle rad 1 innehålla avståndet mellan punkt 1 och punkt 1, 2, 3, 4. Rad 2 avstånd från punkt 2 till punkt 1, 2, 3, 4. Osv.

Om du tänker på ett "normalt" TSM-problem finns inte direkta vägar mellan alla städer utan man får köra via en annan stad. Städer man inte kan nå får sannolikt ett specialvärde 0(?), kanske -1. Du har ett specialfall där man kan nå alla punkter från alla andra punkter. (Och ett jobbigare problem beräkningsmässigt.)

Att programmet vill ha heltal är inte så konstigt då avstånden i kilometer/miles sällan anges med decimaler. Om det inte passar med dina avstånd kan du ange avstånden i centimeter, eller sekunder Det är inte så himla noga med exakt mått bara proportionerna stämmer.

Permalänk
Skrivet av jclr:

Tusen tack för din kod. Och tack ni andra för övriga inputs. Jag har fortfarande ett par bekymmer som uppstod när jag implementerade din kod som jag postade här ovan, vore tacksam om du kan bidra med lösningar

Skickades från m.sweclockers.com

Permalänk
Medlem

Kan inte hjälpa dig konkret men ett område där detta är A & O är ju inom CNC-teknik.
Att jaga sekunder på verktygsbanor i tillverkning kan spara enorma belopp per år vid masstillverkning.
Vad CAM-programmen använder sig utav för algoritm för att hitta snabbaste vägen vet jag inte men kanske går att söka vidare på. Nu finns ju detta knappast som öppen källkod men kanske går det att hitta lite namn på de mattematiska modellerna och ta det där ifrån.

Visa signatur

Bara gammalt skräp...

Permalänk

Jag har funderat lite, och det verkar som att det löser sig om jag sätter $array[0][0] = 1, då startar den och landar på 0 och räknar med alla andra noder jag anger. Och det motsvarar ju den fysiska händelsen, man börjar och slutar på [0][0] med trucken, där ingen fysisk plockplats finns.

Jag tror att jag har löst problemet även med att översätta plocklistan till en array. Jag är en glad nybörjare men tro mig ha löst problemet genom följande kod:

<?php #SQL connection $mysqli = mysqli_connect("127.0.0.1","username","password","database"); $query = "SELECT * FROM coordinates"; $conn = (mysqli_query($mysqli, $query)); #general settings for total rows and columns $total_rows = 9; $total_columns = 10; #functions to convert XXYYZ to array[y][x] function row($string) { $split_string = str_split($string); $row = $split_string[2].$split_string[3]; #convert 0X to X if < two digits if($row < 10) { $row = $split_string[3]; }else { $row = $split_string[2].$split_string[3]; } return $row; } function column($string) { $split_string = str_split($string); $column = $split_string[4]; return $column; } #create "map" set all = 0 for($i = 0; $i < $total_columns + 1; $i++) { for($j = 0; $j < $total_rows + 1; $j++) { $input[$i][$j] = 0; } } #set initial coordinate to 1 $input[0][0] = 1; while($dbrow = mysqli_fetch_array($conn)) { $number = $dbrow['number']; #define return from functions as variables $row = row($number); $column = column($number); #put values into array $input[$row][$column] = 1; } ?>

Denna gör tex 01025 (01 = hylla, 02 = rad, 5 = höjd)
Till $array[2][5] = 1

och tex
01126 > $array[12][6] = 1

Edit
Piss också, har precis fått det att funka, så upptäcker jag med 15 koordinater att det inte orkar köra mina listor. Får "max timeout" av PHP på 120 sec, plus att fläkten i datorn drar igång på max så fort jag kör algoritmen. Har ändå en ny i9.

Permalänk

Jag kan köra 9 noder på 13 sekunder, 10 stycken funkar inte. Då överstiger det PHP's 120 sec max gräns.
Kan jag köra 20 stycken i Python då tro? Är det så stor skillnad?

Permalänk
Medlem

fakultetet av 9 = 9! = 1*2*3*4*5*6*7*8*9 = 362880
fakultetet av 10 = 10! = 3628800 ; 10 gånger mer operationer än 9!
fakultetet av 11 = 11! = 39916800 ; 110 gånger mer operationer än 9!
.
.
.
fakultetet av 20 = 20! = 2.43*10^18 ; 6704 miljader gånger längre beräkningstid än att räkna 9! eller 2.76 miljoner år att beräkna med samma beräkningstakt som du löste med att räkna med 9 noder...

dvs varje objekt/nod man lägger till ger mer än 10 ggr mer i tid/beräkningar

Om 9 noder tog 13 sekunder och 10 noder tog > 120 sekunder (troligen tar 130 sekunder om du får bort tidsspärren och det skalar som ovan) så verkar inte din algoritm ge någon större vinst gentemot att räkna samtliga alternativ och då är tyngd av verkan med fakultetet antal alternativ att prova igenom vilket gör att man slår huvudet i väggen redan vid 12 - 13 objekt då det tar timmar och dagar att räkna på istället för sekunder.

även om du kunde räkna 100 ggr snabbare så kommer det bara ge att du kan sätta in knappt 2 noder till för samma beräkningstid och det är väldigt långt till 20 noder om man redan har problem med lång beräkningstid med 9-10 noder

Med andra ord är det enormt viktigt att titta på olika algoritmer för TSP-problemen, men då på bekostnad att man inte alltid får den mest optimala vägen - men kanske för det mesta tillräckligt bra att det är lönt att räkna på det...

som redan nämnt så är detta en essentiellt problem med CNC-maskiner och räkna ut verktygsbanor - men redan på penplottertiden på 1980-talet var det många som försökte ge sig i kast att optimera dragningarna med så få penbyten och rörelser så effektiva som praktiskt möjligt med tänkta accelerationer och inbromsningar och det visade sig inte vara något lätt problem och både minne och datakraften tröt fort...

Permalänk
Medlem
Skrivet av RobinJacobsson:

Jag upptäckte också att jag bara fick heltal i avstånd av din kod, vilket verkar lite konstigt när man borde åka raka vägen mellan punkterna, så jag skrev om din funktion, vänligen kolla så att jag har gjort rätt!

function cost($from, $to) { list($row1, $col1) = $from; list($row2, $col2) = $to; //Min kod (Pythagoras) return sqrt(pow(abs($row2 - $row1) * 2, 2) + pow(abs($col2 - $col1), 2)); //Din kod return max(abs($row1 - $row2) * 2, abs($col1 - $col2)); }

Skillnaden mellan din och min formel är att min optimerar efter tid och din efter distans. Det är långt ifrån uppenbart vad det verkligen gör för skillnad men tar man tex punkterna (0,0), (4,6), (1,9), (6,6) (skrivna som x,y alltså omvänd ordning från row,col) så får man två olika förslag på bästa rutt.

Din formel ger: (0,0)->(6,6)->(4,6)->(1,9)->(0,0) (0,0)->(6,6) time: 12 dist: 13.416407864998739 (6,6)->(4,6) time: 2 dist: 2.0 (4,6)->(1,9) time: 6 dist: 6.708203932499369 (1,9)->(0,0) time: 18 dist: 18.027756377319946 total: 38 total: 40.15236817481805 Min formel ger: (0,0)->(6,6)->(1,9)->(4,6)->(0,0) (0,0)->(6,6) time: 12 dist: 13.416407864998739 (6,6)->(1,9) time: 6 dist: 7.810249675906654 (1,9)->(4,6) time: 6 dist: 6.708203932499369 (4,6)->(0,0) time: 12 dist: 12.649110640673518 total: 36 total: 40.58397211407828

Ett väldigt bra hjälpmedel när man programmerar är penna och papper (eller ritplatta och tex ms whiteboard). Rita upp punkterna och tänk hur du skulle kunna köra trucken i verkligheten och hur lång tid det tar.

Förflyttningen (0,0)->(6,6) tar 12 tidsenheter eftersom du måste upp 6 våningar. Om vi förutsätter att du kan köra i max hastighet både framåt och uppåt samtidigt är du framme vid hylla 6 efter halva tiden. Du skulle kunna vända där och köra tillbaka till hylla 3 och sen vända tillbaka till hylla 6 igen innan du kommer till våning 6 på samma 12 tidsenheter.

Skrivet av RobinJacobsson:

Jag kan köra 9 noder på 13 sekunder, 10 stycken funkar inte. Då överstiger det PHP's 120 sec max gräns.
Kan jag köra 20 stycken i Python då tro? Är det så stor skillnad?

Php är tyvärr väldigt långsamt för den här typen av problem. Tiderna stämmer iofs inte riktigt med en korrekt (optimerad) implementation av Held-Karp. De borde ligga närmare 2-2.5 längre tid för varje gång du ökar antalet noder O(2^n * n^2). Jag kan absolut inget om php men utifrån koden du postat ser det ut som att en array i php är en typ av hashtable. På flera ställen skapas det strängar från två variabler som sen används för att slå upp ett värde i arrayen vilket inte är speciellt effektivt.

Den rekursiva version jag skrev i scala tar ~2 sekunder för 20 noder. Du behöver nog använda ett effektivare språk (c/c#/Java...) för storleken på problemet du har eller byta algoritm. Branch and Bound löser tsp med något fler noder och det finns flera andra algoritmer att välja på som ger en rutt som ligger väldigt nära den optimala.

Om andra språk inte är ett alternativ så är en ide att testa från andra hållet istället med enklast möjliga algoritm.

Nearest Neighbour
Du kommer oftast inte få en optimal rutt men eftersom förflyttningar i y-led dominerar kostnaden borde du ändå få en klar förbättring jämfört med sortering i x-led. Fördelen är dessutom att algoritmen är väldigt enkel.

Antingen googlar du en php version av nearest neighbour eller så har du en kort beskrivning av hur den rekursiva versionen fungerar här:

Pseudokod:

CostFn(from, to) som tidigare NearestNeighbour(Points, start) Recur(start, Points - start, (start)) Recur(current, Rest, Path) Om Rest är tom returnera Path + start Annars next <- x ∈ Rest | med lägst kostnad CostFn(current, x) Recur(next, Rest - next, Path + next)

Du har din kostnadsfunktion som fungerar på samma sätt som tidigare. Funktionen NearestNeighbour tar två argument, start som är den positionen du vill utgå ifrån och Points som är en samling av positioner (hela listan du vill besöka). Points ska tillåta att man lägger till flera positioner som har samma värde och att man tar bort en position. Den typen av samling brukar ofta kallas MultiSet eller Bag. NearestNeighbour anropar hjälpfunktionen Recur som gör allt arbete.
Recur tar tre argument, current som är den position du befinner dig vid nu, Rest som innehåller alla positioner du har kvar att besöka och Path som är rutten du håller på att bygga upp.
Det första du gör i Recur är att kolla om det finns fler positioner kvar att besöka i Rest.
Om du har besökt alla positioner så ska du bara tillbaka till starten, returnera Path med start tillagd på slutet.
Om du har positioner kvar att besöka så jämför du kostnaden mellan current och alla positioner kvar i Rest, väljer den med minst kostnad som
next och anropar Recur(next som nuvarande, Rest utan next, Path med next tillagd på slutet).

Så här skulle koden kunna se ut i ett annat språk än php:

def nearestNeighbour(points: MultiSet[(Int, Int)], start: (Int, Int)) = def costFn(p1: (Int, Int), p2: (Int, Int)) = (p1._1 - p2._1).abs max ((p1._2 - p2._2).abs * 2) def recur(curr: (Int, Int), rest: MultiSet[(Int, Int)], total: Int, path: Vector[(Int, Int)]): (Int, Vector[(Int, Int)]) = if (rest.isEmpty) then (total + costFn(curr, start), path :+ start) else val (cost, next) = rest.map(point => (costFn(curr, point), point)).minBy(_._1) recur(next, rest - next, total + cost, path :+ next) end recur recur(start, points - start, 0, Vector(start)) end nearestNeighbour

Permalänk

Tack för era svar! Jag har precis vaknat så jag vet inte riktigt vart jag är, men jag förstår inte hur det kan skilja sig mellan tid och avstånd, för det går ju hand i hand. Mindre avstånd borde ju innebära lägre tidsåtgång för förflyttningen.

Tror du att Python funkar? Har precis börjat kika på det och funderar på att börja leta efter en färdig held karp i det språket istället då om PHP är för långsamt!

Skickades från m.sweclockers.com

Permalänk

Jag hittade en kod skriven i Python som jag hoppas kan funka. Dock när jag importerar och försöker köra så klagar den på

arg = sys.argv[1]

och säger "IndexError: list index out of range"

Jag antar att jag måste ange sökvägen till filen innehållandes avstånd i

with open(filename, 'rb') as f:

men det fungerar inte även om jag ändrar "filename".

import itertools import random import sys def held_karp(dists): """ Implementation of Held-Karp, an algorithm that solves the Traveling Salesman Problem using dynamic programming with memoization. Parameters: dists: distance matrix Returns: A tuple, (cost, path). """ n = len(dists) # Maps each subset of the nodes to the cost to reach that subset, as well # as what node it passed before reaching this subset. # Node subsets are represented as set bits. C = {} # Set transition cost from initial state for k in range(1, n): C[(1 << k, k)] = (dists[0][k], 0) # Iterate subsets of increasing length and store intermediate results # in classic dynamic programming manner for subset_size in range(2, n): for subset in itertools.combinations(range(1, n), subset_size): # Set bits for all nodes in this subset bits = 0 for bit in subset: bits |= 1 << bit # Find the lowest cost to get to this subset for k in subset: prev = bits & ~(1 << k) res = [] for m in subset: if m == 0 or m == k: continue res.append((C[(prev, m)][0] + dists[m][k], m)) C[(bits, k)] = min(res) # We're interested in all bits but the least significant (the start state) bits = (2**n - 1) - 1 # Calculate optimal cost res = [] for k in range(1, n): res.append((C[(bits, k)][0] + dists[k][0], k)) opt, parent = min(res) # Backtrack to find full path path = [] for i in range(n - 1): path.append(parent) new_bits = bits & ~(1 << parent) _, parent = C[(bits, parent)] bits = new_bits # Add implicit start state path.append(0) return opt, list(reversed(path)) def generate_distances(n): dists = [[0] * n for i in range(n)] for i in range(n): for j in range(i+1, n): dists[i][j] = dists[j][i] = random.randint(1, 99) return dists def read_distances(filename): dists = [] with open(filename, 'rb') as f: for line in f: # Skip comments if line[0] == '#': continue dists.append(map(int, map(str.strip, line.split(',')))) return dists if __name__ == '__main__': arg = sys.argv[1] if arg.endswith('.csv'): dists = read_distances(arg) else: dists = generate_distances(int(arg)) # Pretty-print the distance matrix for row in dists: print(''.join([str(n).rjust(3, ' ') for n in row])) print('') print(held_karp(dists))

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

Men är det enligt reglemente att färdas på trucken i upphöjt läge då? Om så inte är fallet, vilket jag skulle kunna tänka mig dent enligt regelbok är (även om en del sedan kanske ignorerar det), så blir z-axeln i princip ignorerbar.

För längesedan skrev jag kod med A* och viktade grafer för att tex räkna ut vägen i ett kollektivtrafiknät. Man kunde då plocka fram snabbaste, kortaste eller den väg med minst byten. Skillnaden är egentligen hur man viktar grafen, avstånd, tid osv.
Ett liknande upplägg hade kunnat fungera här där nätet på förväg hade kunnat genereras och lösningar om kortaste/snabbaste vägar att ta sig till de olika punkterna hade kunnat plockas fram.

Visa signatur

Huvudriggen är en Gigabyte Aorus Xtreme | 128gb DDR5 6000 | Ryzen 7950X | 3080Ti
Utöver det är det för många datorer, boxar och servar för att lista :P