Folie SE II

Fakultät Wirtschafts- und Sozialwissenschaften
Professur für BWL, insbes. Wirtschaftsinformatik
Holstenhofweg 85
22043 Hamburg
SEII
16.05.09
Softwareentwicklung:
Frühjahrstrimester
2009
Projektarbeit
 Organisatorisches
 Problemstellungen
 SELibrary
 Organisatorisches (Fortsetzung)
Jens Czogalla
[email protected]
http://ifi.hsu-hh.de
Organisatorisches
Organisatorisches
 Zielgruppe: Studiengang BWL-Bachelor, 6. Trimester
 Formales Ziel der Vorlesung:

Abschlussklausur

Projektarbeit
 Umfang: 109 Stunden (Workload gem. Modulhandbuch)
1-2
Organisatorisches
Organisatorisches
 Materialien:

http://hsu-hh.de/ifi
 Grundlagen Windows Forms (Auswahl):

Webcasts (Bernd Marquardt):
http://www.microsoft.com/germany/msdn/webcasts/serien/MSDNWCS-0712-01.mspx

Online-Buch
http://openbook.galileocomputing.de/visual_csharp/

Online-Hilfe:
http://msdn.microsoft.com/de-de/default.aspx
1-3
Problemstellungen
Übersicht
Travelling Salesman Problem
Vehicle Routing Problem
SUDOKU
1-4
Travelling Salesman Problem
Problemstellung
Gesucht ist die kürzeste Tour (Rundreise) durch m Städte. Jede
Stadt soll genau einmal besucht werden. (vgl. GdWI Folie 4-36/37)
Anzahl der Städte m
Distanzmatrix C = (cij), i, j  {1,...,m}, i ≠ j
NP-schweres Optimierungsproblem (vgl. GdWI Folie 4-39)
Sehr viele Variationen der Problemstellung möglich
1-5
Travelling Salesman Problem
Beispiel
3
5
1
4
1
1
2
2
3
4
5
2,0
4,2
2,2
2,2
3,2
2,2
3,6
2,2
4,1
2
2,0
3
4,2
3,2
4
2,2
2,2
2,2
5
2,2
3,6
4,1
2,0
2,0
 Tourenplanung in der Logistik
 Design/Produktion von Leiterplatten
 Methoden der Bioinformatik (DNA-Sequenzierung)
