Tourenplanung
Die Tourenplanung bietet eine möglichst gute Lösung für das Problem, mit welchen Fahrzeugen welche Kunden von einem oder mehreren Depots beliefert werden. In der Realität wird die Aufgabenstellung meistens noch durch viele Parameter erweitert. Beispielsweise existiert das kapazitierte Tourenplanungsproblem, bei dem die Fahrzeuge eine begrenzte Kapazität (z.B. Volumen, Gewicht) besitzen. Ein andere mögliche Zusatzaufgabe ist die Betrachtung von Zeitfenstern, in deren Grenzen ein Fahrzeug beim Kunden eintreffen muß. Von einer dynamischen Tourenplanung spricht man dann, wenn die Aufträge für eine Planungsperiode noch nicht vollständig sind und sich entweder Aufträge ändern oder neue hinzukommen.
Anwendungen existieren neben dem Logistikbereich in allen Wirtschaftszweigen, die ihre Kunden beliefern (z.B. Möbelindustrie, Müllabfuhr oder Automatenbeschicker). In vielen Unternehmen wird Tourenplanungssoftware eingesetzt, um die anfallenden Touren zusammenzustellen und anhand von Kriterien, wie z.B. der Einhaltung von Zeitvorgaben oder Gewichtschranken, sowie Transportkosten zu optimieren.
Mathematische Funktionsweisen
Die Tourenplanung gehört zu der Klasse der NP-Schwere-Probleme. Daher werden zur Lösung des Problems Heuristiken angewandt. Gute und einfache Lösungsverfahren bieten das Savings-Verfahren und der Sweep-Algorithmus. Bessere Verfahren beruhen auf Genetischer Algorithmus, simulierte Abkühlung und Tabu Search. Sie nutzen lokale Suchstrategien, bei dem die Reihenfolge von Aufträgen bzw. Zuordnung von Aufträgen zu Fahrzeugen getauscht wird. In letzter Zeit wird auch immer häufiger der Ameisenalgorithmus als Problemlösung in Betracht gezogen.
Als Subproblem der Tourenplanung ergibt sich das Problem des Handlungsreisenden, indem man ein Fahrzeug mit unbegrenzter Kapazität betrachtet und dieses mit minimalen Kosten oder Weglänge fahren lässt.
Siehe auch
Literatur
- Domschke, W.: Logistik: Rundreisen und Touren. 4. Aufl., Oldenbourg-Verlag, München - Wien 1997.