Om pubrundor och trädbeskärning

Figur 1: Lösningen (1, 2, 5, 4, 3, 6) för ett TSP med 6 noder.

För ett tag sedan dök en artikel upp i mitt flöde som fångade mitt intresse en smula. Det handlade om en grupp matematiker som hade löst ett problem med att hitta den kortaste pubrundan som besökte alla pubar i Storbrittanien. Detta ligger ganska nära de problem vad jag för närvarande pysslar med på jobbet. Annat pockade dock på uppmärksamheten så det är först nyligen som jag satte mig ner och läste originalartikeln, och jag insåg att det fanns fler beröringspunkter med mitt arbete än jag först trodde, och jag fick några intressanta uppslag. Artikeln är populärvetenskapligt hållen och kan rekommenderas, men jag ska ändå ge en egen beskrivning nedan med lite utvikningar.

Handelsresandeproblemet

Det hela är ett exempel på det klassiska så kallade handelsresandeproblemet, hädanefter refererat till dess engelska akronym TSP. TSP handlar kortfattat om att besöka ett antal (N) platser så att den totala kostnaden blir så låg som möjligt, där kostnaden att ta sig mellan varje par av platser är känd. Med kostnad kan avses många olika saker beroende på tillämpningen; sträcka, tid, pengar eller något annat. Och "platser" bör förstås metaforiskt; visserligen kan det handla om fysiska platser i logistiksammanhang, men det kan även handla om ett tillverkningssteg i en fabrik, och kostnaden att "ta sig mellan platser" kan då exempelvis vara tiden för att ställa om en maskin mellan två moment. Framgent kommer platser i stället kallas för noder, och vägen/kopplingen mellan två noder kallas kanter.

Figur 2: Beslutsträd för ett TSP med 6 noder som utgår från noden 1.
Rektanglarna anger vald dellösning hittills.
Siffrorna bredvid pilarna anger val av nästa nod.
Av utrymmesskäl är bara delar av trädet utritat.

Man kan visualisera lösningsprocessen med ett beslutsträd som i figur 2 ovan. Vi väljer en nod att starta i, vilken som helst. Vi kan kalla den nod 1. Därefter väljer man nästa nod att besöka, vilken som helst utan 1. Det innebär N-1 möjliga val som motsvaras av lika många grenar i beslutsträdet. För nästa nod att besöka finns det N-2 möjligheter o.s.v. Antalet möjliga sätt att besöka noderna på är (N-1)*(N-2)*...*2 vilket snabbt blir ett gigantiskt stort tal för stora N. Redan för ungefär N=20 går gränsen där det tar orimligt lång tid att testa alla lösningar, och TSP är ett så kallat NP-fullständigt problem, vilket gör att alla matematiker tror att det är omöjligt att lösa varje probleminstans inom rimlig tid. Lyckligtvis finns det tack vare stora forskningsinsatser effektiva algoritmer för att lösa realistiska problem med hundratals eller till och med tusentals noder med rimlig tidsåtgång. Dessa algoritmer kan delas upp i exakta eller approximativa.

Approximativa algoritmer

Denna klass av algoritmer nöjer sig med att hitta en lösning som inte nödvändigtvis är den bästa men som ändå är tillräckligt bra i utbyte mot att beräkningstiden hålls nere. Det kan vara värt att tillägga att approximativa algoritmer ibland avser en smalare kategori där man kan garantera att lösningens kostnad ligger inom ett visst avstånd från den optimala kostnaden. Jag använder dock den bredare betydelsen här.

Giriga algoritmer

Den kanske enklaste metoden - som nog de flesta skulle tänka ut om man funderade på det ett slag - är följande: Börja i någon nod, gå därefter till den nod till vilken kostnaden är lägst, därefter till den kvaravarande nod till vilken kostnaden är lägst, etc. Detta är ett typiskt exempel på så kallade giriga algoritmer; man gör hela tiden det som verkar vara bäst för stunden utan någon framförhållning. Giriga algortimer är allmänt beräkningssnabba men ger ofta ett mediokert resultat. De går dock att förbättra på många sätt genom diverse mer eller mindre smarta sätt att förse valet om vart man ska gå härnäst med olika typer av information. Sådana varianter används ofta som startlösning för lokalsökningsmetoder vilket vi ger oss på nu.

Lokalsökning

