W ostatnim czasie zainteresował mnie temat map Google i tworzenie programów z tym związanych. Pomyślałem aby zrobić swoją aplikację do której będę mógł wkleić w losowy sposób adresy miejscowości, a program sam ułoży je w odpowiedniej kolejności i pokaże optymalną trasę przejazdu z przypisanego wcześniej punktu startowego i powrotem do niego. Pojęcie to nazywane jest "Problemem komiwojażera".

Program zacząłem pisać w C# wykorzystując bibliotekę GMap. Liczbę możliwych do wpisania miast ograniczyłem na ten moment do 40, ponieważ w przypadku źle wykonanej pętli bałem się wykorzystania wszystkich środków na koncie. Wynika to z tego, że aby móc pisać programy oparte o mapy Google trzeba podpiąć do nich kartę płatniczą.

W przypadku pierwszej wersji programu poszedłem na łatwiznę. Po wpisaniu różnych adresów obliczam odległość od punktu startowego, do każdego z nich. W ten sposób ustaliłem kolejność od najmniejszej odległości do największej i w takiej kolejności wyznaczyłem trasę.

Nie wyszło to najgorzej, o dziwo w sporej liczbie przypadków trasa jest bardzo dobra, jak w przypadku poniżej. Można również wpisywać nazwy firm zamiast adresu i Google również je rozpoznaje na mapie. Niebieskim kolorem wyznaczyłem trasę powrotną do punktu startowego, w moim przypadku będzie to Zamek w Melsztynie.
dobrze wyznaczona trasa

Problem pojawia się wtedy, kiedy bardziej rozrzucimy nasze adresy. W podanym niżej przypadku program pokierował najpierw do Ciężkowic, które uznał, że są najbliżej, następnie do Tarnowa, a potem tą samą drogą kazał wracać do Tuchowa, pomimo że już przez niego przejeżdżaliśmy. Według mnie najpierw powinniśmy jechać do Tarnowa, potem do Tuchowa (lub odwrotnie najpierw Tuchów, potem Tarnów), następnie do Jasła i na powrocie odwiedzić Ciężkowice.
źle wyznaczona trasa

Kolejna wersja programu próbująca rozwiązać ten problem pojawi się w kolejnym artykule.