Oprogramowanie do planowania najkrótszej trasy do wielu adresów [zamknięte]

8

Mam w mieście około 300 adresów i próbuję znaleźć oprogramowanie, które może rozwiązać problem sprzedawcy w podróży. Wypróbowałem OptiMap rozwiązanie oparte na przeglądarce, które korzysta z Google API, ale jest ograniczone do 100 miejsc docelowych (nawet po zmianie limitów zakodowanych na stałe), a przeglądarkom próbuję w końcu zabraknąć pamięci. Wiem, że problem jest trudny, ale nie jest to nowy problem, na pewno ktoś już napisał oprogramowanie. Jedyne komercyjne rozwiązania, które widziałem, dotyczą wyłącznie USA (to miasto w Australii) lub mają niskie limity.

Czy istnieje wolne lub komercyjne oprogramowanie do wykonania tego zadania i jego rozmiar?

software-rec calculator użytkownik348998
źródło
2
Być może możesz rozwiązać problem w kawałkach po 100. Czy możesz rozbić lokalizacje na klastry i podać je do OptiMap we fragmentach. Czy obsługiwać przejścia ręcznie?
uSlackr
Zawsze widziałem problem sprzedawcy podróżującego jako przykład, coś w rodzaju foobarbaz hello world. Zabawnie jest widzieć, że ma tak praktyczny potencjał. Nawiasem mówiąc, NP trudne lub nie, algorytmy genetyczne zapewnią doskonałe (nie idealne) rozwiązanie w kilka minut lub krócej. Ponadto 300 adresów? To wygląda na rodzaj sytuacji WTF, której deweloperzy OptiMap nie uwzględnili. Złożyć błąd?
Camilo Martin
Wyszukaj za pomocą tych słów kluczowych: optymalizacja dostarczania oprogramowania logistycznego. Istnieje wiele programów dedykowanych dla tego rodzaju problemów. duckduckgo.com/…
climenole

Odpowiedzi:

1

Niezupełnie „darmowy” - ale być może zaimplementować algorytm aproksymacji dla TSP opisany w tym podręczniku .

IIRC, daje rozwiązanie TSP dla grafów płaskich współczynnik 2 w ramach optymalnego rozwiązania.

emptyset
źródło
1
Haha, +1 za odpowiedź „napisz ten algorytm”
Fopedush
Myślę, że to zabawne, gdy ludzie myślą, że znajdą stronę internetową z niestandardowym oprogramowaniem napisanym w celu rozwiązania określonego scenariusza.
emptyset