Routingprobleme

Routingprobleme bezeichnen in der Betriebsforschung und Informatik Optimierungsaufgaben, die die Zuweisung von Abfahrtszeiten, Fahrzeugen oder Wegen anfordern, um Ressourcen effizient zu nutzen. Typischer Fokus ist die Bestimmung von Routen, die Kosten, Zeit oder Entfernungen minimieren, während Anforderungen wie Kapazität, Zeitfenster und Reihenfolgen eingehalten werden.

Eine zentrale Form ist das Vehicle Routing Problem (VRP): Aus einem Depot müssen mehrere Fahrzeuge so eingesetzt werden, dass alle Kunden bedient werden, wobei Fahrzeugkapazitäten nicht überschritten werden und die Gesamtbelastung minimiert wird. Viele Varianten existieren, darunter das Capacitated VRP (CVRP), VRP mit Zeitfenstern (VRPTW), Pickup-and-Delivery VRP und Split Delivery VRP.

Das Traveling Salesman Problem (TSP) ist eng mit Routingproblemen verbunden: Es sucht die kürzeste Rundreise, die eine Menge von Standorten genau einmal besucht. Das TSP ist NP-schwer; viele VRP-Varianten erben diese Komplexität.

Methoden: Für kleine Probleme können exakte Verfahren wie ganzzahlige Programmierung, Branch-and-Bound oder Branch-and-Cut passende Lösungen liefern. Größere oder realitätsnähere Aufgaben lösen sich häufig besser durch Heuristiken und Metaheuristiken wie Greedy-Algorithmen, Tabu Search, genetische Algorithmen, Simulated Annealing oder Ant Colony Optimierung. Hybride Ansätze kombinieren verschiedene Strategien.

Anwendungen finden sich in Logistik, Lieferdiensten, öffentlichen Verkehrsmitteln, Abfallwirtschaft und Notfalldiensten. In der Informatik wird zwischen physischen Routingaufgaben (Weg- und Routenplanung) und Netzwerkrouting für Datentransfer unterschieden, wobei Letzteres oft andere Modelle verwendet.