Routingberegninger

Routingberegninger refer to the computation of optimal or near-optimal routes through a network. In transport and logistics, it involves determining sequences of edges that connect a source to a destination while minimizing a criterion such as distance, travel time, fuel consumption, or cost. In computer networking, routing calculations determine how data packets are forwarded across a network to minimize delay and maximize reliability.

Networks are modeled as graphs with nodes (vertices) and edges (links). Edges carry weights that can represent distance, time, capacity, cost, or energy use. Weights may be static or subject to change due to traffic, weather, incidents, or other dynamic factors. The fundamental problem is the shortest-path problem, though many routing tasks involve multiple criteria or constraints.

Classical algorithms include Dijkstra's algorithm for non-negative weights, Bellman-Ford for graphs with negative weights, and Floyd-Warshall for all-pairs routes. A* uses heuristic estimates to speed up queries. For large road networks, preprocessing-based methods such as contraction hierarchies, transit node routing, ALT, and hub labeling enable very fast queries after upfront work. For public transport, timetable routing and multi-criteria approaches use specialized data like GTFS.

Dynamic or real-time routing combines live data on traffic, incidents, or weather with the static network to update routes and re-route as conditions change. Multicriteria routing can optimize for time, distance, reliability, or energy use, sometimes under constraints such as time windows or vehicle capabilities.

Applications include car navigation, logistics and fleet management, ride-hailing, emergency response, and urban planning. Key challenges include data quality and freshness, scalability to large networks, uncertainty in travel times, and privacy concerns.