Zwischenbericht der

Projektgruppe

Transportoptimierung

Bericht Nr. 1998/06

Seite 1: nächste Seite | Übersicht

Seite 2: vorherige Seite | nächste Seite | Übersicht

P

Universität
Stuttgart

Zwischenbericht der Projektgruppe

Transportoptimierung

Jörg Fleischmann
Lars Hermes
Tobias Spribille
Frank Wagner

Betreuung

Prof. Dr. Volker Claus
Dipl.-Inform. Friedhelm Buchholz
Dipl.-Inform. Stefan Lewandowski

Abteilung Formale Konzepte
Fakultät Informatik
Universität Stuttgart

4. Mai 1998

Seite 3: vorherige Seite | nächste Seite | Übersicht

Prof. Dr. Volker Claus
Abteilung Formale Konzepte
Institut für Informatik
Universität Stuttgart

Breitwiesenstr. 20-22
D-70565 Stuttgart

Telefon:

0711-7816-300 (Prof. Dr. V. Claus)
0711-7816-301 (Sekretariat)
0711-7816-330 (FAX)

E-Mail: claus@informatik.uni-stuttgart.de

Seite 1: vorherige Seite | nächste Seite | Übersicht

Inhaltsverzeichnis

1 Vorwort 8
1.1 Die Projektgruppe im Informatikstudium . . . . . . . . . . . . . 8
1.2 Die Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Seminarvorträge 11
2.1 Constraint Programming . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.1 Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.3 Anwendungsbeispiele . . . . . . . . . . . . . . . . . . . . . 13
2.1.4 Constraints als Vorgaben . . . . . . . . . . . . . . . . . . 14
2.1.5 Constraints als Beziehungen . . . . . . . . . . . . . . . . . 18
2.1.6 EinÄufl des Benutzers . . . . . . . . . . . . . . . . . . . . 23
2.1.7 Komplexität . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Objektorientierte Spezi?kation . . . . . . . . . . . . . . . . . . . 25
2.2.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2 Das Objektmodell . . . . . . . . . . . . . . . . . . . . . . 25
2.2.3 Objekte und Klassen . . . . . . . . . . . . . . . . . . . . . 28
2.2.4 Klassi?zierung . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.5 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.6 Prozefl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3 Flüsse in Netzwerken . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3.2 De?nitionen . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.3.3 Das Minimum Cost Flow Problem . . . . . . . . . . . . . 52
2.3.4 Spezialfälle . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3.5 Verallgemeinerungen . . . . . . . . . . . . . . . . . . . . . 58
2.3.6 Das Integer Generalized Flow Problem ist NP-hart . . . . 60
2.3.7 Anwendung . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.4 Nachbarschaftssuche im Rd . . . . . . . . . . . . . . . . . . . . . 64
2.4.1 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . 64
2.4.2 Baumstrukturen . . . . . . . . . . . . . . . . . . . . . . . 65
2.4.3 Das Gitterverfahren >= mehrdimensionales Hashing . . . . 72
2.4.4 Das Closest Pair Problem >= CPP . . . . . . . . . . . . . . 80

3 Anforderungsanalyse 85 3.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2 Umgebung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.3 Aufbau des Systems . . . . . . . . . . . . . . . . . . . . . . . . . 86

5

Seite 2: vorherige Seite | nächste Seite | Übersicht