1-6
Travelling Salesman Problem
Weitere Beispiele
7.397 Punkte auf PLA (1994)
15.112 Städte in Deutschland (2001)
[Quelle: http://www.tsp.gatech.edu]
1-7
Travelling Salesman Problem
Lösungsverfahren
Heuristiken




Nearest Neighbor (Nächster Nachbar)
Spanning Tree
Insertion
...
Meta-Heuristiken



Iterated Local Search (Iterative Lokale Suche)
Simulated Annealing
...
1-8
Travelling Salesman Problem
Quellen (kleine Auswahl)
Bücher:
Domschke, Logistik: Rundreisen und Touren. Oldenbourg Verlag, München,
1997.
Grünert und Irnich, Optimierung im Transport. Band II: Wege und Touren.
Shaker Verlag, Aachen, 2005.
Hußmann und Lutz-Westphal (Hrsg.) Kombinatorische Optimierung
erleben. Vieweg Verlag, Wiesbaden, 2007.
(Volltextzugang Campus: http://springerlink.com/content/x35k73)
Web:
Algorithmus der Woche:
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php
Englischsprachige TSP-Seite: http://www.tsp.gatech.edu//index.html
Visualisierung von TSP-Heuristiken:http://bjornson.inhb.de/?p=26
TSP-Spiel:http://www.tsp.gatech.edu/games/tspOnePlayer.html
1-9
Vehicle Routing Problem
Problemstellung
Gesucht ist die kürzeste Gesamtstrecke (Touren) bei der (alle)
Kunden aus Depots beliefert werden. Jeder Kunde ist genau einmal
zu besuchen. Ladekapazitäten der (identischen) Fahrzeuge sind
einzuhalten. (Verallgemeinertes Travelling Salesman Problem)
Capacitated Vehicle Routing Problem (CVRP)

1 Depot (Index 0)

n Kunden mit Bedarf bi (darf nicht gesplittet werden)
M identische Fahrzeuge mit Kapazität cap
Distanzmatrix C = (cij), i, j  {0,...,n}, i ≠ j

Minimierung der insgesamt zurückgelegten Entfernung

NP-schweres Optimierungsproblem


1-10
Vehicle Routing Problem
Beispiel
3
1
5
4
1
1
2
2
D
1
2
D
D
1
2
3
4
5
1,4
3,2
5,7
3,6
3,0
2,0
4,2
2,2
2,2
3,2
2,2
3,6
2,2
4,1
1
1,4
2
3,2
2,0
3
5,7
4,2
3,2
4
3,6
2,2
2,2
2,2
5
3,0
2,2
3,6
4,1
2,0
2,0
3
1-11
Vehicle Routing Problem
Lösungsverfahren
Heuristiken




Sweep
Petal
Saving
...
Meta-Heuristiken



Iterated Local Search (Iterative Lokale Suche)
(Simulated Annealing)
...
1-12
Vehicle Routing Problem
Quellen (kleine Auswahl)
Bücher:
Domschke, Logistik: Rundreisen und Touren. Oldenbourg Verlag, München,
1997.
Grünert und Irnich, Optimierung im Transport. Band II: Wege und Touren.
Shaker Verlag, Aachen, 2005.
Web:
Visualisierung Route Planning:
http://www.dna-evolutions.com/dnaappletsample.html
1-13
SUDOKU
Problemstellung
Ein 9x9 Gitter ist so zu füllen, dass jede Ziffer in einer Spalte, in
einer Zeile und in einem Block genau einmal vorkommt.
1
9
2
6
6
7
6
3
3
5
9
1
8
9
7
8
7
6
6
8
4
8
6
3
2
8
2
5
1
1
4
6
3
8
9
1-14
SUDOKU
Lösungsmöglichkeit
2
6
5
1 2 3 1 2 3
4 5 6 4 5 6
1
9
7
1 2 3 1 2 3
6
3
4 5 6
7 8 9
9
3
5
9
1
8
7 8 9 7 8 9
1 2 3
6
6
7 8 9 7 8 9
4 5 6 4 5 6
2
9
7
8
7
6
6
8
4
8
6
3
2
8
2
5
1
1
4
6
3
8
9
1-15
SUDOKU
Lösungsmöglichkeit
2
6
5
Block
1 2 3 1 2 3
4 5 6 4 5 6
1
9
7
1 2 3 1 2 3
6
3
4 5 6
7 8 9
9
3
5
9
1
8
7 8 9 7 8 9
1 2 3
6
6
7 8 9 7 8 9
4 5 6 4 5 6
2
9
7
8
7
6
6
8
4
8
6
3
2
8
2
5
1
1
4
6
3
8
9
1-16
SUDOKU
Lösungsmöglichkeit
2
6
5
Zeile
1 2 3 1 2 3
4 5 6 4 5 6
1
9
7
1 2 3 1 2 3
6
3
4 5 6
7 8 9
9
3
5
9
1
8
7 8 9 7 8 9
1 2 3
6
6
7 8 9 7 8 9
4 5 6 4 5 6
2
9
7
8
7
6
6
8
4
8
6
3
2
8
2
5
1
1
4
6
3
8
9
1-17
SUDOKU
Lösungsmöglichkeit
2
6
5
Spalte
1 2 3 1 2 3
4 5 6 4 5 6
1
9
7
1 2 3 1 2 3
6
3
4 5 6
7 8 9
9
3
5
9
1
8
7 8 9 7 8 9
1 2 3
6
6
7 8 9 7 8 9
4 5 6 4 5 6
2
9
7
8
7
6
6
8
4
8
6
3
2
8
2
5
1
1
4
6
3
8
9
1-18
SUDOKU
Lösungsmöglichkeit
2
6
5
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 8 9
7
1
9
7
1
6
3
2
7
6
1
5
9
1
8
6
3
9
7
8
7
6
9
6
8
4
8
6
3
2
8
2
5
1
1
4
6
3
8
9
1-19
SUDOKU
Quellen (kleine Auswahl)
Web:
SUDOKU-Lobby:
http://www.sudoku-lobby.de/
Mathematische Basteleien:
http://www.mathematische-basteleien.de/sudoku.htm
Sudoku lösen:
http://arbeitsblaetter.stangl-taller.at/GEDAECHTNIS/Sudoku.shtml
1-20
SELibrary
Klassendiagramm
1-21
SELibrary
Verwendung
1-22
SELibrary
Verwendung
using SELibrary;
...
class TSP : BaseTSP
{
}
1-23
SELibrary
Verwendung
TSP tsp = new TSP();
string file = @“C:\a280.tsp“;
bool isLoaded = tsp.Load(file);
// foreach-Schleife über alle Städte
foreach (Depot city in tsp) …
// Zugriff auf einzelne Stadt
tsp[1].X …
1-24
Organisatorisches
Organisatorisches
 Gruppenarbeit in 2er/3er Teams
 Termine:

Aufgabenvergabe

1. Zwischenbesprechung


Erläuterung Aufgabenstellung

Lösungsansatz (Klassendesign)
2. Zwischenbesprechung


Offene Fragen
Abgabe der Projektarbeit
und Präsentation
1-25
Organisatorisches
Erwartungen
 Objektorientiertes Design
 Implementierung der geforderten Algorithmen
 Grafische Visualisierung der Lösung (für Fortgeschrittene)
 Projektarbeit (schriftliche Ausarbeitung) & Präsentation
1-26
Organisatorisches
Projekte
 Travelling Salesman Problem

Nearest Neighbor (Nächster Nachbar) Heuristik und Verbesserung
der Tour durch Simulated Annealing (2-opt Nachbarschaft)

(Cheapest) Insertion (Einfüge) Heuristik und Verbesserung der Tour
durch Iterated Local Search (2-opt Nachbarschaft)

Patching Heuristik
 Vehicle Routing Problem

Sweep Heuristik

Savings Heuristik
 SUDOKU

Lösungsverfahren gem. Folien 15-19
1-27