Route/Locaties berekenen.

[Verwijderd]

Ik bezig met een klein hobby projectje ;-)

Bij ons in het magazijn worden routes berekend op basis van tekst.
Als voorbeeld: product-1 ligt op A-10-3-21
A staat voor stelling
10 voor rij(in de stelling)
3 staat voor de laag van de rij.
21 staat voor het bakje in deze laag

Wat ik nu probeer te maken, is een route door ons magazijn te tekenen op basis van een lijst producten.
Ik heb al een simpel begin gemaakt in javascript met "canvas", wat goed werkt.

Alleen het berekenen van de posities is lastiger dan ik dacht.
Ik weet namelijk niet welke bestellingen ik binnen krijg, en hoe ik dan de meest logische route kan berekenen/tekenen om deze producten te verzamelen.

Verder heb ik al zitten googlen, maar kom niet erg op een antwoord wat ik zoek ;-)

Weet iemand hier informatie over, hoe je dit het beste kan berekenen met je eigen plattegrond?


In deze afbeelding tekening ik alleen de rode lijn met canvas, de kruisjes staan voor producten die opgehaald moeten worden.

Alvast bedankt

[ Voor 3% gewijzigd door Verwijderd op 05-01-2015 08:52 ]

[Verwijderd]

Zet de plattegrond om naar een graaf met routes en hoe duur die routes zijn. Vervolgens is het een "simpel" Traveling Salesman Problem. En daar is heel veel over te lezen.

[Verwijderd]

Bedankt voor de snelle reactie

Met grafentheorie kom ik al een aardig in de richting met wat ik hebben wil.

Met wat verder onderzoek heb ik het volgende gevonden, wat ik momenteel aan het onderzoeken ben.
http://js.cytoscape.org/

Nu de uitdagen aangaan en hopen dat ik het voor elkaar krijg

[Cypher87]

Of kijk eens naar http://en.wikipedia.org/wiki/A*_search_algorithm zijn genoeg implementaties van te vinden

[MSalters]

A* is point-to-point, niet om een lijst van punten langs te lopen.

[Caelorum]

Maar als je het startpunt weet best goed te gebruiken. Wellicht dat je bijv altijd bij het artikel het dichts bij de printer waar de orders uitkomen wilt beginnen of zoiets.

[aaitje]

Ik heb wel eens gelezen dat iemand precies zoiets gemaakt had. Na het bouwen van de software deed hij een test hoeveel sneller het picken zou gaan.

Resultaat was dat het berekenen van de optimale route zo lang duurde dat het uiteindelijk sneller was om het op gevoel te doen...

Eea hangt natuurlijk af van de snelheid van je hardware en omvang magazijn en ik wil je niet ontmoedigen

Zou je niet een begin kunnen maken door de picklijst simpelweg te sorteren op rij, laag, bakje. Dan heb je waarschijnlijk al een vrij optimale route?

[roy-t]

De beste route vinden langs meerdere punten is een erg ingewikkeld probleem om efficient op te lossen (Traveling Salesman is NP-Hard). Er zijn gewoon snel al te veel mogelijkheden. Ik hoop dus dat je een sub-optimale oplossing kunt vinden die wel snel uit te rekenen is

[Woy]

aaitje schreef op dinsdag 06 januari 2015 @ 22:23:
Ik heb wel eens gelezen dat iemand precies zoiets gemaakt had. Na het bouwen van de software deed hij een test hoeveel sneller het picken zou gaan.

Resultaat was dat het berekenen van de optimale route zo lang duurde dat het uiteindelijk sneller was om het op gevoel te doen...

Eea hangt natuurlijk af van de snelheid van je hardware en omvang magazijn en ik wil je niet ontmoedigen

Zou je niet een begin kunnen maken door de picklijst simpelweg te sorteren op rij, laag, bakje. Dan heb je waarschijnlijk al een vrij optimale route?

Daarom wil je dit soort dingen vaak met een heuristiek oplossen. Niet perse de allerbeste oplossing, maar wel een goede oplosssing.

[Soultaker]

roy-t schreef op woensdag 07 januari 2015 @ 11:15:
De beste route vinden langs meerdere punten is een erg ingewikkeld probleem om efficient op te lossen (Traveling Salesman is NP-Hard). Er zijn gewoon snel al te veel mogelijkheden. Ik hoop dus dat je een sub-optimale oplossing kunt vinden die wel snel uit te rekenen is

In de praktijk zijn instances met meer dan 10.000 punten gewoon exact op te lossen. Als het warenhuis van TS niet al te groot is, hoeft het vinden van een exacte oplossing dus geen probleem te zijn. Sowieso lijkt me dat je het probleem kunt beperken tot het vinden van een route tussen de kasten. Je gaat natuurlijk nooit tussen twee kasten heen en weer lopen als je uit meerdere bakjes in dezelfde kast iets nodig hebt.

Het lijkt me ook niet dat je meer dan (zeg) 100 items kunt pakken in een enkele trip, dus dat beperkt de complexiteit ook aardig. Aan de andere kant maakt dat het probleem wel weer lastiger: als je meerdere trips moet maken, hoe moet je de lijst bestellingen dan weer opsplitsen om ze het efficiëntst te kunnen ophalen? We missen de nodige informatie om daar wat zinnigs over te zeggen.

[ Voor 22% gewijzigd door Soultaker op 07-01-2015 12:45 ]

[farlane]

Soultaker schreef op woensdag 07 januari 2015 @ 12:40:
Je gaat natuurlijk nooit tussen twee kasten heen en weer lopen als je uit meerdere bakjes in dezelfde kast iets nodig hebt.

Tenzij de kasten 50m lang zijn, 1m uit elkaar staan en je uit elke kast het begin en eind wat moet hebben

[Soultaker]

Hm, dan misschien wel ja.

[Caelorum]

Ach zelfs dan nog. Een optimale route is leuk, maar eigenlijk is algoritme die gemiddeld 10% tijd bespaart ook al mooi meegenomen natuurlijk.