Die Behandlung des Hierarchischen Chinese Postman Problems

Tourenplanung ist in der heutigen Welt vielseitig anwendbar. Ob man Waren liefert, neue Straßen baut oder eine Stadtrundfahrt plant − überall finden sich Beispiele, wo man Routing-Probleme praktisch einsetzen kann. Die Aufgabe besteht grundsächlich darin, unter Einhaltung aller Restriktionen eine Menge von Routen zu bestimmen, so dass alle erforderlichen Standorte besucht werden und die anfallenden Transportkosten dabei minimal sind. Ein mögliches Anwendungsgebiet für solche Probleme wäre zum Beispiel der Winterdienst, wo eine effiziente Vorgehensweise bei der Schneeräumung oder beim Salzstreuen erforderlich ist. Meistens müssen viel befahrene Straßen und Kreuzungen an erster Stelle bedient werden, um die Unfallwahrscheinlichkeit zu reduzieren. In diesem Fall ergeben sich dann gewisse Prioritätsbeziehungen zwischen bestimmten Gruppen von Straßen. Um den gesamten Straßennetz effizient zu bedienen, muss man den Einsatz von Spezialfahrzeugen optimal gestalten. Hierbei sind zwei wichtige Aspekte ausschlaggebend: zum einen müssen die vorgegebenen Prioritäten eingehalten werden, zum anderen soll die Länge der insgesamt gefahrenen Strecke möglichst kurz sein. Mit solchen Aufgaben befasst