Baumzerlegung unter Nebenbedingungen

• Im ersten Schritt wird ein minimaler aufspannender Baum berechnet auf Grundlage der Entfernungen zwischen den Orten.

• Dann wird durch Wegnahme einiger Kanten der Baum in Teilbäume aufgeteilt.

• Der Baum wird so unterteilt, dass in jedem entstehenden Teilbaum bestimmte Restriktionen gelten (z.B. Gesamtmenge an Zeitungen darf LKW-Kapazität nicht überschreiten, nur wenige Kunden sollten zeitkritisch sein)

• In jedem Teilbaum wird danach die Tour des LKWs nach Zulässigkeit (pünktliche Belieferung) und Weglänge optimiert