Graphentheorie in Planungs- und Tourenproblemen

Die vorliegende Arbeit befasst sich mit den Problemkreisen der Standortwahl und der Tourenplanung. Zwischen diesen beiden Themen besteht meist grund satzliche gegenseitige Abhangigkeit, ob sie nun in die konkrete Aufgaben stellung miteinbezogen oder willentlich von ihr ausgeklammert werde: fiir die Festlegung von wirts chaftlichen Tourenplanen beis pielsweis e zum Zwecke der Belieferung von Filialgeschaften wird man wissen mussen, wie viele Filialgeschafte zu bedienen sind und wo sie ihren Standort haben, aber auch von wie vie len Bedienungspunkten aus dies geschehen solI und wo diese letzteren gefunden werden konnen. Umgekehrt lassen sich Zahl und Standorte der an einem solchen Verteilsystem gesamthaft angeschlossenen Umschlagpunkte zweifellos durch Mitberucksichtigung der Tourenplanung neben den anderen Einflussquellen in wirtschaftlicher Sicht bestimmen. Dennoch kann der Grad dieser gegenseitigen Abhangigkeit je nach Aufgaben stellung recht unterschiedlich sein: die Wahl des genauen "Standorts" eines Flughafens innerhalb einer grosseren Region wird sich vermutlich weit weniger ausgepragt oder praktisch gar nicht auf die Wirtschaftlichkeit der internationa len "Tourenplanung" von dort beheimateten Flugzeugen einer Fluggesellschaft auswirken verglichen mit der Bedeutung des Standorts eines Lagerhauses fiir die Wirtschaftlichkeit der Tourenplanung zwecks Belieferung von Detail- s chaften von dort aus, weil im ersteren FaIle die beiden Problem -Kreis e von anderen, unabhangigen Einflus sfaktoren dominierenden Charakters tiber schattet werden. Beide erwahnten Aufgabentypen: Standortwahl und Festlegung von Bedienungs touren sind vom Standpunkt des Operations Research aus gesehen anspruchs voll und nicht ohne weiteres losbar. Die mathematische Behandlungsschwierig keit steigt mit dem Grade der Berucksichtigung der gegenseitigen Abhangigkeit.

Inhalt
0.1. Vorwort.- 0. 2. Zusammenfassung.- 1. Einige Begriffe aus der Graphentheorie.- 1.1. Einleitung.- 1.2. Definitionen.- 1.3. Graphen und Abbildungen.- 1.4. Funktionen auf Graphen.- 1.5. Matrizendarstellung von Graphen und Funktionen darauf.- 2. Euler-Graphen, -Zyklen und-Kreise.- 2.1. Begriffe und Einleitung.- 2.2. Anzahl verschiedener Euler-Kreise und -Zyklen eines Graphen.- 2.3. Erzeugung eines Euler-Zyklus auf einem Euler-Graphen mit Hilfe eines Zufallsmechanismus (Irrgang).- 3. Probleme des chinesischen Briefträgers.- 3.1. Einleitung.- 3.2. Erstes Problem: Fall eines einzigen zusammenhängenden Untergraphen.- 3.3. Zweites Problem: Fall mehrerer je zusammenhängender Komponenten.- 3.4. Diskussion.- 4. Optimale Bedeckung eines Euler-Graphen, unter Einhaltung gewisser Restriktionen.- 4.1. Problemstellung.- 4.2. Diskussion.- 4.3. Heuristisches Lösungsverfahren.- 4.4. Beispiel.- 5. Restriktionen für die Planung periodisch wiederkehrender Tätigkeiten, z.B. Strassenreinigung.- 5.1. Einleitung.- 5.2. Erster Fall.- 5.3. Zweiter Fall.- 5.4. Dritter Fall.- 5.5. Schlussfolgerungen.- 5.6. Reinigungsdichten und Umformung der Restriktionen.- 6. Zerschneidung einer ebenen Figur, unter Einhaltung gewisser Restriktionen.- 6.1. Einleitung.- 6.2. Problemstellung 6.- 6.3. Diskussion.- 7. Optimale Aufteilung eines Graphen, unter Einhaltung gewisser Restriktionen.- 7.1. Einleitung.- 7.2. Problemstellung.- 7.3. Diskussion.- 7.4. Formulierung des Problems durch ein Modell der ganzzahligen Programmierung.- 7.5. Heuristisches Lösungsverfahren.- 8. Strassenreinigung in Zürich.- 8.1. Einleitung.- 8.2. Ist-Zustand.- 8.3. Systematische Datenerfassung.- 8.4. Datenverarbeitung und Auswertung.- 8.5. Einige Ergebnisse der Auswertungen.- 8.6. Fiktives Anwendungsbeispiel der entwickeltenVerfahren auf die Grobplanung der maschinellen Trottoirreinigung der Stadt Zürich.