Optymalizacja trasy

Wszystkie narzędzia, wtyczki, programy itp. pomocne przy znajdowaniu skrzynek i dbaniu o lasy...

Moderator: Moderatorzy

Awatar użytkownika
taiffun
Bywalec
Posty: 57
Rejestracja: poniedziałek 25 października 2010, 23:41
Podziękował;: 1 raz
Otrzymał podziękowań: 2 razy

Optymalizacja trasy

Post autor: taiffun »

Witam!
Do zobrazowania problemu posłużę się konkretną geościeżką z rozrzuconymi skrzynkami.
Sam problem brzmi natomiast: jak najoptymalniej ułożyć trasę, żeby jeżdżąc nie nabijać zbyt wielu kilometrów? Czyli klasyczny problem komiwojażera, do tego trzeba dołożyć jeszcze punkt lub kierunek z którego nadjeżdzamy i w którym wracamy. Dodam, że problematykę optymalizacji i heurystyki znajdowania rozwiązań znam (i wiem że nie bywa jest prosta ;) ) - pytam bardziej o konkretne narzędzia - możliwie niedrogie - które mogłyby mi pomóc ułożyć optymalną trasę. Macie jakieś sprawdzone patenty na takie sytuacje?
Awatar użytkownika
Lza
Rada Techniczna
Posty: 1621
Rejestracja: poniedziałek 19 października 2009, 10:01
Podziękował;: 24 razy
Otrzymał podziękowań: 81 razy

Re: Optymalizacja trasy

Post autor: Lza »

większość nawigacji samochodowych (np. automapa) posiada funkcję układania trasy z wieloma punktami pośrednimi tak, aby zminimalizować dystans. Można podać haotycznie poukładane punkty i tylko zaznaczyć który jest pierwszy a który ostatni, resztę zrobi algorytm.

W sumie dosyć ciekawe zagadnienie matematyczne/informatyczne samo w sobie dla zaawansowanych. Można pomyśleć o implementacji gotowych rozwiązań google: https://developers.google.com/maps/docu ... irections/ kto wie, może by się i przydało takie narzędzie w OC :-)

Edit: optymalizacja trasy jest dostępna:
By default, the Directions service calculates a route through the provided waypoints in their given order. Optionally, you may pass optimize:true as the first argument within the waypoints parameter to allow the Directions service to optimize the provided route by rearranging the waypoints in a more efficient order.
Awatar użytkownika
taiffun
Bywalec
Posty: 57
Rejestracja: poniedziałek 25 października 2010, 23:41
Podziękował;: 1 raz
Otrzymał podziękowań: 2 razy

Re: Optymalizacja trasy

Post autor: taiffun »

No właśnie mam zerowe doświadczenie z nawigacjami samochodowymi, więc szukałem jakiegoś oprogramowania do tego.
Co do google maps - jeśli mają taką opcję, to nie wiem jak z niej skorzystać, domyślnie jest określona kolejność i brak jakby opcji optymalizowania. Trzeba by kodzić coś własnego, tak?
Przed chwilą wykopałem idąc tym tropem http://www.gebweb.net/optimap/ i nawet daje radę.
Awatar użytkownika
Karls
Forumator
Posty: 620
Rejestracja: czwartek 15 września 2011, 20:58
Podziękował;: 0
Otrzymał podziękowań: 7 razy

Re: Optymalizacja trasy

Post autor: Karls »

W wypadku keszy takie coś ma sens tylko jeśli skrzynki leżą przy dobrze wyznaczonych drogach. Ja wolę jednak jechać na wyczucie bo już nie raz się zdarzało, że chociaż mapa twierdziła co innego to po drodze wypadał płot czy inna przeszkoda terenowa. Wtedy taka na sztywno zaplanowana trasa będzie często automatycznie do wyrzucenia. Bywa też w drugą stronę - po przebijaniu się ciężką trasą do skrzynki nagle okazuje się, że z drugiej strony jest dużo wygodniejsza ścieżka. Inna sprawa, że nigdy nie robiłem w serii więcej niż około 20 skrzynek a wtedy i tak to było w większości pieszo więc to inna sytuacja. Chociaż dla mnie pieszo a rower dużej różnicy nie robi :)
ObrazekObrazekObrazek
maks1823
Bywalec
Posty: 47
Rejestracja: środa 04 grudnia 2013, 16:08
Podziękował;: 4 razy
Otrzymał podziękowań: 1 raz

Re: Optymalizacja trasy

Post autor: maks1823 »

Cóż, ja używam do OC PL (a właściwie używałem) OC Planera by futrzak.Sprawdza(ł) się bardzo dobrze.POLECAM :D
Obrazek Obrazek Obrazek
Awatar użytkownika
Silent A
Wyjadacz
Posty: 467
Rejestracja: poniedziałek 07 listopada 2011, 09:19
Podziękował;: 0
Otrzymał podziękowań: 18 razy

Re: Optymalizacja trasy

Post autor: Silent A »

Wszelkie algorytmy matematyczne nadają się tylko i wyłącznie do driveinów przy drogach asfaltowych. Trasę do skrzynek poza asfaltem trzeba już wyznaczać samodzielnie bazując na minimum kilku mapach uwzględniając drogi, dróżki, ścieżki, pola, lasy, rowy, rzeki, bagna, płoty, parkingi, stromizny i wiele wiele innych zmiennych, częśc nieznanych w tym np kierunki w którym idą multaki. Żaden algorytm tego nie ogarnie a nawet jeśli to samo przygotowanie tych wszystkich danych do algorytmu trwało by dłużej niż przejście tych wszystkich skrzynek byle jaką drogą.
Odpowiedni dobór drogi pomiędzy skrzynkami to jedna z trudniejszych spraw przy szukaniu i nie ma się co oszukiwać - raz się uda a raz się nie uda dobrać optymalnej drogi, mówi się trudno. Ja staram się przygotowywać jakąś trasę bo zawsze lepiej jest rozpoznać teren przed komputerem mając do dyspozycji kilka map niż walczyć w terenie i miotać się na lewo i prawo aby na końcu trafić na rzekę ;-)
Obrazek
ODPOWIEDZ