Jak stworzyć zoptymalizowaną listę marszów, biorąc pod uwagę współrzędne długości i szerokości geograficznej?

Pracuję nad kampanią polityczną, w której dziesiątki wolontariuszy będą prowadzić promocje pukania do drzwi w ciągu najbliższych tygodni. Biorąc pod uwagę listę z nazwami, adresami i długimi / prostymi współrzędnymi, jakich algorytmów można użyć do stworzenia zoptymalizowanej listy ścieżek.

Jak powiedział Steve Kallestad, jest to problem z TSP, a istnieją cudowne bezpłatne rozwiązania pozwalające znaleźć przybliżone rozwiązania.

To może być zbyt dużo pracy dla tego, czego szukasz, ale możesz spróbować użyć jednego z tych solverów w połączeniu z interfejsem API Map Google, aby znaleźć rzeczywiste odległości spaceru między współrzędnymi: https://developers.google.com/maps / dokumentacja / wskazówki / # DirectionsRequests

(Nigdy nie korzystałem z tego interfejsu API, więc nie wiem, jak łatwy i skuteczny byłby)

Ludzie widzą coś ściśle związanego z Problemem Podróżującego Sprzedawcy i myślą, że nie można go rozwiązać.

Dużo pracy wykonano na ten temat i nie wszystko wskazuje na to, że rozwiązanie nie jest dostępne. W zależności od parametrów i pożądanego rozwiązania możesz znaleźć coś, co zadziała.

Możesz rzucić okiem na bibliotekę Pythona OpenOpt .

Innym zasobem do obejrzenia jest TPS Solver and Generator .

Jeśli używasz R, dostępny jest pakiet TSP .

W rzeczywistości wdrożenie rozwiązania twojego problemu to trochę za dużo do omówienia, ale powinno to stanowić dobry punkt wyjścia. W tych pakietach oraz w dokumentacji w linkach, które dla ciebie podałem, przekonasz się, że istnieje dość szeroki wybór strategii algorytmicznych. Masz mały region geograficzny i niewielki zestaw „sprzedawców”, więc moc obliczeniowa potrzebna do obliczenia strategii w rozsądnych ramach czasowych powinna być dostępna na pulpicie.

W praktyce nie musisz znajdować najbardziej optymalnej strategii. Potrzebujesz tylko bardzo dobrego. Wybierz pakiet TSP, który wygląda najmniej przytłaczająco, i wypróbuj go.

Jak zauważył @SpacedMan w komentarzu , układ ulic będzie miał ogromny wpływ na optymalizację listy spacerów. W tytule pytania podałeś tylko „szerokość i długość geograficzną”; ale rozwiązanie tego problemu nie prowadzi do „listy pieszych”, ale do „listy w linii prostej”.

Spojrzenie na układ ulicy jako wykres z wagami krawędzi opisującymi odległości i próba znalezienia najkrótszego przejścia między wszystkimi wymaganymi adresami, sprawi, że będziesz postrzegał swój problem jako „ problem najkrótszej ścieżki ”. Algorytm Dijkstry jest najbardziej znanym rozwiązaniem (istnieją inne); w swojej naiwnej implementacji zbiega się w O (n ² ) , co może być do przyjęcia, jeśli listy adresów są umiarkowane. W przeciwnym razie poszukaj zoptymalizowanych wersji w powyższych linkach.

Jeśli chodzi o biblioteki i zasoby, aby zacząć rozwiązywać ten problem, ponieważ nie określasz języków ani platform, pozwól mi wskazać na kompilację solverów routingu na wiki Open Street Maps i ogólnie na ich stronie frameworków i bibliotek .

Oto szalony pomysł: porozmawiaj z wolontariuszami, którzy znają dzielnice i którzy wcześniej pracowali od drzwi do drzwi. Uzyskaj porady i pomysły. Prawdopodobnie będą mieli spostrzeżenia, których nie wygeneruje żaden algorytm, a modyfikacje te będą cenne dla każdej wygenerowanej komputerowo listy tras. Jeden przykład: unikanie przechodzenia przez bardzo uczęszczane ulice przy wolnym świetle lub bez świateł. Kolejny przykład: pary wolontariuszy pracujących po przeciwnych stronach tej samej ulicy poczują się bezpieczniej niż wolontariusz pracujący na tej samej ulicy.