Vehicle Routing Probleme

Das ZAIK/ZPR kann bereits auf eine langjährige Erfahrung im Bereich der Distributionstourenplanung zurückblicken. Häufig bereiten Nebenbedingungen, die nicht genau quantifiziert werden können, große Schwierigkeiten. Ein Unternehmen hatte den Wunsch, daß die Kunden einer Tour räumlich nahe beieinander liegen sollten, um die Ortskenntnis der Fahrer möglichst gut zu nutzen. Wir wählten daher die zur Lösung von Vehicle Routing Problemen (VRP) gängige Vorgehensweise des ,,Cluster first - Route second``. Hierbei werden die zu beliefernden Kunden zunächst zu Clustern zusammengefaßt, um darauf aufbauend die Reihenfolge der Kunden eines Clusters, also die eigentlichen Touren bestimmen zu können.

Das uns damit gestellte Problem der Bestimmung von regional begrenzten Kundenclustern formulierten wir mathematisch als Baumzerlegungsproblem unter Nebenbedingungen. Ein Baum T =(V,E) mit Knotengewichten $w:V \Rightarrow \mathbb{N} ^q$ wird durch Entfernen einer Kantenmenge $S \subseteq E$ in Teilbäume zerlegt. Ziel ist es, eine minimale Menge S zu finden, so daß für die Summen der Knotengewichte in den einzelnen Teilbäumen T_i gilt: $\sum_{v \in V(T_i)} w(v) \leq R$bei vorgegebener oberer Schranke $R\in \mathbb{N} ^q$.