Löser multi-depot slutna-slinga flera-resande-säljare-problemet med k-means++ hierarkisk klustring och neurala kombinatoriska nätverk

Smartare rutter för många förare

Från paketbilar till leveransdronor och konvojer för katastrofhjälp ställs planerare ofta inför ett pussel: hur kan flera fordon som startar från olika platser dela arbetet med att besöka hundratals eller tusentals stopp utan att slösa bränsle eller tid? Denna artikel presenterar ett nytt sätt att dela upp och erövra det pusslet, genom att kombinera en klassisk klustringsteknik med ett modernt neuralt nätverk så att datorer kan rita upp effektiva rutter på sekunder istället för minuter eller timmar.

Utmaningen med många depåer och många förare

Studien tar sig an en krävande variant av det välkända handelsresandeproblemet, där det i stället för en resenär finns många, var och en som startar och slutar vid sin egen bas. Tillsammans måste de besöka varje stad exakt en gång samtidigt som den totala sträckan hålls så kort som möjligt. Denna konfiguration speglar uppgifter som samordning av lastbilsflottor, grupper av robotar eller luftburna drönare som delar arbete över ett område. Eftersom antalet möjliga ruttkombinationer exploderar när städer och förare ökar blir exakta metoder för långsamma, och traditionella sökmetoder baserade på prövning och förbättring kämpar ofta eller tvingas byta bort lösningskvalitet mot fart.

Begränsningar hos klassisk sökning och enkel uppdelning

I åratal har ingenjörer förlitat sig på ”metaheuristiker” som genetiska algoritmer, myrkolonisökning och partikel-svärmar. Dessa efterliknar naturliga processer för att utforska många kandidatutturer och gradvis förbättra dem. De kan vara flexibla men har två stora nackdelar: de ger inga fasta garantier för hur bra en lösning är, och de kan bli mycket långsamma för stora kartor, särskilt när varje nytt uppdrag kräver att sökningen startas om. Ett populärt snabbtrick är att först klustra städerna i regioner med verktyg som k-means och sedan lösa ett mindre problem inom varje kluster. Medan denna dela-och-lös-strategi hjälper begränsas slutkvaliteten fortfarande av den underliggande sökmetoden, och att sikta på bättre rutter betyder ofta längre körtid.

Lära ett nätverk att ruttera, och sedan hjälpa det att skala

Under de senaste åren har en annan idé vuxit fram: träna ett neuralt nätverk att direkt producera bra rutter. Efter att ha lärt sig på många exempel på stadsuppställningar kan ett sådant nätverk föreslå en hel rutt i ett enda framåtsteg, ungefär som en språkmodell skriver en mening. Dessa neurala lösare fungerar imponerande väl för en-förare-problem av måttlig storlek, men de snubblar när de ombeds samordna många förare eller när mängden städer är mycket större än i träningen. Författarnas centrala grepp är att kapsla in en sådan neural lösare i en noggrant utformad tvåstegsprocess som omformar en enorm multi-förar-uppgift till många mindre, välkända delproblem som nätverket lätt klarar av.

Hur tvåfasmetoden fungerar

Den föreslagna metoden, kallad KHC-NCN, börjar med att använda en förbättrad version av k-means-klustring för att tilldela städer till olika depåer och förare. Om en resulterande region innehåller för många städer för att den neurala lösaren ska hantera pålitligt delar metoden automatiskt upp den regionen i mindre bitar, vardera av en storlek nära vad nätverket såg under träningen. Koordinaterna i varje del skalas om till en standardkvadrat så att de liknar träningsdata ännu mer. Det neurala nätverket producerar sedan en rutt för varje liten del. Slutligen fogar ett sammanslagningssteg ihop dessa delrutter till en enda slinga för varje förare, med enkla geometriska regler för att koppla ihop delar där det lägger till minst extra sträcka.

Hastighet och kvalitet på verkliga referenskartor

Författarna testar sin metod på en bred samling standardkartor från en offentlig benchmark-samling som ofta används i routingforskning. De jämför mot många etablerade söktekniker och mot både en ledande handbyggd lösare och en annan neural metod. I 44 testfall med olika kartstorlekar och antal förare hittar deras metod kortare totala rutter i nästan tre fjärdedelar av fallen samtidigt som den är dramatiskt snabbare, ofta med flera storleksordningar. Den håller sig särskilt väl när antalet städer stiger till hundratals eller tusentals, där många klassiska metoder bromsar upp eller ger svagare rutter.

Vad detta betyder för ruttplanering i verkligheten

Enkelt uttryckt visar studien att låta ett snabbt neuralt nätverk hantera många små, välformade pussel kan vara bättre än att lägga mycket tid på ett enda gigantiskt pussel. Genom att klustra städer på ett sätt som respekterar nätverkets komfortzon och sedan smart kombinera delresultaten levererar metoden rutter som både är korta och snabba att beräkna. För tillämpningar som logistik, planering av flera robotar och katastrofinsatser pekar detta på ett praktiskt sätt att få nästintill realtids ruttplaner som använder fordon och energi bättre än många befintliga verktyg.

Citering: 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

Nyckelord: fordonsrouting, neuronätverk, klustring, optimering, logistik