3.3.1 Benutzungsschnittstelle . . . . . . . . . . . . . . . . . . . 86
3.3.2 Datenverwaltung . . . . . . . . . . . . . . . . . . . . . . . 86
3.3.3 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 86
3.3.4 Automatische Tourplanung . . . . . . . . . . . . . . . . . 87
3.3.5 Ermittlung von Analysedaten . . . . . . . . . . . . . . . . 87
3.3.6 Anbindung an ein Verkehrstool . . . . . . . . . . . . . . . 87
3.4 Ist-Zustand beim Kunden . . . . . . . . . . . . . . . . . . . . . . 87
3.4.1 Allgemeines . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.4.2 Dienste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.4.3 Ressourcen . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.4.4 Planung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.5 Erfahrungsbericht . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.6 Notwendige Eingabedaten . . . . . . . . . . . . . . . . . . . . . . 93
3.6.1 Kunden erfassen . . . . . . . . . . . . . . . . . . . . . . . 93
3.6.2 Dienst anfordern . . . . . . . . . . . . . . . . . . . . . . . 94
3.6.3 Touren eingeben . . . . . . . . . . . . . . . . . . . . . . . 96
3.7 Szenarien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.7.1 Schulfahrten . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.7.2 MSD / PÄegedienst . . . . . . . . . . . . . . . . . . . . . 98
3.7.3 Essen auf Rädern . . . . . . . . . . . . . . . . . . . . . . . 100
3.7.4 Individualfahrten . . . . . . . . . . . . . . . . . . . . . . . 101
3.7.5 Pläne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4 Spezi?kation 104 4.1 Gesamtsystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.1.1 Umgebung des Produktes . . . . . . . . . . . . . . . . . . 104
4.1.2 Warum Java? . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.1.3 Verwendete Tools . . . . . . . . . . . . . . . . . . . . . . . 105
4.1.4 Funktionalität . . . . . . . . . . . . . . . . . . . . . . . . 106
4.1.5 Entwicklungsphilosophie . . . . . . . . . . . . . . . . . . . 108
4.2 Datenmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.2.1 Klassendiagramme . . . . . . . . . . . . . . . . . . . . . . 108
4.2.2 Klassen-Beschreibungen . . . . . . . . . . . . . . . . . . . 115
4.2.3 Tourkonzept . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.3 Verkehrsmodul . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
4.3.1 Das Verkehrstool: Map&Guide . . . . . . . . . . . . . . . 138
4.3.2 Aufbau des Verkehrsmoduls . . . . . . . . . . . . . . . . . 138
4.3.3 Korrektur von Entfernungen . . . . . . . . . . . . . . . . . 139
4.4 Datenausgabe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.4.1 Dienstpläne . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.4.2 Analysedaten . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.4.3 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
4.4.4 Anfragen . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.4.5 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 143
4.5 Lokale Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.5.1 Ein- und Ausgabe der Optimierung . . . . . . . . . . . . . 144
4.5.2 Was soll optimiert werden? . . . . . . . . . . . . . . . . . 144
4.5.3 EÖzienz . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.5.4 Mafle für verschiedene Parameter . . . . . . . . . . . . . . 145
4.5.5 Wie könnte eine gute Lösung gefunden werden? . . . . . . 145

Seite 3: vorherige Seite | nächste Seite | Übersicht

7

4.5.6 Generischer Ansatz . . . . . . . . . . . . . . . . . . . . . . 153
4.6 Inkrementelle Optimierung . . . . . . . . . . . . . . . . . . . . . 160
4.6.1 Touren erweitern . . . . . . . . . . . . . . . . . . . . . . . 160
4.6.2 Dienstwünsche einfügen . . . . . . . . . . . . . . . . . . . 161
4.6.3 Inkrementelles Verbessern . . . . . . . . . . . . . . . . . . 161
4.6.4 Bewertung Tourenmengen . . . . . . . . . . . . . . . . . . 161
4.7 Die BenutzungsoberÄäche . . . . . . . . . . . . . . . . . . . . . . 163
4.7.1 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 163
4.7.2 Hauptmenu . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.7.3 Dienste anfordern . . . . . . . . . . . . . . . . . . . . . . 163
4.7.4 Obertour eingeben . . . . . . . . . . . . . . . . . . . . . . 169
4.7.5 Untertour eingeben . . . . . . . . . . . . . . . . . . . . . . 170
4.7.6 Mitarbeiter eingeben . . . . . . . . . . . . . . . . . . . . . 171
4.7.7 Fahrzeug eingeben . . . . . . . . . . . . . . . . . . . . . . 172
4.7.8 Fahrzeugtyp eingeben . . . . . . . . . . . . . . . . . . . . 174
4.7.9 Kunden eingeben . . . . . . . . . . . . . . . . . . . . . . . 174
4.7.10 Rechnungsempfänger eingeben . . . . . . . . . . . . . . . 175
4.7.11 Kontaktperson eingeben . . . . . . . . . . . . . . . . . . . 176

