I dagens inlägg lär du dig hur du kan använda Excel för att lösa det kortaste sökvägsproblemet. Problemet med den kortaste vägen är ett grundläggande optimeringsproblem med ett stort antal applikationer. Det används till exempel i logistisk problemlösning, budgetplanering och nätverksoptimering – för att bara nämna några.

Här är ett enkelt nätverk där vi snabbt kan räkna ut för hand att det minimala avståndet från A till F uppnås via rutten C -> E -> D, med ett avstånd på 20.

I verkligheten är avståndet mellan noder sällan rent fysiskt avstånd eller ett enda tal, utan en kombination av olika variabler som bidrar till ett tal som representerar de resurser som används för att ta sig från en nod till en annan.

Till exempel när en navigator planerar din rutt, beräknas rutten med en mycket liknande princip. Det tar hänsyn till saker som fysiskt avstånd, trafik, vägarnas skick och hastighetsbegränsningar. Dessa kombineras sedan för att representera en ungefärlig tid för förflyttning mellan platser (noder).

I en liten datamängd är det relativt enkelt att räkna ut den kortaste vägen utan en algoritm helt enkelt genom att beräkna alla möjliga kombinationer för hand, men när nätverket växer kommer detta att bli nästan omöjligt att göra manuellt. Därför behöver vi en generisk lösning som vi kan använda för ett nätverk i alla storlekar.

Ladda ner övningsfilen som innehåller följande nätverk, som vi kommer att lösa.

kortaste_vägen.xlsx

Vi skapar ett nytt blad där vi kommer att räkna ut den kortaste vägen från A till Destination. Vi börjar med att kartlägga alla olika rutter i nätverket med sina respektive avstånd.

Från nod A kan vi flytta oss till B som kostar oss 12, och till C vilket kostar oss 10. 

Följer vi samma princip, kan vi kartlägga hela nätverket som följande.
Observera att vi kan röra oss i nätverket i vilken riktning som helst, så vi måste även kartlägga vissa rutter i omvänd ordning. Till exempel kan ruttens start vara A -> B -> D eller A -> C -> D -> B          

Här har vi ignorerat några uppenbara omvända vägar för att hålla kartan mer lättläst, men i allmänhet är det inte en bra metod ifall rutten inte uttryckligen är en enkelriktad väg.

Skapa sedan en tom kolumn bredvid “Distans”. Dessa celler kommer att fungera som binära variabler när vi löser den kortaste vägen och markerar den korrekta vägen. Det vill säga: om kortaste vägen börjar från A och går sedan till C, kommer värdet vara 1 i cell D3, annars 0. Det samma gäller alla celler i kolumn D.

Eftersom vi vet att kolumnen “Rutt” kommer att markera de korrekta rutterna med 1, skapar vi en ny kolumn som kommer att mata ut rutten i ett mer läsbart format.

Om den korrekta rutten börjar från A -> B kommer formeln helt enkelt att mata ut “A till B”, annars förblir den tom. Kopiera formeln till alla celler nedan.

Nu måste vi skapa en ny tabell för de begränsningar som vi kommer att skicka in i lösaren. I den första kolumnen skriver vi ner alla noder i nätverket. I kolumnen “Begränsningar” kommer vi att ställa in en funktion som förser lösaren med våra begränsningar – eftersom vi letar efter endast en korrekt rutt.

Skriv:
=SUMMA.OM($A$2:$A$26;H2;$D$2:$D$26)-SUMMA.OM($B$2:$B$26;H2;$D$2:$D$26)

Det kan se komplicerat ut, men allt funktionen gör är att den returnerar 1 om det finns en använd rutt som går ut ur noden, 0 om det finns en använd rutt som kommer in och ut ur noden, och -1 om det finns en rutten kommer in men inte ut. Den kommer också att returnera 0 om det inte finns någon rutt som kommer in eller ut över huvudtaget. Kopiera formeln till alla celler nedan.

Eftersom vi måste berätta för lösaren vad våra begränsningar bör vara lika med, lägger vi till ytterligare en kolumn där vi skriver dessa värden manuellt.

Sammanfattat: vi löser den kortaste vägen genom att ändra de variabla cellerna i kolumn D, då nod A har värdet 1, och Destination värdet -1 i kolumn I. Detta är alltså ett sätt att ange start- och slutnod till problemlösaren.

Innan vi löser kortaste vägen, vill vi även få reda på det totala avståndet – inte bara den korrekta rutten, så vi skriver in en objektiv funktion som vi vill minimera med PRODUKTSUMMA. Funktionen summerar helt enkelt avstånden för de använda sträckorna (SUMMA.OM fungerar också).

Skriv:
=PRODUKTSUMMA(D2:D26;C2:C26)

Nu är vi redo för att lösa den kortaste vägen! Börja med att öppna problemlösaren – tillägget. Om du inte har det installerat, gå till Arkiv -> Fler-> Alternativ och välj Tillägg. Klicka på Gå och välj Problemlösaren från menyn. Problemlösaren hittar du sedan i verktygsfältet längst till höger under Data-fliken.

I problemlösaren behöver vi nu markera objektivfunktionen (E27) som vi löser med att ändra variabla cellerna i kolumn D. Vi väljer MIN för att minimera, och Simplex LP-metoden för att lösa den kortaste vägen. 

Före vi löser bör vi även mata in våra begränsingar. Klicka på Lägg till, välj lika med och mata in kolumnerna för begränsningar. Med andra ord: vi löser vilken kombination av siffror i kolumn D ger det minsta möjliga resultatet i objektivfunktionen (E27) inom begränsingens ramar.

Klicka sedan på OK och på Lös, för att få fram den kortaste vägen från A till Destination – vilket blir rutten A -> B -> E -> G -> J -> Destination. Totala distansen för rutten är 27, vilket returneras av den objektiva funktionen.

Det är viktigt att kunna identifiera vilka problem som går att lösa med en liknande princip. En bra tumregel är att problemet bör ha en livscykel, eller förutsägbar utveckling där vi vet eller kan uppskatta hur mycket resurser vi förbrukar med att röra oss mellan punkter. En resurs blir ofta en enhet, vilket kan vara allt från tid till pengar eller koldioxidutsläpp.