Ruttberäkning

Ruttberäkning, eller ruttplanering, är processen att hitta en lämplig väg mellan två eller flera punkter i ett transportnätverk. Nätverket modelleras ofta som en graf där noder kan vara korsningar eller hållplatser och kanter motsvarar vägar eller länkar med vikter som kan representera avstånd, restid, kostnad eller klimatpåverkan. Målet är att optimera en eller flera kriterier beroende på sammanhang, till exempel snabbaste, kortaste eller billigaste rutt.

Vanliga algoritmer omfattar Dijkstra-algoritmen för kortaste vägen i grafen med icke-negativa vikter, samt A*-algoritmen som använder en heuristik för att snabbare hitta vägen i stora nätverk. Andra klassiska metoder är Bellman-Ford som hanterar negativa vikter och Floyd-Warshall för all-pairs kortaste vägar. Modern ruttberäkning används ofta förlängda tekniker och parametriska varianter samt anpassade kostnader som tidsvariationer, köer och fordonsbegränsningar.

Moderna navigationssystem kombinerar kartdata med realtidsinformation om trafik, väder eller incidenter för att uppdatera vikterna och generera nya rutter. Utvidgningar inkluderar multi-criteria ruttberäkning där flera mål vägs samman, användarpreferenser samt fordonsegenskaper samt tekniker för att hantera mycket stora nätverk med förhandsberäkningar och snabb uppslagning.

Användningsområden sträcker sig över bilnavigation, gång- och cykelvägar, kollektivtrafikplanering samt logistik och leverans. Viktiga utmaningar inkluderar hantering av dynamik i realtid, skala, osäkerhet i färdvägar och kompromisser mellan exakt optimala lösningar och snabb svarstid. Ruttberäkning är ett centralt område inom grafteori och geografiska informationssystem.