Hybridoptimeringsalgoritm för att lösa ruttplaneringsproblem baserat på gråvargoptimeringsalgoritmen

Smartare rutter i trånga städer

Varje dag står förare, leveransfordon och robotar inför samma utmaning: hur tar man sig snabbast och säkrast från A till B utan att slösa bränsle eller tid? Denna artikel presenterar en ny beräkningsmetod som planerar kortare, jämnare rutter genom komplexa gatnät fyllda med hinder och trängsel. Genom att låna idéer från hur gråvargar jagar i flock och hur prospektörer söker efter guld visar författarna hur man mer effektivt kan styra fordon och robotar genom tätbefolkade stadsmiljöer.

Varför bättre rutter spelar roll

När städer växer och trafiken tätas kan även små förbättringar i ruttplanering ge stora besparingar i tid, energi och utsläpp. Traditionella sökmetoder fungerar väl när kartan är enkel, men de tenderar att sakta ner eller fastna när miljön är full av möjliga svängar och hinder. Moderna ”intelligenta” sökmetoder försöker efterlikna naturen—som fågelflockar eller myrkolonier—för att samtidigt utforska många alternativ och slå sig ner på bra lösningar. En sådan metod, kallad gråvargoptimeringsalgoritmen, har blivit populär eftersom den är enkel och flexibel, men den lider fortfarande av tre huvudsakliga problem: den kan fastna i näst bästa rutter, den kan konvergera för tidigt och den söker inte alltid igenom hela kartan noggrant.

Blanda vargar, kaos och guldgrävare

För att övervinna dessa svagheter utformar författarna en förbättrad version som de kallar CGGWO. Den behåller grundidén med en flock virtuella gråvargar som söker efter den bästa rutten, men ändrar hur flocken sprider sig och lär sig. För det första, i stället för att placera vargarna på slumpmässiga startpunkter, använder metoden ett matematiskt knep kallat kaotisk avbildning för att sprida dem jämnare över sökområdet. Det ökar chansen att åtminstone några vargar upptäcker lovande regioner på kartan. Därefter lånar metoden en regel från en annan teknik inspirerad av guldprospektörer. Här skjuts den ledande ”alfa”-vargen mot särskilt rika områden i sökutrymmet, ungefär som gruvarbetare gradvis flyttar sig mot områden med mer guld. Detta steg injicerar kontrollerad slumpmässighet och variation, vilket hjälper flocken att undkomma dåliga lokala val.

Klyftig korsning och försiktig skakning

CGGWO lägger sedan till två typer av ”kors-kors”-rörelser som blandar information mellan vargarna. I den horisontella rörelsen byter två olika kandidatvägar delar av sina rutter, vilket minskar blinda fläckar och uppmuntrar sökningen att täcka kartan mer fullständigt. I den vertikala rörelsen blandas olika sektioner inom en och samma rutt med varandra, vilket kan återuppliva stillastående delar av lösningen och förhindra att flocken låser sig för tidigt på en bristfällig rutt. Slutligen håller en mild dos av Gaussisk mutation—små, slumpmässiga knuffar styrda av hur väl varje varg presterar—flocken i utforskande läge. Om en vargs rutt är sämre än genomsnittet får den en kraftigare skakning, vilket hjälper hela gruppen att undvika att fastna i ett hörn av lösningslandskapet.

Sätta den nya metoden på prov

Forskarna testar först CGGWO på 23 standardiserade matematiska problem som ofta används för att bedöma sökalgoritmer. Dessa problem varierar från jämna landskap med en enda bästa dal till skrovliga terränger fulla av många lokala minima. I de flesta av dessa tester hittar CGGWO bättre svar, konvergerar snabbare och uppvisar mer stabilt beteende än flera välkända konkurrenter, inklusive den ursprungliga gråvargsmetoden, partikelsvärmsoptimering och genetiska algoritmer. Teamet går sedan vidare till ett realistiskt ruttplaneringsproblem baserat på ett förenklat gatnät nära ett livligt kommersiellt område i Lhasa. Hinder representerar blockerade eller trånga sektioner, och målet är att koppla ihop start- och slutpunkt med en kort, jämn rutt som undviker dem.

Kortare, mjukare resor

I trafikliknande testet producerar CGGWO konsekvent kortare rutter med färre skarpa svängar än de andra metoderna samtidigt som beräkningstiden är måttlig. Jämfört med den ursprungliga gråvargsalgoritmen och flera rivaliserande tekniker är dess planerade rutter rakare och lättare att följa, vilket i vissa jämförelser minskar avståndet med upp till ungefär en fjärdedel. För en allmän läsare är slutsatsen tydlig: genom att skickligt kombinera idéer från kaos, gruppjakt och guldprospektering söker den nya metoden igenom kartor mer noggrant och undviker att fastna i bara acceptabla lösningar. Det gör den till ett lovande verktyg för framtida navigationssystem, leveransrobotar och andra smarta maskiner som snabbt måste hitta säkra, effektiva rutter genom dagens trånga och föränderlig stadslabyrinter.

Citering: Cheng, G., Liu, Y. Hybrid optimization algorithm for solving path planning problems based on grey wolf optimization algorithm. Sci Rep 16, 8479 (2026). https://doi.org/10.1038/s41598-026-35037-z

Nyckelord: ruttplanering, optimeringsalgoritm, intelligent transport, svärmintelligens, robotnavigering