PL 
EnglishDomyślny
Українська🚚 Optymalizator tras dostaw — symulowane wyżarzanie na żywo
Obserwuj, jak symulowane wyżarzanie hartuje trasy floty dostawczej na mapie miasta, uciekając z minimów lokalnych za pomocą kontrolowanych losowych skoków, gdy całkowita odległość spada ku optimum.
O tej symulacji
Trasowanie dostaw to jeden z najstarszych trudnych problemów badań operacyjnych: mając magazyn i zbiór przystanków, znajdź najkrótszą zamkniętą trasę odwiedzającą każdy przystanek dokładnie raz — problem komiwojażera. Ta symulacja implementuje prawdziwy optymalizator symulowanego wyżarzania dla tego problemu. Prawdziwe sąsiedztwo 2-opt (odwrócenie segmentu), prawdziwy geometryczny harmonogram chłodzenia i prawdziwa reguła akceptacji Metropolisa działają nieprzerwanie w przeglądarce, a ty obserwujesz, jak bieżąca trasa i najlepsza dotąd trasa są rysowane na żywo na mapie miasta, gdy całkowita odległość spada.
🔬 Co pokazuje
Każda klatka animacji proponuje kilka losowych ruchów 2-opt: wybierane są dwie pozycje w trasie, a segment między nimi jest odwracany, co jest równoważne zamianie dwóch krawędzi na dwie inne. Dokładna zmiana długości trasy (Δ) jest obliczana tylko z czterech dotkniętych długości krawędzi. Jeśli Δ < 0, ruch jest zawsze zachowywany; w przeciwnym razie jest akceptowany z prawdopodobieństwem e^(−Δ/T). Temperatura T maleje przy każdej iteracji jako T ← α·T, więc na początku trasa skacze i czasem nawet się wydłuża, a później osiada w gładkiej, monotonicznej poprawie.
🎮 Jak korzystać
Przeciągnij suwak przystanków dostaw (8–40) lub kliknij „Nowa losowa mapa”, aby wygenerować świeży układ miasta. Współczynnik chłodzenia α kontroluje, jak powoli spada temperatura — wartości bliskie 0,9999 eksplorują znacznie więcej, zanim zaangażują się w dopracowanie, wartości bliskie 0,985 zachowują się niemal jak czyste zachłanne 2-opt. Temperatura początkowa ustala, jak agresywnie akceptowane są wczesne ruchy. Kroki na klatkę kontrolują szybkość odtwarzania. Restart tasuje trasę i resetuje harmonogram na tej samej mapie; Pauza zamraża wyżarzanie, byś mógł zbadać bieżący stan.
💡 Czy wiesz, że?
Symulowane wyżarzanie bierze swoją nazwę — i regułę akceptacji — bezpośrednio z metalurgii: podgrzanie metalu i powolne jego chłodzenie pozwala jego atomom znaleźć niskoenergetyczną, wolną od defektów sieć krystaliczną, podczas gdy zbyt szybkie chłodzenie „zamraża” nieuporządkowaną, wyższej energii strukturę. Kirkpatrick, Gelatt i Vecchi zastosowali dokładnie tę fizyczną analogię do optymalizacji kombinatorycznej w 1983 roku, a optymalizacja tras — problem komiwojażera — była jednym z ich pierwotnych przypadków testowych.
Najczęściej zadawane pytania
Czym jest symulowane wyżarzanie i dlaczego stosuje się je do optymalizacji tras?
Symulowane wyżarzanie to probabilistyczna technika optymalizacji inspirowana metalurgicznym procesem podgrzewania metalu i powolnego chłodzenia go, tak by jego atomy osiadły w niskoenergetycznej strukturze krystalicznej. Zastosowane do problemu komiwojażera / trasowania pojazdów, „energią” jest całkowita odległość trasy. Przy wysokiej temperaturze algorytm akceptuje wiele pogarszających ruchów, pozwalając mu szeroko eksplorować i wyskakiwać ze słabych lokalnych układów; gdy temperatura spada, staje się coraz bardziej zachłanny, dopracowując trasę, aż zbiegnie w pobliże krótkiej trasy. Jest popularne w trasowaniu, ponieważ przestrzeń przeszukiwania możliwych kolejności przystanków ma rozmiar silniowy, zbyt duży, by przeszukać wyczerpująco, a jednak sąsiedztwa 2-opt połączone z wyżarzaniem niezawodnie znajdują trasy w granicach kilku procent od optimum.
Czym jest ruch 2-opt i dlaczego odwraca się segment?
Ruch 2-opt usuwa dwie krawędzie z trasy i ponownie łączy cztery końce w jedyny inny sposób, który utrzymuje pojedynczą zamkniętą pętlę, co jest równoważne odwróceniu kolejności przystanków między dwoma punktami cięcia. To najprostszy ruch przeszukiwania lokalnego, który może rozplątać trasę: gdy dwa segmenty trasy krzyżują się na mapie, dokładnie jeden ruch 2-opt je prostuje i skraca całkowitą odległość. Ponieważ zmieniają się tylko dwie krawędzie, zmianę długości trasy (deltę) można obliczyć, porównując tylko te dwie stare i dwie nowe długości krawędzi, bez ponownego sumowania całej trasy.
Czym jest kryterium akceptacji Metropolisa?
Po obliczeniu delty kosztu kandydującego ruchu algorytm zawsze akceptuje ruchy, które skracają trasę (Δ < 0). Dla ruchów, które ją wydłużają, akceptuje z prawdopodobieństwem e^(−Δ/T), gdzie T to bieżąca temperatura. Oznacza to, że duży pogarszający ruch jest rzadko akceptowany, ale małe pogarszające ruchy są wciąż dość prawdopodobne na początku, gdy T jest wysokie. Gdy T maleje ku zeru, e^(−Δ/T) zapada się ku zeru dla dowolnego dodatniego Δ, więc algorytm efektywnie staje się czystym zachłannym zejściem — wspinaczka jest zabroniona i przetrwają tylko poprawiające ruchy.
Jak harmonogram chłodzenia wpływa na wynik?
Ta symulacja używa chłodzenia geometrycznego: T jest mnożone przez współczynnik chłodzenia α (bliski, ale poniżej 1) po każdym proponowanym ruchu, więc T maleje wykładniczo wraz z liczbą iteracji. Współczynnik chłodzenia bardzo bliski 1 (np. 0,9995) chłodzi powoli, dając przeszukiwaniu wiele iteracji przy wyższych temperaturach, by szeroko eksplorować, zanim zaangażuje się w dopracowanie rozwiązania — zwykle znajduje krótsze trasy, ale dłużej się ustala. Niższy współczynnik chłodzenia (np. 0,985) chłodzi szybko i zachowuje się niemal jak zachłanne przeszukiwanie lokalne 2-opt, zbiegając szybko, ale bardziej prawdopodobnie utykając w przeciętnym minimum lokalnym.
Dlaczego długość trasy czasem się pogarsza, zanim się poprawi?
To cały sens wyżarzania: przy wysokiej temperaturze kryterium Metropolisa celowo akceptuje niektóre ruchy zwiększające długość. Trasa może wyglądać na lokalnie optymalną (żaden pojedynczy ruch 2-opt jej nie poprawia), będąc wciąż daleką od najkrótszej możliwej trasy — to jest minimum lokalne. Okazjonalnie akceptując gorszy ruch, przeszukiwanie może wyjść z basenu tego minimum lokalnego i później wpaść w inne, krótsze. Obserwując wykres odległości, zwykle zobaczysz, że najpierw szybko spada, okazjonalnie skacze w górę, gdy T jest jeszcze wysokie, a następnie osiada w gładkim, monotonicznym spadku, gdy T zbliża się do zera.
Jak ma się to do rzeczywistego planowania tras dostaw?
Prawdziwe firmy logistyczne rozwiązują problemy trasowania pojazdów (VRP) z setkami lub tysiącami przystanków, wieloma pojazdami, oknami czasowymi i limitami pojemności — problem kombinatoryczny NP-trudny, gdzie dokładne rozwiązania są obliczeniowo niewykonalne powyżej kilkudziesięciu przystanków. Metaheurystyki, takie jak symulowane wyżarzanie, wraz z algorytmami genetycznymi, optymalizacją mrowiskową i przeszukiwaniem tabu, są standardowymi narzędziami branżowymi do znajdowania bardzo dobrych (choć niekoniecznie dowiedzionych jako optymalne) tras w sekundy do minut. Ta symulacja modeluje rdzeń pojedynczego pojazdu tego problemu — klasyczny problem komiwojażera — który jest tym samym silnikiem kombinatorycznym w sercu produkcyjnego oprogramowania trasowania.