Denna breda klass av metoder innebär att man utgår ifrån någon lösning och försöker förbättra den genom små (lokala) förändringar. Ett exempel på en sådan förändring ges i figur 3 nedan. Den nya, förbättrade lösningen försöker man sedan ytterligare förbättra med samma metod. När det inte går att göra några fler lokala förbättringar har man nått ett lokalt optimum. En probleminstans har ofta många lokala optimum, och risken är att just det man hamnat i är avsevärt sämre än det globala optimum man söker. Samtidigt är lokalsökningsmetoder relativt beräkningssnabba, och man kan införa olika åtgärder för att ta sig ur lokala optimum och fortsätta sökningen. Ett exempel ges av simulerad glödgning där man slumpmässigt tillåter försämrande förändringar för att undvika att sökningen fastnar. Sannolikheten för att välja en sämre lösning avtar allteftersom sökningen fortgår och till slut hamnar man i vanlig lokalsökning.

Figur 3: Förbättring av turen i figur 1 till turen (1, 2, 3, 4, 5, 6) medelst kantbyte.

Metaheuristiker

Den sistnämnda metoden är ett exempel på så kallade metaheuristiker, en något diffus klass av metoder med syfte att effektivt och brett söka efter bra lösningar. Ofta är de inspirerade av naturen. Det mest kända exemplet är kanske genetiska algoritmer, där en population av lösningar utvecklas i generationer efter evolutionära principer såsom att de bästa lösningarna får "para sig" och kombinera ihop sig till nya lösningar. Andra metaheuristiker har inspirerats av vargflockar, myrsamhällen* och fågelsvärmar.

Hybridmetoder

De approximativa algoritmer som har levererat bäst resultat hittills kombinerar en metaheuristik med lokalsökning. I vissa fall är detta inbyggt i metaheuristiken från början, som för simulerad glödgning eller tabusökning. I andra fall kan det infogas på något systematiskt sätt, exempelvis genom att alltid köra lokalsökning varje gång en ny lösning skapas. Men nog om detta, vi är ju faktiskt ute efter den absolut bästa pubrundan, och då behöver vi exakta metoder.

Exakta metoder

Denna klass av metoder har egenskapen att de levererar en optimal lösning förr eller senare. I det sistnämnda fallet kan man avbryta efter en i förväg given bortre tidsgräns och förhoppningsvis åtminstone erhålla en lösning tillsammans med en tolerans som anger minst hur nära optimum man är procentuellt. De absolut vanligaste exakta metoderna är branch-and-bound, cutting planes och branch-and-cut som är en kombination av de två förstnämnda.

Branch-and-bound

Idén bakom branch-and-bound (B&B) är att på något sätt kunna sätta en undre gräns på den bästa lösningen givet olika positioner i beslutsträdet. Säg att vi till exempelvis vill utforska alla lösningar där vi besöker BrewDog-baren i Edinburgh direkt efter motsvarande i Camden**. Ponera att vi på något sätt visste att sådana lösningar aldrig kan vara kortare än 46 000 km. Detta kallar vi en undre gräns för denna del av sökträdet. Tänk om vi dessutom redan kände till en lösning som är kortare än 46 000 km - exempelvis genom några av de approximativa metoderna beskrivna ovan. Detta kallar vi en övre gräns för hela problemet. Då vet vi att den optimala lösningen inte finns i denna del av beslutsträdet, och vi kan strunta att leta vidare just här. Vi kan beskära denna del av trädet. Denna idé genomför vi sedan generellt genom att för varje position i beslutsträdet beräkna en undre gräns och jämföra denna med den nuvarande övre gränsen. Varje gång vi stöter på en ny lösning (genom att tränga hela vägen ner i trädet genom någon väg) som är den bästa hittills får vi en ny övre gräns som är bättre än den förra. Genom effektiv beskärning av trädet blir det en hanterbar mängd lösningar som behöver analyseras.

Kärnfrågan är hur vi beräknar dessa undre gränser, och framgången hos B&B är helt avhängigt hur tajt vi lyckas med detta. Vi kan ju alltid säga att 0 är en undre gräns, men det hjäper oss föga. Ett sätt är via så kallade relaxeringar. En relaxering innebär att vi släpper på vissa krav i problemformuleringen och får ett generellare problem som samtidigt är lättare att lösa. Varje lösning till ursprungsproblemet är också en lösning till det relaxerade problemet, men inte tvärtom. Därmed blir den optimala lösningen för det relaxerade problemet en undre gräns. För TSP så är ett exempel på relaxering att tillåta flera turer/slingor/cykler, något som brukas kallas "minimum cycle cover problem", och illustreras i figur 4. Detta problem är betydligt enklare än TSP och en optimal lösning kan beräknas med en tidsåtgång som är proportionell mot N^2.

Figur 4: En "cycle cover" för ett TSP med 6 noder.

Cutting planes

