Rozwiązywanie wielobazowego zamkniętego problemu wielokrotnego komiwojażera za pomocą hierarchicznego grupowania k-means++ i sieci kombinatorycznych

Sprytniejsze trasy dla wielu kierowców

Od furgonetek kurierskich po drony dostawcze i konwoje pomocowe — planujący często stają przed zagadką: jak kilka pojazdów startujących z różnych baz może wspólnie odwiedzić setki lub tysiące punktów, nie marnując paliwa ani czasu? Artykuł przedstawia nowy sposób podziału i zwyciężania nad tym problemem, łącząc klasyczny trik grupowania z nowoczesną siecią neuronową, dzięki czemu komputery mogą opracowywać efektywne trasy w ciągu sekund zamiast minut czy godzin.

Wyzwanie wielu baz i wielu kierowców

Badanie podejmuje wymagającą wersję słynnego problemu komiwojażera, w której zamiast jednego podróżnika jest wielu, z których każdy zaczyna i kończy w swojej bazie. Razem muszą odwiedzić każde miasto dokładnie raz, minimalizując łączny dystans. Taka konfiguracja odzwierciedla zadania, takie jak koordynacja flot ciężarówek, zespołów robotów czy dronów operujących na wspólnym obszarze. Ponieważ liczba możliwych kombinacji tras eksploduje wraz ze wzrostem liczby miast i kierowców, metody dokładne stają się zbyt wolne, a tradycyjne wyszukiwania często mają trudności lub muszą poświęcić jakość rozwiązania dla szybkości.

Granice klasycznych przeszukiwań i prostego dzielenia

Przez lata inżynierowie polegali na „metaherystykach” takich jak algorytmy genetyczne, kolonii mrówek czy roje cząstek. Naśladują one procesy naturalne, aby przeszukiwać wiele kandydatów na trasy i stopniowo je ulepszać. Są elastyczne, ale mają dwie poważne wady: nie dają twardych gwarancji co do jakości rozwiązania i mogą być bardzo wolne dla dużych map, zwłaszcza gdy dla każdego nowego zadania trzeba zaczynać przeszukiwanie od nowa. Popularnym przyspieszeniem jest najpierw pogrupowanie miast w regiony za pomocą narzędzi takich jak k-means, a następnie rozwiązanie mniejszych podproblemów w każdej grupie. Choć strategia dziel-i-rozwiaz pomaga, ostateczna jakość nadal zależy od użytej metody przeszukiwania, a dążenie do lepszych tras zwykle wiąże się z dłuższym czasem działania.

Nauczenie sieci trasowania, a potem pomoc w skalowaniu

Ostatnie lata przyniosły inny pomysł: wytrenować sieć neuronową, aby bezpośrednio generowała dobre trasy. Po nauczeniu się na wielu przykładach rozkładów miast taka sieć może zaproponować pełną trasę w jednym przejściu w przód, podobnie jak model językowy tworzy zdanie. Te neuronowe solvery działają imponująco dobrze w problemach z jednym kierowcą i umiarkowanym rozmiarem, lecz słabną, gdy trzeba koordynować wielu kierowców lub gdy zestaw miast jest znacznie większy niż podczas treningu. Kluczowym posunięciem autorów jest umieszczenie takiego neuronowego solvera w starannym dwufazowym procesie, który przekształca ogromne, wielokierowcowe zadanie w wiele mniejszych, znanych podproblemów, które sieć potrafi wygodnie obsłużyć.

Jak działa metoda dwufazowa

Proponowana metoda, nazwana KHC-NCN, zaczyna od użycia ulepszonej wersji grupowania k-means do przypisania miast do poszczególnych baz i kierowców. Jeśli powstały region zawiera zbyt wiele miast, by sieć neuronowa mogła je niezawodnie obsłużyć, metoda automatycznie dzieli ten region na mniejsze części, zbliżone rozmiarem do tych, które widziano podczas treningu. Współrzędne w każdej części są przeskalowywane do standardowego kwadratu, aby jeszcze bardziej przypominały dane treningowe. Następnie sieć neuronowa generuje trasę dla każdej małej części. Na koniec krok łączenia zszywa te podtrasy w jedną pętlę dla każdego kierowcy, stosując proste reguły geometryczne do łączenia fragmentów tam, gdzie dodane odległości są jak najmniejsze.

Szybkość i jakość na rzeczywistych mapach benchmarkowych

Autorzy testują swoją metodę na szerokiej kolekcji standardowych map z publicznego zestawu benchmarkowego powszechnie stosowanego w badaniach nad trasowaniem. Porównują ją z wieloma ugruntowanymi technikami przeszukiwania oraz zarówno z najlepszym ręcznie opracowanym solverem, jak i innym podejściem neuronowym. W 44 przypadkach testowych o różnej wielkości map i liczbie kierowców ich metoda znajduje krótsze łączne trasy w prawie trzech czwartych przypadków, będąc przy tym dramatycznie szybsza, często o rzędy wielkości. Metoda sprawdza się szczególnie dobrze, gdy liczba miast rośnie do setek lub tysięcy, gdzie wiele klasycznych podejść zwalnia lub daje gorsze wyniki.

Co to znaczy dla trasowania w praktyce

W prostych słowach badanie pokazuje, że pozwalanie szybkiej sieci neuronowej zajmować się wieloma małymi, dobrze ukształtowanymi podzadaniami może przewyższyć poświęcanie dużo czasu na jeden ogromny problem. Poprzez grupowanie miast w sposób respektujący strefę komfortu sieci, a następnie sprytne łączenie częściowych odpowiedzi, metoda dostarcza trasy zarówno krótkie, jak i szybkie do obliczenia. Dla zastosowań takich jak logistyka, planowanie zespołów robotów czy reagowanie kryzysowe wskazuje to praktyczny sposób uzyskania planów tras niemal w czasie rzeczywistym, które lepiej wykorzystują pojazdy i energię niż wiele istniejących narzędzi.

Cytowanie: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Słowa kluczowe: trasowanie pojazdów, sieci neuronowe, grupowanie, optymalizacja, logistyka