5 Entwurf 177 5.1 Grobentwurf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.1.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.1.2 BenutzungsoberÄäche . . . . . . . . . . . . . . . . . . . . 177
5.1.3 Datenhaltung . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.1.4 Verkehrsmodul . . . . . . . . . . . . . . . . . . . . . . . . 185
5.1.5 Konsistenztests . . . . . . . . . . . . . . . . . . . . . . . . 186
5.1.6 Optimierung . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.2 Feinentwurf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.2.1 Klasse Person und zugehörige Klassen . . . . . . . . . . . 190
5.2.2 Klasse Dienstwunsch und zugehörige Klassen . . . . . . . 194
5.2.3 Klasse Fahrzeug und zugehörige Klassen . . . . . . . . . . 197
5.2.4 Klasse Tour und zugehörige Klassen . . . . . . . . . . . . 199
5.2.5 Datenhaltung . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.2.6 Vorgehensweise bei der Eingabe . . . . . . . . . . . . . . . 202
5.2.7 Verkehrsmodul . . . . . . . . . . . . . . . . . . . . . . . . 204

A Begriöslexikon 207

Literaturverzeichnis 210

Seite 7: vorherige Seite | nächste Seite | Übersicht

Kapitel 1

Vorwort

1.1 Die Projektgruppe im Informatikstudium

Eine Projektgruppe ist eine besondere Form der Lehrveranstaltung im Rahmen des Informatikstudiums. Sie vereinigt Seminar bzw. Hauptseminar (2 SWS), Fachpraktikum (4 SWS) und Studienarbeit (10 SWS) in einer thematisch durchgehenden Lehrveranstaltung über den Zeitraum eines Jahres (hierfür sind 16 SWS angesetzt). Während dieser Zeit arbeitet eine Gruppe von (etwa fünf) Studenten von der Erarbeitung theoretischer Grundlagen bis zur Implementierung eines lauöähigen Programms gemeinsam an einem zentralen Thema.

Dadurch können Ausbildungsziele verfolgt werden, die sich kleineren, in sich abgeschlossenen Lehrveranstaltungen von Natur aus nicht oder nur begrenzt erschlieflen:

- Arbeiten im Team

- Analyse von Problemen, Strukturierung von Lösungen und gemeinsamer Entwurf geeigneter Systeme

- Selbständige Erarbeitung von Lösungsvorschlägen und deren Vorstellung und Verteidigung in einer Gruppe

- Übernahme von Verantwortung für die Lösung von Teilaufgaben und die Erstellung von Modulen

- Mitwirkung an einer umfassenden Dokumentation

- Erstellen eines Software-Produktes, das ein Einzelner innerhalb des vorgegebenen Zeitraumes unmöglich bewältigen kann. Hierbei sollen sämtliche Phasen eines Software-Lifecycles >= von der Planung bis zur Wartung >= durchlaufen werden

- Projekt-Planung und Kosten/Nutzen-Analyse

- Einsatz von Werkzeugen

- Persönlichkeitsbildung (Übernahme von Verantwortung, Selbstvertrauen, Verläfllichkeit, Rücksichtnahme, Durchsetzungsfähigkeit usw.)

8

Seite 8: vorherige Seite | nächste Seite | Übersicht

1.1. DIE PROJEKTGRUPPE IM INFORMATIKSTUDIUM 9

Das Konzept der Projektgruppe wird bereits seit Jahren an anderen Universitäten wie z.B. in Oldenburg und Dortmund erprobt und durchgeführt. Dort sind Projektgruppen zum Teil schon PÄichtveranstaltungen im Rahmen des Informatikstudiums. An der Universität Stuttgart gibt es seit 1994 Projektgruppen im Fach Informatik. Im neu eingerichteten Studiengang Software-Technik ist die Teilnahme verbindlich vorgeschrieben.

Durch die eher kleine Teilnehmerzahl von 4 Studenten pro Projektgruppe (die ursprünglich für bis zu zehn Studierende vorgesehen war) können in der Praxis leider nicht alle Projektziele realisiert werden. Als ungünstig für die Teilnehmer hat sich auch erwiesen, dafl die Arbeit in vollem Umfang in der vorlesungsfreien Zeit weitergeführt werden soll, was zwangsläu?g zu Kollisionen mit Prüfungsvorbereitung und Urlaub führt. Der Ablauf der Projektgruppe ist in verschiedene Phasen unterteilt:

Seminarphase Zu Beginn des Projekts werden verschiedene, für die folgende Arbeit grundlegende Themen erarbeitet. Literaturrecherche sowie Aufarbeitung und Präsentation des Materials sind wesentliche Arbeitsschritte, die hierbei gelernt werden sollen.