Det här är en teknik som kräver lite mer matematisk kunskap för att förstås, men vi gör ett försök. Grundtanken är att man inför binära kantvariabler x1, x2, x3 etc. enligt någon numrering på kanterna, där värdet på variabeln är 1 om kanten är med i lösningen och 0 annars. Om vi samtidigt betecknar kanternas kostnader med c1, c2, ... så ges den totala kostnaden av

z = x1*c1 + ... + xN*cN

Vi vill alltså minimera z, men för att få en koppling till TSP så måste vi lägga på lite ytterligare krav på kantvariablerna så att vi inte kan välja kanter hur som helst. För att vi ska passera varje nod exakt en gång så krävs att varje nod är ändpunkt för exakt två kanter. För en nod som är ändnod i kanterna 2, 3, 5 och 6 kan vi uttrycka detta som

x2 + x3 + x5 + x6 = 2

Ett liknande bivillkor kan ges per nod för att säkerställa att varje nod besöks exakt en gång. Däremot garanterar dessa bivillor inte att vi får en riktig tur, utan det kan se ut som i figur 4. För att garantera en riktig tur måste vi ställa ytterligare bivillkor, så kallade sub-tour elimination constraints. Det ena sättet går via att införa fler variabler, och fördelen med detta sätt är att det krävs en måttlig mängd extra bivillkor. Ett alternativ är i stället att uttrycka bivillkoren enbart med kantvariablerna, men då får vi en enorm mängd bivillkor. Detta går dock att hantera via det som kallas för cutting planes.

Grundtanken är att vi släpper på kravet att kantvariablerna bara kan anta värdena 0 eller 1, och i stället tillåter att de kan vara allt mellan 0 och 1. Då blir problemet att försöka minimera z med bivillkoren ett mycket enklare problem som kan lösas effektivt med simplexmetoden. Om denna optimala lösning faktiskt är en TSP-lösning (alla kantvariabler är 0 eller 1, och de kanter som är med bildar en tur) är vi klara och har hittat den optimala TSP-lösningen. Om inte lägger vi till några väl valda bivillkor och upprepar proceduren. Notera att vi i varje upprepning får en undre gräns till det optimala värdet. Detta går förstås att kombinera med branch-and-bound, och då får man något som kallas branch-and-cut vilket får ses som kronan på verket bland algoritmer för TSP. I branch-and-cut väljer man att förgrena problemet på någon kantvariabel som varken är 0 eller 1, och skapar ett delträd för 0 och ett för 1.

Knyta ihop säcken

Nu återstår en sista aspekt som för egen del kanske är den intressantaste och som var det som på allvar gjorde att jag intresserade mig för detta projekt. När antalet noder är N = 24 727 så är det potentiellt ungefär 306 miljoner avstånd mellan pubar som behöver beräknas. Eftersom vi vill veta det faktiska gångavståndet så får vi vända oss exemeplvis till Google Maps för varje sådan avståndsberäkning. Detta är helt ogörbart, och man får hitta någon bra strategi för att hantera detta.

För de tillämpningar jag sysslar med så har vi liknande svårigheter. Vi försöker minimera den totala tid en industrirobot behöver för att utföra ett antal uppgifter (exempelvis punktsvetsar på en kaross) samt att förflytta sig mellan de olika uppgifterna. Tiden det tar för alla dessa parvisa förflyttningar kan beräknas med en sofistikerad banplaneringsalgoritm som tyvärr är ganska tidskrävande, och att beräkna alla potentiella förflyttningar är ej aktuellt.

Lösningen är att hitta en approximation av avstånden/tiderna/kostnaderna som är snabb att beräkna och samtidigt alltid är lägre än det faktiska värdet. För gångavstånden mellan pubarna kan man använda "fågelavståndet", och för robotarna finns ett liknande kortaste avstånd där man bortser från diverse geometriska hinder. Dessa approximationer är vad som används initialt för alla kanter. Kanter som verkar lovande och som man av någon anledning tror kan ingå i den optimala lösningen analyseras fullt ut. Exakt vilka kriterier som används för detta går jag inte in på här, men det är ändå värt att påpeka att lösningar som används för en övre gräns måste ha alla ingående kanter fullt analyserade. Och oavsett hur många kanter vi har beräknat den faktiska kostnaden för så kommer vi hela tiden få giltiga undre gränser för den optimala lösningen. Görs detta på ett smart sätt kommer förhoppningsvis bara en liten bråkdel av alla faktiska kantkostnader beräknas. För detaljer angående pubrundeproblemet hänvisas till originalartikeln.


* Jag håller just på med en artikel där vi använder en sådan algoritm
** Bara för att få dessa sunkhak snabbt överstökade