Routingmodelle

Routingmodelle sind mathematische Modelle zur Bestimmung von Routen in Netzwerken unter Kosten-, Zeit- oder Kapazitätsbedingungen. Sie dienen der effizienten Gestaltung von Logistik-, Verkehrs- oder Kommunikationssystemen und zielen darauf ab, Lieferzeiten zu reduzieren, Kosten zu senken und Servicegrade zu verbessern.

Aufbau: Ein Routingmodell arbeitet mit einem Netzwerk G = (N, A). N sind Knoten (z. B. Städte, Depots, Router); A sind Kanten (Straßenabschnitte, Links). Jede Kante (i, j) hat Merkmale wie Kosten c_ij, Reisezeit t_ij oder Kapazität u_ij. Nachfragemengen d_k beschreiben, wie viel von Gut oder Information transportiert werden soll. Entscheidungsvariablen x_ij^k geben an, welcher Fluss des Kontinuums k über (i, j) läuft. Typische Nebenbedingungen umfassen Flussbilanz, Kapazitätsrestriktionen und Nicht-Negativität. Das Ziel ist meist die Minimierung der Gesamtkosten oder der Gesamtzeit.

Klassifikation: Routingmodelle unterscheiden statisch von dynamisch, deterministisch von stochastisch und ein- von Multi-Commodity. Häufige Probleme sind der kürzeste Pfad, das Minimum-Cost-Flow-Problem und das Maximum-Flow-Problem sowie komplexere Fragestellungen wie das Vehicle Routing Problem (VRP) und VRP mit Zeitfenstern oder Abhol- und Lieferaufträgen.

Methoden: Exakte Ansätze verwenden lineare oder gemischt-ganzzahlige Programmierung, oft mit Branch-and-Price-Verfahren für VRP. Für große Netze kommen heuristische und metaheuristische Verfahren wie Tabu Search, Genetic Algorithms oder Ant Colony Optimization zum Einsatz. Grundbausteine wie Dijkstra, Bellman-Ford und Floyd-Warshall liefern Pfad- und Distanzberechnungen.

Anwendung und Grenzen: Routingmodelle finden Anwendung in Logistik, Verkehrsleitsystemen, Telekommunikation und Notfallplanung. Ihre Aussagekraft hängt von Datenqualität, Modellannahmen und Rechenressourcen ab. Typischer Kompromiss ist zwischen Optimalität und Rechenzeit, besonders in zeitabhängigen Netzen.