Algorytm trasy dla ok 250 obiektów

Cześć, stoję przed zadaniem zdefiniowania no i implementacji algorytmu, który wyszukałby możliwie najlepszą trasę dla 250 obiektów.
Oczywiście powyższy problem to problem komiwojażera.

Ogólnie rzecz biorąc moim zadaniem jest znalezienie takiej trasy, aby w jeden dzień odwiedzić jak największą ilość wrocławskich krasnali. Jest ich koło UWAGA 300. Ich ilość chciałbym zmniejszyć do około 250.

Zakładając punkt startowy (jakiś tam krasnal) chcę obliczyć możliwie najlepsza trasę (zabierającą najmniej czasu).
Jaki algorytm byście polecili? Może jakieś wskazówki co do samej implementacji, jak rozwiązać właśnie powyższy problem czasowy?

Dzięki!

To co chcesz osiągnąć jest zdefiniowane pod hasłem "selective travelling salesman problem". W skrócie polega to na tym, że musisz wyznaczyć granicę kosztów. Możesz dolną i górną. Kosztem jest czas przejścia z punktu A do punktu B. Granicą górną jest np. 12h, a granicą dolną dla liczby ruchów to 250.

Założyłem przy tym, że osiągnięcie 300 krasnali na dobę jest nieosiągalne i poszukujesz rozwiązania problemu, aby znaleźć część informacji spośród zbioru, najlepiej spełniającą kryteria.

Ale chcesz jakis "własny" pomysł? Może np. klastrowanie krasnali w grupy oddalone o nie więcej niż X (jakimś dbscanem na przykład) a potem wyznaczenie trasy między klastrami plus wyznaczenie tras między punktami w klastrach. W ten sposób rozmiar problemu spada drastycznie, przynajmniej dla jakiegoś średniego przypadku.

Czy ktoś mógłby troszeczkę obrazowo wytłumaczyć, jak powinienem użyć algorytmu mrówkowego? Z programowania czuje sie spoko, ale z algorytmów.. no po prostu muszę to widzieć :/

Zdecydowalem sie uzyc algorytmu wyzarzania. Napotkalem jednak problem. Algorytm jest w zasadzie raczej dobrze napisany bo pisalem go z pomoca innego kodu, natomiast z tego co widze algorytm nie potrafi znalezc mi rozwiazania lepszego niz najblizszy sasiad..

Czym to moze byc spowodowane? Mimo ze licze to po pare razy to wyzarzania nie zwraca lepszego wyniku, natomiast najblizszy sasiad (co nic dziwnego bo przeciez caly czas ma ta sama trase) zwraca ta sama wartosc, ktora jest zawsze nizsza od wyzarzania..

obiektow mam 130 w bazie aktualnie. Robie z nich macierz 130 x 130 i nastepnie na jej podstawie jest liczona dlugosc trasy.

Gdzie moze lezec problem?