Permalänk
Medlem
Skrivet av RobinJacobsson:

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

PHP5 var rätt långsamt. PHP7 är bra mycket snabbare och PHP8 ser ut att få en JIT-compiler så kommer nog bli snabbare det också. Bilden av PHP som långsamt i gruppen Python, Perl och PHP är rätt missvisande idag. (https://benchmarksgame-team.pages.debian.net/benchmarksgame/f...) Sedan beror det självklart på exakt vad man gör. Vissa saker är snabbare i olika språk. Om prestanda är ett primary concern så hade jag nog gjort lösning i C++.

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

Permalänk

Okej, är skillnaden så stor att PHP inte klarar 10 noder, men tex med c++ skulle jag eventuellt kunna lösa 21 noder? Vilka tider snackar vi om då jämfört med mina 13 sekunder @ 9 noder i PHP?

Jag vet inte vilken version av PHP jag har, är på jobbet. Kör wamp iallafall. Är PHP8 släppt eller?

Skickades från m.sweclockers.com

Permalänk
Medlem
Skrivet av RobinJacobsson:

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.

Vad sägs om en tävling i virtuell truckkörning?
Vi placerar samma produkt på fyra olika hyllor i rad på våning två (0,2) (1,2) (2,2) (3,2). Man startar vid (0,0) och ska hämta en produkt från valfri plats och sen ta sig tillbaka till starten. Det gäller samma regler som tidigare för hur trucken kan röra sig, båda riktningarna samtidigt och halva hastigheten i y-led. Du kan välja tre plockplatser och jag tar den som blir över. Lyckas du slå min tid med något av dina tre försök så vinner du, annars vinner jag.
Ställer du upp och hur mycket pengar satsar du?

Skrivet av RobinJacobsson:

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!

Python är också ganska långsamt. Dessutom ser det ut som både php och python koden du postat använder en hashtable för att spara de partiella lösningarna. Byter jag till att lagra kostnaden för lösningarna i en hashtable istället för en primitiv (n * 2^n) 2d array blir min kod ~5ggr långsammare. Att du får lång körtid beror alltså både på valet av språk och att algoritmen inte är implementerad på ett optimalt sätt.

Jag skulle verkligen rekommendera att du försöker sätta dig in i exakt hur den algoritm du tänker använda fungerar istället för att bara kopiera färdig kod. Tänk på att om du använder den här lösningen på jobbet så kan du få frågor om hur den fungerar eller om din lösning går att tillämpa på andra liknande problem. Av den anledningen kan det också vara bra att byta till en enklare algoritm.

Permalänk
Skrivet av jclr:

Jag skulle verkligen rekommendera att du försöker sätta dig in i exakt hur den algoritm du tänker använda fungerar istället för att bara kopiera färdig kod. Tänk på att om du använder den här lösningen på jobbet så kan du få frågor om hur den fungerar eller om din lösning går att tillämpa på andra liknande problem. Av den anledningen kan det också vara bra att byta till en enklare algoritm.

Jag vill återigen poängtera att jag inte vill kalla mig programmerare, och min anställningsform berör inte alls detta ämne.
Däremot vill jag försöka implementera en kod som kan lösa och underlätta rutter i olika situationer i jobbet. Om jag lyckas lära mig och förstå koden så ser jag det bara som ett plus. Men det primära är att få igång en kod där jag kan lägga in mina listor. All hjälp är tacksam, min PHP kod funkar men tyvärr bara på ett för litet antal artiklar.

Permalänk

Jag har fått igång Python och tänkte ge det ett försök att få igång koden där istället och se om jag kan få en förbättrad tid. Har du någon presentation på hur en primitiv 2d-array-lösning ser ut i förhållande till hashtable?

Permalänk

Om du istället för att snöa in på Held-Karp kan tänka dig enklare lösningsmetoder så kan du exempelvis köra tre svep. Som jag har förstått problemet så har du 9 hyllplan och det är dyrare att åka i upp och ned än att åka höger och vänster.

Låt säga att din hylla hylla har 9 hyllplan i höjdled (y-led) och 10 platser i bredvid varandra (x-led).
1) Börja i (0,0) och plockar allt på hylla 0,1, och 2 mellan medan v åker får 0 till 9 i x-led.
2) Plockar plan 3,4,5 mellan plats 9 och 5 i x-led
3) Plocka plan 6,7,8 mellan 9 och 0 i x-led
4) Plocka plan 3,4,5 mellan 0 och 4 i x-led
5) Tillbaka till (0,0)

Detta ger dig en rutt du kan starta med. Den kommer inte vara optimal, men den kommer sannolikt vara betydligt bättre än en slumpmässig plockordning.

