Opencaching Polska - Forum

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?

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.

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ę.

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

Cóż, ja używam do OC PL (a właściwie używałem) OC Planera by futrzak.Sprawdza(ł) się bardzo dobrze.POLECAM

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ę