Anforderungsanalyse Die Projektgruppe analysiert die Aufgabenstellung durch Diskussion mit dem Kunden sowie Erarbeitung verschiedener Möglichkeiten der Modellierung. Ziel dieser Phase ist es, ein möglichst genaues Bild der zu modellierenden Objekte aus der realen Welt zu bekommen, sowie alle Begriöe festzulegen und zu standardisieren. Damit kann im folgenden eine Abbildung auf Verfahren und Strukturen der Informatik erfolgen.

Spezi?kation Die jetzt genau bekannte Aufgabenstellung und Anforderung des Kunden wird modelliert. Dabei werden bekannte Problemlösungen aus der Literatur genauso gesammelt wie eigene Ideen. Abwägungen zwischen unterschiedlichen Ansätzen in Hinblick auf die gewünschten Eigenschaften des Ergebnisses (Flexibilität, Schnelligkeit, Erweiterbarkeit, etc.) müssen hier getroöen werden. Dabei soll eine möglichst genaue, in Teilen auch formale, Beschreibung des zu programmierenden Systems entstehen.

Entwurf Aufbauend auf die Spezi?kation werden hier die einzelnen Komponenten des Programms bis ins Detail beschrieben. Die verschiedenen Schnittstellen sowohl zum Benutzer als auch innerhalb des Programms werden genau festgelegt, ebenso die zu verwendenden Datenstrukturen und Algorithmen. Der Entwurf soll eine möglichst eindeutige Beschreibung des Programms darstellen und somit direkt als Vorlage für die Implementierung dienen. Alle wesentlichen Design-Entscheidungen, die bisher noch nicht getroöen werden, fallen im Entwurf.

Implementierung Nach Einarbeitung in eine Programmiersprache und zugehörige Entwicklungsumgebungen werden die Vorgaben von Spezi?kation und Entwurf konkret in Code umgesetzt.

Test Das lauöähige Programm wird bereits während der Codierung mit möglichst realistischen Daten getestet, um Programmfehler zu entdecken und die Handhabbarkeit zu prüfen.

Seite 9: vorherige Seite | nächste Seite | Übersicht

10 KAPITEL 1. VORWORT

Dokumentation/Präsentation Die gesamte Arbeit der Projektgruppe wird fortlaufend dokumentiert. Der Stand nach dem Entwurf (?Zwischenbericht?) sowie der Überblick über das gesamte Projekt (?Endbericht?) werden gedruckt und ähnlich einer Studienarbeit verööentlicht. Das Ergebnis der einjährigen Arbeit wird auflerdem in einer Präsentationsveranstaltung der interessierten Ööentlichkeit vorgeführt.

1.2 Die Aufgabenstellung

Neben den allgemeinen Lehrinhalten im Rahmen des Informatikstudiums hat diese Projektgruppe ein konkretes Ziel: Es soll ein Programm zur Verwaltung und Optimierung von sozialen Fahrdiensten entwickelt werden, das dann beim DRK in Stuttgart eingesetzt wird.

Das Programm soll alle für das DRK in Zusammenhang mit seinen Fahrdiensten wichtigen Daten erfassen und verwalten. Die momentan manuell durchgeführte Planung soll in Zukunft computergestützt ablaufen können, was den Planern beim DRK einen besseren Überblick über die Dienste und Einsatz von Mitarbeitern und Fahrzeugen liefern soll. Auflerdem ist vorgesehen, die Optimierung von Fahrdiensten auch automatisch auszuführen, um aufwendige Handarbeit einzusparen oder gar bessere Ergebnisse zu bekommen.

Zunächst wird das Programm also denjenigen Ausschnitt der realen Welt modellieren, der soziale Fahrdienste (und zwar ganz speziell aus Sicht des DRK Stuttgart) betriöt. Dabei geht die Anforderungsanalyse vom Ist-Zustand beim DRK aus, so dafl das Programm letztlich in der Lage ist, diesen möglichst exakt wiederzugeben.

Dennoch sollen einzelne Komponenten des Programms unabhängig austauschund erweiterbar sein. Durch Einsatz objektorientierter Analyse- und Designmethoden von der Spezi?kation bis zur Implementierung wird ein modularer Programmaufbau erreicht, der die einzelnen Komponenten weitgehend unabhängig voneinander und damit austauschbar macht.

Seite 10: vorherige Seite | nächste Seite | Übersicht