I nästa steg kan du titta på om du kan förbättra rutten genom att kasta om ordningen lite och se om det blir kortare totaltid för traverseringen. För varje nod i grafen, kolla vad som händer om du besöker närmsta grannen före/efter. (Se 2-opt på https://en.wikipedia.org/wiki/Travelling_salesman_problem). Detta borde ta hand om en del enkla fall som om du befinner dig på plan 2 så kan du passa på att ta saken som ligger ett steg upp på plan 3 för att det är närmare till den härifrån än från dess grannar på plan 3,4,5. Den hittar även en del fall då du borde åka lite i x-led för att slippa åka i y-led.

Det kommer inte ge en optimal lösning men den är sannolikt tillräckligt bra till en betydligt mindre arbetsinsats.

Permalänk

Men held-karp borde väl ge en ännu mer optimal rutt? Isåfall är det väl att föredra att använda den istället?
Det enda jag behöver lösa är att kunna köra mer än 9 noder som jag gör just nu i PHP.

Permalänk

@RobinJacobsson: Held-Karp ger säkert en bättre resultat, men det är tråkigt om det tar längre tid att räkna ut den optimala rutten än att plocka i slumpvis ordning. Ibland får man nöja sig med Good Enough.

Permalänk
Medlem

@Ingetledigtnamn: Kan bara hålla med. Känns lite som att det är någon som försöker vara smartare än folk som är anställda för att sköta det här. Inte sagt att det inte går att optimera det hela. Men om nu företaget har folk som verkligen ska försöka får ner tiderna så optimalt som det bara går så känns det lite konstigt om de inte har tänkt på det här. Kanske har de redan kollat på problemet och kommit fram till att det ger inte de vinsterna som TS tror sig se? Jag vet inte. Men om det nu är ett väldigt stort företag så känns det väldigt konstigt om de inte redan tidigare har kollat på det här problemet och gjort den avvägning och det är värt det hela. Men vad vet jag.

Permalänk

Såhär är det. Det finns ca 40 olika plocklistor som alltid innehåller samma artiklar. Har man väl funnit snabbaste vägen en gång så behövs detta inte upprepas.

Och vidare - företagets mjukvarusystem ligger inte lokalt och det finns ett fåtal inom Sverige som kan lägga beställningar på ändringar och dylikt till företaget som har säte utomlands- och detta påverkar mjukvaran inom hela koncernen på SAMTLIGA fabriker. Då kanske du får en uppfattning om vilken stor apparat det handlar om. Mellan dessa och mig finns tekniker utan någon som helst programmeringskunskap och antagligen utan vetskap om dessa algoritmer. Dom har optimerat platser fysiskt för bättre tider, sen sorterar mjukvaran i en simpel kronologisk ordning efter gång och rad, inte i närheten av snabbaste rutt. Jag försöker inte vara smartare, jag har bara råkat uppmärksamma att det går att förbättra och kunskapen finns inte på annat håll inom företaget. Kan jag lösa det skulle det sätta mig i en bättre position, vilket självklart också vore roligt. Inte för mina kunskaper inom utveckling, utan för att jag uppmärksammat problemet och lyckats ta fram en lösning.

Huruvida storleken på förbättringen är värdefull eller ej vet jag inte eftersom jag inte har några optimerade tider att jämföra med. Men själva plockmomentet utgör uppskattningsvis 70% av arbetsdagen och med 4 personer som plockar likadant ser jag värde i en effektivisering på redan 5-10%

Skickades från m.sweclockers.com

Permalänk
Datavetare
Skrivet av RobinJacobsson:

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.

Kul problem, ska slänga ihop ett program i Go som använder Held-Karp under morgondagen. Om jag förstår algoritmen rätt borde det vara en smal sak att sprida delen där man räknar ut kortaste vägen för en visst antal steg över alla kärnor.

Kroppen till det fetmarkerade ser ut att kunna spridas över kärnor förutsätt att man inte använder en hash-tabell att lagra S i (vilket både PHP och Python exemplen gör). Om man hanterar den som en array som också är förallokerad behövs inga lås då varje vända i den kroppen kommer skriva till olika delar i den arrayen.

for s := 2 to n-1 do for all S ⊆ {2, . . . , n}, |S| = s do for all k ∈ S do C(S, k) := minm≠k,m∈S [C(S\{k}, m) + dm,k] end for end for end for

Ett klarläggande: gissar att trucken inte längre man röra sig i X-led när den ställer om sig för att nå högre än 4:e våningen? Om så är fallet lär man ju ta med det i sättet man räknar avstånd!

Gjorde ett snabbskott med en enkeltrådad brute-force lösning av TSP i Go. D.v.s. kör bara en bredden-först fram till att en hel loop genom alla punkter tillbaka still start hamnar först i prioritetskön.

Går att lösa 11 steg på 17s på min rätt gamla bärbara (i7-5700U). 12 steg fallerar p.g.a. för lite RAM (16 GB), men är lösbart på min Ryzen (40 GB RAM). Visar ändå att som redan nämnts i tråden är brute-force rätt värdelöst för detta problem.

Kan skriva Go-programmet så det tar samma indata som Python-programmet, postar det här i tråden under morgondagen.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Härligt!

1. Trucken går med samma hastighet i X-led oavsett hur högt man är hissad.

2.Precis innan man når att plocka från fjärde hyllan så tar det tidsmässigt en extra plats i höjd för trucken att ställa om sig till ett annat läge. Så mellan vån 3-4 är avståndet egentligen 2 enheter, inte 1.

3. Att förflytta sig i X-led går dubbelt så snabbt som i Y-led

4. Man börjar och slutar alltid på (0, 0)
Skickades från m.sweclockers.com

Permalänk
Datavetare

Blev lite sent, tog lite mer tid jag trodde att dra Ethernet-kabel i stugan...

Lämnar inga garantier på detta, men den lilla testning jag gjort ger samma resultat med mitt Go-program som med Python-programmet du postade tidigare.

Skalningen är inte perfekt med CPU-kärnor, vilket var väntat, men skalar ändå helt OK. Detta är en körning med 24 artiklar (25 punkter att besöka när man räknar in start/mål på 0,0). Tar runt en minut och kräver ~32 GB RAM.

$ time ./main 26 { { 0, 27, 27, 28, 23, 25, 34, 26, 12, 9, 6, 28, 46, 28, 2, 12, 15, 30, 47, 41, 2, 12, 38, 23, 29, 33 }, { 27, 0, 0, 4, 4, 6, 10, 6, 18, 18, 21, 4, 19, 6, 27, 26, 12, 3, 20, 14, 29, 15, 11, 10, 2, 8 }, { 27, 0, 0, 4, 4, 6, 10, 6, 18, 18, 21, 4, 19, 6, 27, 26, 12, 3, 20, 14, 29, 15, 11, 10, 2, 8 }, { 28, 4, 4, 0, 8, 10, 14, 10, 19, 19, 22, 0, 18, 10, 28, 27, 13, 4, 19, 13, 30, 16, 12, 14, 2, 12 }, { 23, 4, 4, 8, 0, 2, 11, 3, 14, 14, 17, 8, 23, 5, 23, 22, 8, 7, 24, 18, 25, 11, 15, 6, 6, 10 }, { 25, 6, 6, 10, 2, 0, 9, 1, 16, 16, 19, 10, 21, 3, 25, 24, 10, 6, 22, 16, 27, 13, 13, 4, 8, 8 }, { 34, 10, 10, 14, 11, 9, 0, 8, 25, 25, 28, 14, 12, 6, 34, 33, 19, 10, 13, 12, 36, 22, 4, 11, 12, 2 }, { 26, 6, 6, 10, 3, 1, 8, 0, 17, 17, 20, 10, 20, 2, 26, 25, 11, 6, 21, 15, 28, 14, 12, 4, 8, 7 }, { 12, 18, 18, 19, 14, 16, 25, 17, 0, 4, 10, 19, 37, 19, 10, 8, 6, 21, 38, 32, 14, 6, 29, 16, 20, 24 }, { 9, 18, 18, 19, 14, 16, 25, 17, 4, 0, 6, 19, 37, 19, 9, 8, 6, 21, 38, 32, 11, 3, 29, 14, 20, 24 }, { 6, 21, 21, 22, 17, 19, 28, 20, 10, 6, 0, 22, 40, 22, 6, 10, 9, 24, 41, 35, 8, 6, 32, 17, 23, 27 }, { 28, 4, 4, 0, 8, 10, 14, 10, 19, 19, 22, 0, 18, 10, 28, 27, 13, 4, 19, 13, 30, 16, 12, 14, 2, 12 }, { 46, 19, 19, 18, 23, 21, 12, 20, 37, 37, 40, 18, 0, 18, 46, 45, 31, 16, 12, 12, 48, 34, 8, 23, 17, 13 }, { 28, 6, 6, 10, 5, 3, 6, 2, 19, 19, 22, 10, 18, 0, 28, 27, 13, 6, 19, 13, 30, 16, 10, 5, 8, 5 }, { 2, 27, 27, 28, 23, 25, 34, 26, 10, 9, 6, 28, 46, 28, 0, 10, 15, 30, 47, 41, 4, 12, 38, 23, 29, 33 }, { 12, 26, 26, 27, 22, 24, 33, 25, 8, 8, 10, 27, 45, 27, 10, 0, 14, 29, 46, 40, 14, 11, 37, 22, 28, 32 }, { 15, 12, 12, 13, 8, 10, 19, 11, 6, 6, 9, 13, 31, 13, 15, 14, 0, 15, 32, 26, 17, 4, 23, 14, 14, 18 }, { 30, 3, 3, 4, 7, 6, 10, 6, 21, 21, 24, 4, 16, 6, 30, 29, 15, 0, 17, 11, 32, 18, 8, 10, 2, 8 }, { 47, 20, 20, 19, 24, 22, 13, 21, 38, 38, 41, 19, 12, 19, 47, 46, 32, 17, 0, 6, 49, 35, 10, 24, 18, 14 }, { 41, 14, 14, 13, 18, 16, 12, 15, 32, 32, 35, 13, 12, 13, 41, 40, 26, 11, 6, 0, 43, 29, 10, 18, 12, 10 }, { 2, 29, 29, 30, 25, 27, 36, 28, 14, 11, 8, 30, 48, 30, 4, 14, 17, 32, 49, 43, 0, 14, 40, 25, 31, 35 }, { 12, 15, 15, 16, 11, 13, 22, 14, 6, 3, 6, 16, 34, 16, 12, 11, 4, 18, 35, 29, 14, 0, 26, 11, 17, 21 }, { 38, 11, 11, 12, 15, 13, 4, 12, 29, 29, 32, 12, 8, 10, 38, 37, 23, 8, 10, 10, 40, 26, 0, 15, 10, 5 }, { 23, 10, 10, 14, 6, 4, 11, 4, 16, 14, 17, 14, 23, 5, 23, 22, 14, 10, 24, 18, 25, 11, 15, 0, 12, 10 }, { 29, 2, 2, 2, 6, 8, 12, 8, 20, 20, 23, 2, 17, 8, 29, 28, 14, 2, 18, 12, 31, 17, 10, 12, 0, 10 }, { 33, 8, 8, 12, 10, 8, 2, 7, 24, 24, 27, 12, 13, 5, 33, 32, 18, 8, 14, 10, 35, 21, 5, 10, 10, 0 }, } 131 [0 20 14 15 8 16 4 2 1 24 11 3 17 19 18 12 22 6 25 13 7 5 23 21 9 10 0] real 1m1.566s user 13m31.732s sys 1m37.333s

Dold text

Programmet kräver att du installerar Go-miljön, den hittar du här. Du kan bygga programmet så här

$ cd <PATH_WHERE_MAIN.GO_IS_LOCATED> $ go build <FILENAME>.go

Programmet tar noll eller ett argument. Med noll argument får man skriva in kostnadsmatrisen (som CSV) på stdin. Med ett argument fungerar det som Python-programmet, d.v.s. en siffra kör en simulering och något som slutar på ".csv" antas vara en fil med en kostnadsmatris.

package main import ( "bytes" "encoding/csv" "fmt" "io" "log" "math/bits" "math/rand" "os" "runtime" "strconv" "strings" "time" ) const MaxInt = int(^uint(0) >> 1) // IntSet type IntSet struct { Storage uint } func (vs IntSet) Contains(value int) bool { return (vs.Storage & (1 << uint(value))) != 0 } func (vs IntSet) Count() int { return bits.OnesCount(vs.Storage) } func (vs *IntSet) Insert(value int) { vs.Storage |= 1 << uint(value) } func (vs *IntSet) Remove(value int) { vs.Storage &= ^(1 << uint(value)) } func (vs IntSet) Value() int { return int(vs.Storage >> 1) } func (vs IntSet) Iter() []int { n := vs.Count() v := make([]int, n) for c, i := 0, 0; c < n; i++ { if vs.Contains(i) { v[c] = i c++ } } return v } func (vs IntSet) String() string { buf := bytes.Buffer{} buf.WriteString("{") delim := "" for c, i := 0, 0; c < vs.Count(); i++ { if vs.Contains(i) { buf.WriteString(fmt.Sprintf("%s%v", delim, i)) delim = "," c++ } } buf.WriteString("}") return buf.String() } // Combinations 'k' integers from a serie '1..n' type Combs []IntSet func combWithLen(n, k, first int, vs IntSet, acc Combs) Combs { if k > vs.Count() { for x := first; x <= n; x++ { s := vs s.Insert(x) acc = combWithLen(n, k, x + 1, s, acc) } } else { acc = append(acc, vs) } return acc } func Comb(n, k int) Combs { return combWithLen(n, k, 1, IntSet{}, Combs{}) } // Held Karp type Path struct { Cost int From int } func minPath(paths []Path) Path { m := paths[0] for i := 1; i < len(paths); i++ { if m.Cost > paths[i].Cost { m = paths[i] } } return m } func pathFromTo(from, to int, c [][]Path, dists CostMatrix, prev IntSet) Path { p := Path{} p.Cost = c[prev.Value()][from-1].Cost + dists[from][to] p.From = from return p } func reverse(a []int) []int { for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 { a[i], a[j] = a[j], a[i] } return a } // CostMatrix type CostMatrix [][]int func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) { maxWorkers := runtime.NumCPU() workers := 0 done := make(chan bool) for _, visited := range(Comb(edges, subsetSz)) { if workers == maxWorkers { <-done } else { workers += 1 } go func(vs IntSet) { subset := vs.Iter() // Find the lowest cost to get to this subset for _, k := range subset { prev := vs prev.Remove(k) res := []Path{} for _, m := range subset { if m != k { res = append(res, pathFromTo(m, k, c, dists, prev)) } } if len(res) > 0 { c[vs.Value()][k-1] = minPath(res) } } done<- true }(visited) } // Wait for all workers to finish for ;workers > 0; workers -= 1 { <-done } } func (dists CostMatrix) ShortestPath() (int, []int) { n := len(dists) c := make([][]Path, 1<<uint(n-1)) for i := 0; i < len(c); i++ { c[i] = make([]Path, n-1) } // Add paths from start to first steps for k := 1; k < n; k++ { c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0} } for s := 2; s < n; s++ { dists.CalcCostToSubsets(c, n - 1, s) } visited := IntSet{} for k := 1; k < n; k++ { visited.Insert(k) } // Add path back to start and calculate optimal cost res := []Path{} for k := 1; k < n; k++ { res = append(res, pathFromTo(k, 0, c, dists, visited)) } p := minPath(res) cost := p.Cost // Backtrack to find path steps := make([]int, n+1) for i := 1; i < n; i++ { steps[i] = p.From from := p.From p = c[visited.Value()][p.From-1] visited.Remove(from) } return cost, reverse(steps) } func (c CostMatrix) MaxDigitWidth() (width int) { for row := 0; row < len(c); row++ { for col := 0; col < len(c[row]); col++ { w := 0 for d := c[row][col]; d > 0; d /= 10 { w += 1 } if width < w { width = w } } } return } func (c CostMatrix) String() string { fmtstr := fmt.Sprintf("%%%vv", c.MaxDigitWidth()) buf := bytes.Buffer{} for row := 0; row < len(c); row++ { if row == 0 { buf.WriteString("{\n") } buf.WriteString(" { ") for col := 0; col < len(c[row]); col++ { buf.WriteString(fmt.Sprintf(fmtstr, c[row][col])) if col != len(c[row])-1 { buf.WriteString(", ") } } buf.WriteString(" },\n") if row == len(c)-1 { buf.WriteString("}") } else { } } return buf.String() } func Abs(n int) int { if n < 0 { return -n } return n } func Max(a, b int) int { if a < b { return b } return a } type Location struct { shelf int level int } func cost(from, to Location) int { dx := Abs(from.shelf - to.shelf) dy := Abs(from.level - to.level) * 2 return Max(dx, dy) } func zeroMatrix(dim int) CostMatrix { var c CostMatrix = make([][]int, dim) for i := range c { c[i] = make([]int, dim) } return c } func genMatrix(nodes, depth, height int) CostMatrix { rand.Seed(time.Now().UnixNano()) c := zeroMatrix(nodes) l := make([]Location, nodes) for i := range l { l[i] = Location{rand.Intn(depth), rand.Intn(height)} } for row := 0; row < nodes; row++ { for col := row + 1; col < nodes; col++ { c[row][col] = cost(l[row], l[col]) c[col][row] = c[row][col] } } return c } func readMatrix(r io.Reader) CostMatrix { cr := csv.NewReader(r) rec, err := cr.ReadAll() if err != nil { log.Fatalln(err) } M := zeroMatrix(len(rec)) for row, line := range rec { for col, str := range line { v, err := strconv.ParseInt(strings.TrimSpace(str), 10, 32) if err != nil { log.Fatalln(err) } M[row][col] = int(v) } } return M } func GetCostMatrix() CostMatrix { if len(os.Args) == 1 { return readMatrix(os.Stdin) } arg := os.Args[1] if strings.HasSuffix(arg, ".csv") { file, err := os.Open(arg) if err != nil { log.Fatalln(err) } return readMatrix(file) } dim, err := strconv.ParseInt(arg, 10, 32) if err != nil { log.Fatalln(err) } return genMatrix(int(dim), 50, 9) } // Program entrypoint func main() { c := GetCostMatrix() fmt.Println(c) fmt.Println(c.ShortestPath()) }

här är koden
Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

@RobinJacobsson:
Eftersom det handlar om listor som inte ändras hela tiden så spelar inte körtiden lika stor roll längre. Du ska helt klart använda en algoritm som ger optimal rutt. Det finns andra algoritmer än Held-Karp som ger en optimal lösning och som klarar större problem än Held-Karp, t.ex. Branch and Bound. Fördelen med Held-Karp är att den är enkel att skriva och faktiskt ganska enkel att förstå (om man vet hur dynamisk programmering fungerar, annars är det ren magi).

Jag gjorde en snabböversättning av min scala kod till python (vissa saker kan skrivas snyggare/bättre, programmerar normalt inte i python). Eftersom det börjar bli en hel del kod i den här tråden som inte är helt självklar att förstå så försöker jag även förklara hur algoritmen fungerar.

Steg ett är att skriva enklast möjliga algoritm som går igenom alla möjliga lösningar vilket tar O(n!) tid:

def tspStupid(graph): sz = len(graph) # antal noder all = (1 << sz) - 1 # alla bitar satta till 1 = alla noder besökta paths = {} def loop(curr, visited): # curr = vilken nod man beräknar optimal rutt för om man redan besökt de i visited och har resten kvar if visited == all: # om vi har besökt alla noder redan return graph[curr][0] # så är det bara kostnaden tillbaka till nod 0 kvar att lägga till else: minCost = 999999 # måste finnas något bättre? Int.MaxValue index = -1 for target in range(sz): # loopa över alla noder if (visited & (1 << target)) == 0: # kontrollera att man inte redan besökt target i rutten # beräkna kostnaden för att ta sig till target + lösningen för optimal rutt för resten av problemet utan target :) newCost = graph[curr][target] + loop(target, visited | (1 << target)) if newCost < minCost: # använd nya lösningen om den är bättre än de man sett tidigare minCost = newCost index = target paths[(curr, visited)] = index # spara vägen man tog för optimal rutt. return minCost cost = loop(0, 1) # beräkna lösningen från nod 0 med nod 0 redan besökt # reconstruct path path = [0] current = 0 state = 1 for _ in range(sz - 1): nextIndex = paths[(current, state)] current = nextIndex path.append(nextIndex) state = state | (1 << nextIndex) path.append(0) return cost, path

Besökta noder lagas som ett heltal istället för ett Set. T.ex. talet 37 (10011 binärt) är samma sak som ett Set innehållande nod 0,1 och 4.
(1 << n)
Ger ett tal med bit n satt till en etta, samma sak som 2 upphöjt med n.
(1 << n) - 1
Sätter n första bitarna till 1, för 4 noder blir det 2^4 = 16 (10000) -1 = 15 (01111)
(x & (1 << n)) == 0
Kollar om bit n inte är satt i talet x, används till att kolla om en nod inte är besökt
(x | (1 << n))
Sätter bit n i talet x till en etta, används till att lägga till en nod som besökt

Det rekursiva anropet till loop kräver lite mer förklaring.
Om vi tar en graf med bara 4 noder som exempel:
Första anropet till loop(0, 1) betyder att vi startar från nod 0 och sätter första biten i visited till 1 för att markera att vi redan besökt den noden.
För att ta reda på hur mycket det kostar att lösa hela problemet så loopar vi över alla noder och ignorerar de vi redan besökt {0} och försöker hitta den billigaste lösningen av de alternativ som finns kvar. Minsta av (0->1 + resten, 0->2 + resten, 0->3 + resten)

0->1 + lösningen för resten {2,3} eftersom vi inte har löst resten av problemet så måste vi göra det först, alltså anropar vi loop rekursivt med loop(1, 0011) loopa igen över alla noder och ignorerar de vi redan besökt {0,1} och hitta den billigaste lösningen för 1->2 + lösningen för resten {3} eftersom vi inte har löst resten av problemet så måste vi göra det först, alltså anropar vi loop rekursivt med loop(2, 0111) loopa igen över alla noder och ignorerar de vi redan besökt {0,1,2} och hitta den billigaste lösningen för 2->3 + lösningen för resten {} eftersom vi inte har löst resten av problemet så måste vi göra det först, alltså anropar vi loop rekursivt med loop(3, 1111) den här gången har vi besökt alla noder och har bara kostnaden för 3->0 kvar vilket vi returnerar som svar. 1->3 + lösningen för resten {2} 3->2 + {} = 2->0 0->2 + lösningen för resten {1,3} 2->1 + {3} 1->3 + {} = 3->0 2->3 + {1} 3->1 + {} = 1->0 0->3 + lösningen för resten {1,2} 3->1 + {2} 1->2 + {} = 2->0 3->2 + {1} 2->1 + {} = 1->0

Det bildas en trädstruktur av anrop till loop. Det är först när man kommit längst ut på en gren som man börjar returnera svar uppåt i anropskedjan och kan börja jämföra minsta kostnad vid varje förgrening.

(0,0001) / | \ (1,0011) (2,0101) (3,1001) / \ / \ / \ (2,0111) (3,1011) (1,0111) (3,1101) (1,1011) (2,1101) | | | | | | (3,1111) (2,1111) (3,1111) (2,1111) (2,1111) (1,1111)

Här kan man se varför algoritmen blir så långsam när man ökar antalet noder. Med 20 noder så skulle lagret under första (0,00000000000000000001) innehålla 19 (n-1) anrop till loop. Varje sånt anrop skapar i sin tur 18 (n-2) nya osv.

Dags att "uppfinna" Held-Karp.
Om man skriver ut värdet för curr och visited i loop och kör tspStupid på en graf med >=5 noder så kommer man se att loop anropas med exakt samma värden flera gånger. Det betyder att man gör en massa onödigt arbete (varje anrop till loop utom det sista i varje kedja skapar nya anrop). Skulle det inte vara smart om man kunde återanvända redan beräknade resultat? Det är här smart rekursion/dynamisk programmering/memoizering kommer in i bilden. Varje gång man beräknar ett resultat för ett visst anrop av loop(curr, visited) så sparar man undan det. Istället för att hela tiden beräkna ny resultat så kontrollerar man först om man redan löst problemet och undviker på så sätt en massa extra jobb. Alla förgreningar under det anropet försvinner.

Det krävs bara några få rader kod för att göra om den naiva version av tsp till Held-Karp:

def tspSmart(graph): sz = len(graph) all = (1 << sz) - 1 paths = {} memo = {} # sparar kostnaden för partiella lösningar def loop(curr, visited): if visited == all: return graph[curr][0] elif (curr, visited) in memo: # kontrollera om vi redan har räknat ut den optimala dellösningen return memo[(curr, visited)] # isf kan vi returnera den direkt istället för att beräkna den igen else: minCost = 99999 index = -1 for target in range(sz): if (visited & (1 << target)) == 0: newCost = graph[curr][target] + loop(target, visited | (1 << target)) if newCost < minCost: minCost = newCost index = target paths[(curr, visited)] = index memo[(curr, visited)] = minCost # sparar den optimala kostnaden för en delrutt return minCost cost = loop(0, 1) # reconstruct path ... som tidigare eller en snyggare lösning ...

Inte den snabbaste lösningen men den löser ditt problem. Den har dessutom stöd för att lösa problemet parallellt och distribuerat utan att krångla till algoritmen om du vill att det ska gå fortare. Kör flera kopior av samma program med olika listor på samma dator, parallell lösning. Kör lista 1-20 på en dator och 21-40 på en annan dator, distribuerad lösning.

Permalänk
Medlem
Skrivet av Yoshman:

Kul problem, ska slänga ihop ett program i Go som använder Held-Karp under morgondagen. Om jag förstår algoritmen rätt borde det vara en smal sak att sprida delen där man räknar ut kortaste vägen för en visst antal steg över alla kärnor.

Parallell programmering handlar enbart om att öka prestanda (snabbare/större problem). Det är bättre att använda Branch and Bound istället om du vill skriva en optimerad (parallell) algoritm. Ts problem är dessutom trivialt att parallellisera utan att krångla till algoritmen. Optimera flera listor samtidigt med den enkeltrådade algoritmen.

Skrivet av Yoshman:

Gjorde ett snabbskott med en enkeltrådad brute-force lösning av TSP i Go. D.v.s. kör bara en bredden-först fram till att en hel loop genom alla punkter tillbaka still start hamnar först i prioritetskön.

Går att lösa 11 steg på 17s på min rätt gamla bärbara (i7-5700U). 12 steg fallerar p.g.a. för lite RAM (16 GB), men är lösbart på min Ryzen (40 GB RAM). Visar ändå att som redan nämnts i tråden är brute-force rätt värdelöst för detta problem.

Det är BFS som äter upp allt ditt minne. Hela fronten som söks av sparas ju i kön. Om du ändrar till DFS så fungerar brute-force bättre.

Permalänk
Skrivet av Yoshman:

Lämnar inga garantier på detta...

Wow, mycket engagerade och stora svar! Jag är ju inte insatt i Python eller Go så min första utmaning blir att få igång koden. Har du något emot att jag kontaktar dig utanför forumet för vägledning om jag stöter på problem?

Skickades från m.sweclockers.com

Permalänk
Datavetare
Skrivet av RobinJacobsson:

Wow, mycket engagerade och stora svar! Jag är ju inte insatt i Python eller Go så min första utmaning blir att få igång koden. Har du något emot att jag kontaktar dig utanför forumet för vägledning om jag stöter på problem?

Fråga på i tråden, då finns fler som kan hjälpa dig.

Jag skrev programmet betydligt mer för mig själv än för dig (sådan är jag ). Kändes som en perfekt sak att applicera på Go, ett språk jag håller på att lära mig på fritiden (jobbar primärt med C och C++ samt nu även lite Rust under hösten).

Hur mycket tid jag har till SweC forum under veckorna varierar rätt mycket. På dagarna är det ju jobb och just denna vecka har jag även en hel del kvällsarbete...

Skrivet av jclr:

Parallell programmering handlar enbart om att öka prestanda (snabbare/större problem). Det är bättre att använda Branch and Bound istället om du vill skriva en optimerad (parallell) algoritm. Ts problem är dessutom trivialt att parallellisera utan att krångla till algoritmen. Optimera flera listor samtidigt med den enkeltrådade algoritmen.

Nu var ju detta mest en "kul och relativt litet projekt att applicera på ett språk jag håller på att lära mig vid sidan av".

Självklart är det långt mer effektivt att köra flera oberoende sökningar parallellt, men ville bara se hur de 5-10 rader extra som krävdes för att köra den del jag fetmarkerade ovan fungerade i praktiken. Gick att förbättra effektiviteten ännu lite till genom en smärre omjustering av logiken.

Och specifikt för detta fall där högsta antalet produkter som ska plockas begränsar sig till 20 ville jag se om tiden kunde göras så kort att den kan anses "interaktiv", vilket jag skulle lägga vid <1s.

Är möjligt på t.ex. en i7-9700K och i9-9900K då de har lite högre prestanda per kärna jämfört med min 3900X som tar 1,0s på sig. Att det inte skalar superbra kan man notera i att samma uppgift tar 1,3s på en i7-8559U (sitter bl.a. i förra årets 13" MBP).

Skrivet av jclr:

Det är BFS som äter upp allt ditt minne. Hela fronten som söks av sparas ju i kön. Om du ändrar till DFS så fungerar brute-force bättre.

Är fullt medveten om orsaken till varför det drar så mycket minne. I detta fall är BFS, så länge man har nog med RAM, ofta lite effektivare än DFS om man använder en prioritetskö där den så här långt billigaste vägen alltid hamnar först. Sökningen terminerar då så fort man klivit förbi antal steg den kortaste vägen har. Eller, så är det om man ignorerar saker som CPU-cache och data-lokalitet... I verkligheten kan man inte ignorera sådant i just detta fall och DFS är i praktiken snabbare (ändrade lösningen till en DFS och verifierade detta)!

Men vare sig man kör DFS eller BFS (på väglängd) kommer man inte mycket lägre än 12-14 steg innan det tar till Ragnarök att bli klar.

Primär orsak till valet av BFS var mycket samma som att överhuvudtaget skriva en lösning i Go: har gjort en del nätverksapplikationer i Go samt hackat lite IoT-prylar till RPi, men aldrig behövt använda binärheap implementationen som finns i Go:s standardbibliotek. Så valde just den brute-force lösning specifikt för att få en anledning att testa på den (binärheap är en typisk ingrediens i en prioritetskö).

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Okej, har inte hunnit kolla på det än. Men gjorde du kostnadsmatrisen efter mina kriterier eller genererade du bara en egen?

Annars hade det varit kul att se skillnaden om du ville kolla tex denna listan som man plockar efter i dagsläget, och se hur mycket sträcka/tid man vinner på att optimera listan. Jag gav förresten fel kriterier, det är mellan vån 4-5 trucken stannar till och man ska räkna dubbla sträckor, inte mellan 3-4.

Lista:
03, 1
04, 6
05, 2
05, 6
06, 2
06, 3
07, 3
08, 6
10, 6

Skickades från m.sweclockers.com

Permalänk
Medlem

@RobinJacobsson:
Jag rekommenderar att du försöker skriva en funktion som tar en lista med punkter och skriver ut kostnaden mellan punkterna. Ännu bättre om den ritar upp punkterna och rutten grafiskt.

Om man räknar kostnaden så här:

costX = (p1.x - p2.x).abs costY = if (p1.y min p2.y) <= 4 && (p1.y max p2.y) >= 5 then (p1.y - p2.y).abs * 2 + 2 else (p1.y - p2.y).abs * 2 costX max costY

Så får man följande kostnader:

Enligt din lista:
(0,0)->(3,1): 3
(3,1)->(4,6): 12
(4,6)->(5,2): 10
(5,2)->(5,6): 10
(5,6)->(6,2): 10
(6,2)->(6,3): 2
(6,3)->(7,3): 1
(7,3)->(8,6): 8
(8,6)->(10,6): 2
(10,6)->(0,0): 14
total: 72

En optimal rutt:
(0,0)->(3,1): 3
(3,1)->(5,2): 2
(5,2)->(6,2): 1
(6,2)->(7,3): 2
(7,3)->(4,6): 8
(4,6)->(5,6): 1
(5,6)->(8,6): 3
(8,6)->(10,6): 2
(10,6)->(6,3): 8
(6,3)->(0,0): 6
total: 36

Kul exempel att titta grafiskt på. Jag tror de flesta skulle välja en rutt som kostar 37 först om man försöker lösa problemet för hand.

Permalänk

Okej, häftigt att det är så stor skillnad på totalkostnaden. Jag hade en sån funktion i PHP men den behandlade bara MAX 9st noder. Jag är för dåligt insatt i Python/Go, så om jag ska kunna behandla koordinater där måste koden i princip vara färdig, känns väldigt tråkigt när jag har en PHP kod som "egentligen" funkar

Skickades från m.sweclockers.com

Permalänk
Datavetare
Skrivet av RobinJacobsson:

Okej, har inte hunnit kolla på det än. Men gjorde du kostnadsmatrisen efter mina kriterier eller genererade du bara en egen?

Annars hade det varit kul att se skillnaden om du ville kolla tex denna listan som man plockar efter i dagsläget, och se hur mycket sträcka/tid man vinner på att optimera listan. Jag gav förresten fel kriterier, det är mellan vån 4-5 trucken stannar till och man ska räkna dubbla sträckor, inte mellan 3-4.

Lista:
03, 1
04, 6
05, 2
05, 6
06, 2
06, 3
07, 3
08, 6
10, 6

Skickades från m.sweclockers.com

Körtiden för att räkna ut optimal väg med både djupet-först brute-force och Held-Karp är i praktiken oberoende av hur kostnadsmatrisen ser ut, finns viss cache-effekt för Held-Karp men kan i det stora hela ignoreras.

För att bättre få ordning på detta kan du dela upp processen i flera separata program, då kan du skriva alla utom den prestandakritiska sökningen i PHP om du är mest bekväm i PHP.

Första steget är ju att ta indata du listar ovan, applicera kostnadsfunktionen för alla kombinationer för att skapa en kostnadsmatris

$ cat lista.csv 03, 1 04, 6 05, 2 05, 6 06, 2 06, 3 07, 3 08, 6 10, 6 $ cat lista.csv | plocklista_till_kosnadsmatris 0, 3, 14, 5, 14, 6, 6, 7, 14, 14 3, 0, 12, 2, 12, 3, 4, 4, 12, 12 14, 12, 0, 10, 1, 10, 8, 8, 4, 6 5, 2, 10, 0, 10, 1, 2, 2, 10, 10 14, 12, 1, 10, 0, 10, 8, 8, 3, 5 6, 3, 10, 1, 10, 0, 2, 2, 10, 10 6, 4, 8, 2, 8, 2, 0, 1, 8, 8 7, 4, 8, 2, 8, 2, 1, 0, 8, 8 14, 12, 4, 10, 3, 10, 8, 8, 0, 2 14, 12, 6, 10, 5, 10, 8, 8, 2, 0

Detta är då med en kostnadsfunktion som tar hänsyn till egenheten mellan hylla 4 och 5.

Men det som slog mig i plocklistan är precis det @jclr ger en vink om ovan, kanske räcker det hur bra som helst med den uppenbara heuristiken att köra ett pass bort from startpunkten där alla artiklar upp till och med hylla 4 plockas, för att på tillbakavägen ta alla artiklar som befinner sig på hylla 5 och högre. Det ger i just detta fall en kostnad på 37 mot optimal 36 och sorterade 72.

package main import ( "bytes" "encoding/csv" "fmt" "io" "log" "os" "strconv" "strings" ) const RECONFIG_HIGHT = 4 type Item struct { Pocket int Shelf int } type CostMatrix [][]int func GetItems(r io.Reader) []Item { cr := csv.NewReader(r) rec, err := cr.ReadAll() if err != nil { log.Fatalln(err) } items := []Item{Item{0, 0}} for _, line := range rec { item := Item{} for col, str := range line { v, err := strconv.ParseInt(strings.TrimSpace(str), 10, 32) if err != nil { log.Fatalln(err) } if col == 0 { item.Pocket = int(v) } else { item.Shelf = int(v) } } items = append(items, item) } return items } func Abs(n int) int { if n < 0 { return -n } return n } func Min(a, b int) int { if a > b { return b } return a } func Max(a, b int) int { if a < b { return b } return a } func LiftReconfigCost(fromShelf, toShelf int) int { if Min(fromShelf, toShelf) <= RECONFIG_HIGHT { if Max(fromShelf, toShelf) > RECONFIG_HIGHT { return 1 } } return 0 } func CostFromTo(from, to Item) int { dx := Abs(from.Pocket - to.Pocket) dy := Abs(from.Shelf - to.Shelf) dy += LiftReconfigCost(from.Shelf, to.Shelf) return Max(dx, dy * 2) } func CalcCostMatrix(items []Item) CostMatrix { C := make([][]int, len(items)) for row := range C { C[row] = make([]int, len(items)) } for row := 0; row < len(C); row++ { for col := row + 1; col < len(C); col++ { C[row][col] = CostFromTo(items[row], items[col]) C[col][row] = C[row][col] } } return C } func (c CostMatrix) MaxDigitWidth() (width int) { for row := 0; row < len(c); row++ { for col := 0; col < len(c[row]); col++ { w := 0 for d := c[row][col]; d > 0; d /= 10 { w += 1 } if width < w { width = w } } } return } func (c CostMatrix) String() string { fmtstr := fmt.Sprintf("%%%vv", c.MaxDigitWidth()) buf := bytes.Buffer{} for row := 0; row < len(c); row++ { for col := 0; col < len(c[row]); col++ { buf.WriteString(fmt.Sprintf(fmtstr, c[row][col])) if col != len(c[row])-1 { buf.WriteString(", ") } } buf.WriteString("\n") } buf.Truncate(buf.Len() - 1) return buf.String() } func main() { fmt.Println(CalcCostMatrix(GetItems(os.Stdin))) }

indata till kostnadsmatris i Go
Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Detta ser inte optimalt ut, gröna är ditt utfall och den röda är min plocklista. Den mest optimala rutten vore väl att linjerna inte korsade varandra, utan att man går från 0,0 till 4,6 ända bort till 10,6 och sedan rör sig neråt mot 7, 3 och hämtar resten på vägen tillbaka mot 0,0?

Permalänk
Medlem

Finns ytterligare optimeringspotential att organisera om innehållet i hyllorna efter hur vanligt det är att man behöver plocka varor tillsammans. Dvs behöver man alltid plocka 0,0 och 10,10 i samma runda, kanske det är värt att flytta allt från 10,10 till 0,1.

Permalänk

@gothxx: Självklart, jag har redogjort två gånger innan i den här tråden att sådana optimeringar redan gjorts, och att jag är medveten om det. Men problemet är att vissa artiklar går i olika/flera kit, och så vidare. Så här fokuserar vi på optimering av själva plocklistan.

Permalänk
Medlem

@RobinJacobsson:

Den rutten du föreslår är precis den jag menade med "Jag tror de flesta skulle välja en rutt som kostar 37 först om man försöker lösa problemet för hand." Det är den rutt som ser ut att vara den optimala men kostar 3+2+1+2+1+8+2+3+1+14 = 37, den gröna rutten du ritat upp kostar 36.

Grön rutt är alltså optimal om en robot åker runt och plockar men man ska nog fundera på den mänskliga faktorn också som jag skrivit tidigare. Kommer en "smart" plockare strunta i listan efter några gånger och plocka (6,3) tidigare eftersom man ändå är så nära. Kommer flera personer reagera på att den känns konstigt att åka tillbaka till nästan samma plats man redan varit på och därför dubbelkolla att man verkligen läst rätt. Det kan vara så att en något mindre optimal rutt fungerar bättre mentalt för människor. Det är omöjligt att veta innan man testat i verkligheten. Skiljer det mycket mellan vad man teoretiskt borde få för effektivisering och vad man ser i praktiken? Sker det fler misstag? Vad tycker de som plockar om de nya listorna efter ett par veckor?

Du måste helt enkelt testa och utvärdera hur det fungerar i verkligheten. Om du ska göra det helt själv utan att plocka in någon extern så kommer du nog inte undan att lära dig programmera. Med tanke på din beskrivning av företaget och att det ser ut att kunna leda till effektivisering så kan det vara värt den tiden. Välj ett språk som verkar intressant. Python är ett bra alternativ eftersom det ska vara lätt att lära sig men det finns flera andra alternativ. Go som @Yoshman använder så har du stora delar av koden färdig. Nåt jvm språk (java/kotlin/scala), jag använde t.ex. scala och R för visualisering. C# är också väldigt populärt. Du kommer säkert stöta på fler problem där du har nytta av de kunskaperna även om du inte vill jobba som programmerare.

Permalänk
Datavetare
Skrivet av RobinJacobsson:

Detta ser inte optimalt ut, gröna är ditt utfall och den röda är min plocklista. Den mest optimala rutten vore väl att linjerna inte korsade varandra, utan att man går från 0,0 till 4,6 ända bort till 10,6 och sedan rör sig neråt mot 7, 3 och hämtar resten på vägen tillbaka mot 0,0?

https://i.ibb.co/HTNMb0Y/P24101.jpg

Tänk på att det är dubbelt så dyrt att röra sig i Y-led, är därför bättre att multiplicera alla Y-koordinater med 2 för att visa det i bild.

Får denna bild, grön linje är optimal väg medan blå är vägen man får om man håller sig på hylla 4 och lägre på vägen bort och på hylla fem eller högre på vägen tillbaka.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

En annan sak som kanske skulle vara med i beräkningarna är om människor faktiskt åker på diagonalen. Den kortaste vägen kanske är på diagonalen, men kommer en mänsklig truckförare att följa den vägen? Är det inte lättare att åka i x-led först och sedan i y-led?

Om svaret är ja på föregående fråga, kommer en mänsklig förare ta "rätt" vinkel mellan två punkter? Jag skulle gissa att man åker i maximal hastighet i både x- och y-led till man är på rätt höjd eller på rätt kolumn(?) och sedan bara åker i ett led.

Steget mellan 36 och 37 kanske inte är värt att lägga en massa datakraft på...

Permalänk
Skrivet av jclr:

@RobinJacobsson:

...men man ska nog fundera på den mänskliga faktorn också som jag skrivit tidigare.

Mycket intressant tanke med den psykologiska aspekten. Jag kan tänka mig att situationer kan uppstå då man väljer en annan rutt och "ifrågasätter" listan, det sker dagligen i nuläget vad jag hört från kollegor, men då är ju listan heller inte optimerad. Men i dom fall som du tog som exempel där en "avstickare" finns så ser jag stor risk att man väljer den vägen manuellt, speciellt i denna listans fall då kostnaden bara skiljer "1" enhet, så att säga.

Och "Ingetledigtnamn", det är nog som du säger att man åker ju egentligen inte rakt mot punkten, utan stannar på en axel och kör resterande sträcka längs med den andra axeln. Detta är ju omöjligt att beräkna och jag antar att man kan se den exakta beräkningen som en medelsträcka.

Tack för era svar, det visade sig att mjukvaran vi använder inte går att manipulera på så sätt att man kan anpassa plocklistorna, dom sorteras automatiskt och vi kan inte påverka det på något sätt. (say no more...)

Permalänk

Men det hindrar ju inte att du producerar ett litet tilläggsblad. Du skall plocka lista 4b, plocka då dina artiklar i den här ordningen.

Permalänk

Jo jag har redan funderat på det alternativet, men det kommer inte att fungera eftersom det är så många kit/sekvenser och olika maskintyper. Plockningen går så snabbt att det inte finns utrymme för att leta efter listor vid varje start tyvärr.

Skickades från m.sweclockers.com