Grundlegende Algorithmen des Travelling Salesman Problems (TSP)
©2001
Diplomarbeit
171 Seiten
Zusammenfassung
Inhaltsangabe:Problemstellung:
Das Travelling-Salesman-Problem (TSP), auch bekannt als Problem des Handelsreisenden, ist wohl das am meisten beachtete Optimierungsproblem aus dem Bereich des Operations Research. Hierbei soll ein Handelsreisender, ausgehend von einem beliebigem Startort x0, n verschiedene Städte genau einmal bereisen und anschließend wieder an den Startort x0 zurückkehren. Aus den insgesamt n! möglichen Touren soll nun die kürzeste Rundreise ermittelt werden, wobei die Entfernungen der einzelnen Orte zum Startort sowie zueinander bekannt sind.
Das Kernproblem des TSP liegt im nicht ponentiellen Wachstum der möglichen Touren bei steigender Anzahl der zu bereisenden Orte, so dass verschiedene Algorithmen zum Einsatz kommen, die versuchen, sich dem Optimum so schnell wie möglich anzunähern.
In der hier vorliegenden Arbeit sollen nun einige auserwählte Algorithmen in Visual Basic 6.0 umgesetzt werden, wobei darauf hingewiesen wird, daß es sich um rein symetrische TSPs handelt.
Gang der Untersuchung:
Zunächst werden im Abschnitt 2 wichtige Definitionen für das Verständnis der angewandten Algorithmen dargelegt und näher erläutert. Anschließend werden im dritten Abschnitt dieser Arbeit die umgesetzten Algorithmen behandelt.
Abschnitt 4 bildet den eigentlichen Kern der Arbeit. Hierin werden die Hauptprozeduren des Visual Basic-Programms in Form von Struktogrammen visualisiert und ausgiebig erläutert.
Im fünften Abschnitt werden ausgehend von einem Rundreisebeispiel mit 25 Elementen, Ergebnisse und Rechenzeiten der hier vorgestellten Algorithmen tabellarisch festgehalten und bewertet.
Der sechste und letzte Abschnitt dieser Arbeit dient der persönlichen Reflexion der bearbeiteten Thematik.
Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung3
2.Grundlegende Definitionen4
2.1Metrik als allgemeiner Abstand4
2.2Euklidischer Abstand5
2.3Potential eines Ortes5
2.4Savingwert6
2.5Permutationen7
2.6Längenbetrachtungen7
2.7Mittelwert8
2.8Standardabweichung8
2.9Bewertung nach Chebychev-Markov übertragen auf das TSP9
3.Kurzpräsentation der angewandten Verfahren10
3.1Algorithmus des besten Nachbarn12
3.2Inselalgorithmus13
3.3Vollenumeration14
3.4Anmerkung zur Länge einer Tour15
4.Visual Basic 6.0 Programm16
4.1Datenbankentwurf16
4.2Datenbankzugriff17
4.3Datenbankmanipulation18
4.3.1Elemente hinzufügen18
4.3.2Elemente entfernen20
4.4Klassenmodul Tourenverkettung21
4.5Algorithmen24
4.5.1Algorithmus des besten […]
Das Travelling-Salesman-Problem (TSP), auch bekannt als Problem des Handelsreisenden, ist wohl das am meisten beachtete Optimierungsproblem aus dem Bereich des Operations Research. Hierbei soll ein Handelsreisender, ausgehend von einem beliebigem Startort x0, n verschiedene Städte genau einmal bereisen und anschließend wieder an den Startort x0 zurückkehren. Aus den insgesamt n! möglichen Touren soll nun die kürzeste Rundreise ermittelt werden, wobei die Entfernungen der einzelnen Orte zum Startort sowie zueinander bekannt sind.
Das Kernproblem des TSP liegt im nicht ponentiellen Wachstum der möglichen Touren bei steigender Anzahl der zu bereisenden Orte, so dass verschiedene Algorithmen zum Einsatz kommen, die versuchen, sich dem Optimum so schnell wie möglich anzunähern.
In der hier vorliegenden Arbeit sollen nun einige auserwählte Algorithmen in Visual Basic 6.0 umgesetzt werden, wobei darauf hingewiesen wird, daß es sich um rein symetrische TSPs handelt.
Gang der Untersuchung:
Zunächst werden im Abschnitt 2 wichtige Definitionen für das Verständnis der angewandten Algorithmen dargelegt und näher erläutert. Anschließend werden im dritten Abschnitt dieser Arbeit die umgesetzten Algorithmen behandelt.
Abschnitt 4 bildet den eigentlichen Kern der Arbeit. Hierin werden die Hauptprozeduren des Visual Basic-Programms in Form von Struktogrammen visualisiert und ausgiebig erläutert.
Im fünften Abschnitt werden ausgehend von einem Rundreisebeispiel mit 25 Elementen, Ergebnisse und Rechenzeiten der hier vorgestellten Algorithmen tabellarisch festgehalten und bewertet.
Der sechste und letzte Abschnitt dieser Arbeit dient der persönlichen Reflexion der bearbeiteten Thematik.
Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung3
2.Grundlegende Definitionen4
2.1Metrik als allgemeiner Abstand4
2.2Euklidischer Abstand5
2.3Potential eines Ortes5
2.4Savingwert6
2.5Permutationen7
2.6Längenbetrachtungen7
2.7Mittelwert8
2.8Standardabweichung8
2.9Bewertung nach Chebychev-Markov übertragen auf das TSP9
3.Kurzpräsentation der angewandten Verfahren10
3.1Algorithmus des besten Nachbarn12
3.2Inselalgorithmus13
3.3Vollenumeration14
3.4Anmerkung zur Länge einer Tour15
4.Visual Basic 6.0 Programm16
4.1Datenbankentwurf16
4.2Datenbankzugriff17
4.3Datenbankmanipulation18
4.3.1Elemente hinzufügen18
4.3.2Elemente entfernen20
4.4Klassenmodul Tourenverkettung21
4.5Algorithmen24
4.5.1Algorithmus des besten […]
Leseprobe
Inhaltsverzeichnis
ID 4387
Spreitzer, Stefan: Grundlegende Algorithmen des Travelling Salesman Problems (TSP) / Stefan
Spreitzer - Hamburg: Diplomica GmbH, 2001
Zugl.: Heide, Fachhochschule für Wirtschaft und Technik, Diplom, 2001
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte, insbesondere die
der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von Abbildungen und Tabellen,
der Funksendung, der Mikroverfilmung oder der Vervielfältigung auf anderen Wegen und der
Speicherung in Datenverarbeitungsanlagen, bleiben, auch bei nur auszugsweiser Verwertung,
vorbehalten. Eine Vervielfältigung dieses Werkes oder von Teilen dieses Werkes ist auch im
Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der
Bundesrepublik Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem
Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche
Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten
wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können Fehler nicht
vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die Autoren oder
Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.
verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2001
Printed in Germany
Wissensquellen gewinnbringend nutzen
Qualität, Praxisrelevanz und Aktualität zeichnen unsere Studien aus. Wir
bieten Ihnen im Auftrag unserer Autorinnen und Autoren Wirtschafts-
studien und wissenschaftliche Abschlussarbeiten Dissertationen,
Diplomarbeiten, Magisterarbeiten, Staatsexamensarbeiten und Studien-
arbeiten zum Kauf. Sie wurden an deutschen Universitäten, Fachhoch-
schulen, Akademien oder vergleichbaren Institutionen der Europäischen
Union geschrieben. Der Notendurchschnitt liegt bei 1,5.
Wettbewerbsvorteile verschaffen Vergleichen Sie den Preis unserer
Studien mit den Honoraren externer Berater. Um dieses Wissen selbst
zusammenzutragen, müssten Sie viel Zeit und Geld aufbringen.
http://www.diplom.de bietet Ihnen unser vollständiges Lieferprogramm
mit mehreren tausend Studien im Internet. Neben dem Online-Katalog und
der Online-Suchmaschine für Ihre Recherche steht Ihnen auch eine Online-
Bestellfunktion zur Verfügung. Inhaltliche Zusammenfassungen und
Inhaltsverzeichnisse zu jeder Studie sind im Internet einsehbar.
Individueller Service
Gerne senden wir Ihnen auch unseren Papier-
katalog zu. Bitte fordern Sie Ihr individuelles Exemplar bei uns an. Für
Fragen, Anregungen und individuelle Anfragen stehen wir Ihnen gerne zur
Verfügung. Wir freuen uns auf eine gute Zusammenarbeit.
Ihr Team der Diplomarbeiten Agentur
Inhaltsverzeichnis
1
Inhaltsverzeichnis
1. Einleitung... 3
2. Grundlegende Definitionen ... 4
2.1 Metrik als allgemeiner Abstand... 4
2.2 Euklidischer Abstand ... 5
2.3 Potential eines Ortes ... 5
2.4 Savingwert... 6
2.5 Permutationen ... 7
2.6 Längenbetrachtungen... 7
2.7 Mittelwert ... 8
2.8 Standardabweichung ... 8
2.9 Bewertung nach Chebychev-Markov übertragen auf das TSP ... 9
3. Kurzpräsentation der angewandten Verfahren... 10
3.1 Algorithmus des besten Nachbarn... 12
3.2 Inselalgorithmus ... 13
3.3 Vollenumeration... 14
3.4 Anmerkung zur Länge einer Tour ... 15
4. Visual Basic 6.0 Programm ... 16
4.1 Datenbankentwurf ... 16
4.2 Datenbankzugriff ... 17
4.3 Datenbankmanipulation ... 18
4.3.1 Elemente hinzufügen... 18
4.3.2 Elemente entfernen ... 20
4.4 Klassenmodul Tourenverkettung ... 21
4.5 Algorithmen ... 24
4.5.1 Algorithmus des besten Nachbarn... 24
4.5.2 Inselalgorithmus ... 27
4.5.3 Vollenumeration... 30
4.6 Wartungs- und Änderungsdienst ... 32
Inhaltsverzeichnis
2
Inhaltsverzeichnis
5. Rundreisebeispiel mit 25 Elementen... 33
6. Schlußbetrachtungen ... 35
Literaturverzeichnis ... 36
Anhang ... 37
Kapitel 1 : Einleitung
3
1. Einleitung
Das ,,Travelling-Salesman-Problem" (TSP), auch bekannt als ,,Problem des
Handelsreisenden", ist wohl das am meisten beachtete Optimierungsproblem
aus dem Bereich des Operations Research.
Hierbei soll ein Handelsreisender, ausgehend von einem beliebigem Startort x
0
,
n verschiedene Städte genau einmal bereisen und anschließend wieder an den
Startort x
0
zurückkehren. Aus den insgesamt n! möglichen Touren soll nun die
kürzeste Rundreise ermittelt werden, wobei die Entfernungen der einzelnen
Orte zum Startort sowie zueinander bekannt sind.
Das Kernproblem des TSP liegt im nicht potentiellen Wachstum der möglichen
Touren bei steigender Anzahl der zu bereisenden Orte, so dass verschiedene
Algorithmen zum Einsatz kommen, die versuchen, sich dem Optimum so
schnell wie möglich anzunähern.
In der hier vorliegenden Arbeit sollen nun einige auserwählte Algorithmen in
Visual Basic 6.0 umgesetzt werden, wobei darauf hingewiesen wird, daß es
sich um rein symetrische TSP's handelt.
Zunächst werden im Abschnitt 2 wichtige Definitionen für das Verständnis der
angewandten Algorithmen dargelegt und näher erläutert. Anschließend werden
im dritten Abschnitt dieser Arbeit die umgesetzten Algorithmen behandelt.
Abschnitt 4 bildet den eigentlichen Kern der Arbeit. Hierin werden die
Hauptprozeduren des Visual Basic-Programms in Form von Struktogrammen
visualisiert und ausgiebig erläutert.
Im fünften Abschnitt werden ausgehend von einem Rundreisebeispiel mit 25
Elementen, Ergebnisse und Rechenzeiten der hier vorgestellten Algorithmen
tabellarisch festgehalten und bewertet.
Der sechste und letzte Abschnitt dieser Arbeit dient der persönlichen Reflexion
der bearbeiteten Thematik.
Kapitel 2 : Grundlegende Definitionen
4
2. Grundlegende Definitionen
Nachfolgend werden wesentliche Begriffe und Methoden erläutert, welche zum
Verständnis der eingesetzten Algorithmen unverzichtbar sind.
Die Überlegungen dieses und des nächsten Kapitels stützen sich auf die
Schwerpunktveranstaltung ,,Wirtschaftsinformatik" der Fachhochschule
Westküste.
2.1 Metrik als allgemeiner Abstand
Sei K eine Menge von Orten x
0
,...,x
n
und d eine Abbildung, die zwei Punkten x,y
K genau eine positive Zahl d (x,y) zuordnet. Dann heißt d Metrik genau dann,
wenn folgende Eigenschaften erfüllt sind :
(2-01)
0
)
,
(
=
=
y
x
d
y
x
(2-02)
)
,
(
)
,
(
x
y
d
y
x
d
=
(2-03)
)
,
(
)
,
(
)
,
(
y
z
d
z
x
d
y
x
d
+
.
Erläuterung der Eigenschaften:
1.) Die Punkte x und y sind genau dann gleich, wenn der Abstand zwischen
ihnen gleich null ist.
2.) In der zweiten Eigenschaft der Metrik wird die Symmetrie definiert, das
heißt der Abstand von x zu y ist gleich dem Abstand von y zu x.
3.) Die Dreiecksungleichung der dritten Eigenschaft besagt, dass der
Abstand von x zu y kürzer bzw. gleich dem Abstand von x zu z plus dem
Abstand von z zu y sein muss.
Kapitel 2 : Grundlegende Definitionen
5
n
b
a
,
2.2 Euklidischer Abstand
x
||a-b||
||a||
||b||
y
Abb1.: Euklidischer Abstand
Der Euklidische Abstand beschreibt den Abstand zweier Vektoren und läßt sich
folgendermaßen berechnen :
(2-04)
(
)
=
-
=
-
n
k
k
k
b
a
b
a
1
2
||
||
.
Die Entfernungsmatrix des zugrundeliegenden Travelling Salesman Problems
läßt sich anhand der Formel des Euklidischen Abstandes aufbauen und bildet
die Basis für alle weiteren Berechnungsschritte.
2.3 Potential eines Ortes
Als Potential eines Ortes x
K wird dessen Abstand zum Start- und Zielort x
0
bezeichnet.
(2-05)
)
,
(
)
(
0
x
x
d
x
p
=
Kapitel 2 : Grundlegende Definitionen
6
2.4 Savingwert
Bevor die Defintion des Savingwertes dargelegt wird, soll zunächst einmal
aufgezeigt werden, wie verschiedene Orte innerhalb einer Tour bereist werden
können.
Der Handelsreisende H soll, wie nachfolgend in Abb.2 ersichtlich, ausgehend
vom Start- und Zielort x
0
die Orte x
1
und x
2
bereisen und wieder nach x
0
zurückkehren.
Abb.2 : Bereisung von zwei Orten
Es seien nun zwei Alternativen aufgezeigt :
1.) Tour-unklug
:
x
0
x
1
x
0
x
2
x
0
2.) Tour-klug
:
x
0
x
1
x
2
x
0
Tour 1 setzt sich aus den Potentialen von x
1
und x
2
zusammen, so dass die
Länge der Tour folgendermaßen formuliert werden kann :
(2-06) Unkluge Tourenlänge
:
)
(
)
(
)
(
)
(
2
2
1
1
x
p
x
p
x
p
x
p
+
+
+
.
Die Länge der Tour 2 setzt sich wie folgt zusammen :
(2-07) Kluge Tourenlänge
:
)
(
)
,
(
)
(
2
2
1
1
x
p
x
x
d
x
p
+
+
.
Der Savingwert S sei nun definiert als Ersparnis aus den beiden Ansätzen Tour-
unklug und Tour-klug, das heißt es ist die Länge der Tour-klug von der Länge
der Tour-unklug zu subtrahieren. Es ergibt sich der Savingwert S :
(2-08)
)
,
(
)
(
)
(
)
,
(
2
1
2
1
2
1
x
x
d
x
p
x
p
x
x
s
-
+
=
.
x
0
: Start- und Zielort
x
0
x
1
x
1
, x
2
: zu bereisende Orte
x
2
Kapitel 2 : Grundlegende Definitionen
7
Aufgrund der bisherigen Erläuterungen lassen sich folgende Eigenschaften des
Savingwertes festhalten :
(2-09)
)
(
2
)
,
(
i
i
i
x
p
x
x
s
=
(2-10)
)
,
(
)
,
(
i
j
j
i
x
x
s
x
x
s
=
(2-11)
0
)
,
(
j
i
x
x
s
.
Im folgenden wird die Notation dahingehend vereinfacht, daß der Ausdruck
s(x
i
,x
j
) durch den Ausdruck s
ij
und der Ausdruck d(x
i
,x
j
) durch den Ausdruck d
ij
ersetzt werden.
2.5 Permutationen
Jede Tour kann als Permutation von
{
1,...,n
}
identifiziert werden, wobei
als
die Menge aller Permutationen von
{
1,...,n
}
definiert ist.
Nachstehende Formel beschreibt die Gewichtung einer Permutation bezogen
auf die Gesamtmenge der Permutationen
:
(2-12)
{ }
!
1
)
(
n
P
=
.
2.6 Längenbetrachtungen
Die Länge einer Tour kann wie folgt dargestellt werden :
(2-13)
-
=
+
+
+
=
1
1
)
1
(
),
(
)
(
)
1
(
)
(
n
k
k
k
n
d
p
p
L
für alle
.
Die Savinglänge einer Tour kann folgendermaßen formuliert werden :
(2-14)
-
=
+
=
1
1
)
1
(
),
(
)
(
n
k
k
k
s
S
für alle
.
Kapitel 2 : Grundlegende Definitionen
8
Der Zusammenhang der beiden Formeln lässt sich anhand des nachstehenden
Ausdrucks nachvollziehen :
(2-15)
( )
S
p
L
n
k
k
2
1
-
=
=
für alle
.
2.7 Mittelwert
Der Mittelwert einer Tour kann wie folgt berechnet werden :
(2-16)
=
=
+
=
n
j
i
j
i
j
i
n
k
k
d
n
p
n
L
IE
1
,
,
1
1
2
)
(
.
2.8 Standardabweichung
Die Standardabweichung bezeichnet den mittleren Abstand zur mittleren
Tourenlänge und lässt sich nachstehendem Ausdruck entnehmen :
(2-17)
=
=
=
=
-
-
-
+
=
n
i
n
j
i
j
j
i
n
j
i
j
i
j
i
n
j
i
j
i
j
i
s
n
n
s
n
n
s
n
S
1
2
1
,
2
1
,
,
2
1
,
2
,
2
)
1
(
2
)
1
(
1
1
)
(
.
Kapitel 2 : Grundlegende Definitionen
9
2.9 Bewertung nach Chebychev-Markov übertragen auf das TSP
Die Güte einer ermittelten Tour kann mit Hilfe folgender Formel abgeschätzt
werden :
(2-18)
{
}
(
)
-
-
+
-
-
-
>
-
-
=
=
=
=
)
(
2
)
(
)
(
1
)
(
)
(
1
)
(
2
)
(
)
(
2
)
(
2
1
2
2
1
2
1
1
L
IE
p
L
L
IE
alle
für
L
L
IE
L
IE
p
L
L
IE
alle
für
p
L
IE
p
L
P
n
k
i
n
k
i
n
k
i
n
k
i
.
Kapitel 3 : Kurzpräsentation der angewandten Verfahren
10
3. Kurzpräsentation der angewandten Verfahren
In diesem Abschnitt werden die in Visual Basic umgesetzten Algorithmen
mathematisch kurz dargestellt. Ausgangspunkt aller Algorithmen stellt die
sogenannte Savingliste dar.
Ausgehend von der Entfernungsmatrix wird eine Savingmatrix aufgestellt, die
jeweils die Savingwerte in Bezug zum Ausgangsort repräsentiert. In der
Savingliste werden die Savingwerte der Größe nach absteigend sortiert.
Das nachfolgende Beispiel veranschaulicht die Schritte bis zur Entstehung der
Savingliste. Für das Beispiel repräsentiert ,,A" den Startort x
0
der Tour und die
Elemente ,,B,...,F" stellen die zu bereisenden Orte x
1
,...,x
n
dar.
Bsp. :
Bildung einer Savingliste
1.) Entfernungsmatrix
Startort A B C D E F
A
0 12 4 10 10
19
B
12 0 14 8 22 14
C
4 14 0 6 8 15
D
10 8 6 0 14
9
E
10 22 8 14 0 20
F
19 14 15 9 20 0
Aus der Entfernungsmatrix werden nun die Savingwerte ermittelt und in die
Savingmatrix eingetragen.
2.) Savingmatrix
Startort B C D E F
B 24
2
14
0
17
C
2 8 8 6 8
D 14
8
20
6
20
E 0
6
6
20
9
F 17
8
20
9
38
Kapitel 3 : Kurzpräsentation der angewandten Verfahren
11
14
)
,
(
8
12
10
)
,
(
)
,
(
)
(
)
(
)
,
(
=
-
+
=
-
+
=
B
D
s
B
D
s
B
D
d
B
p
D
p
B
D
s
Die Berechnung der Savingwerte soll einmal exemplarisch am Wert ,,14" des
Ortepaares ,,DB" verdeutlicht werden :
(3-01)
Die Savingwerte werden nun der Größe nach in einer Liste erfasst (aufgrund
der Symmetrie halbiert sich die Liste).
3.) Savingliste
Index Ortepaar Savingwert
1 FD 20
2 FB 17
3 DB 14
4 FE 9
5 DC 8
6 FC 8
7 EC 6
8 ED 6
9 CB 2
10 EB
0
Anhand der Savingliste werden Ortepaare entsprechend des angewandten
Verfahrens sukzessive zusammengesetzt bis die Tour komplett ist.
Kapitel 3 : Kurzpräsentation der angewandten Verfahren
12
3.1 Algorithmus des besten Nachbarn
Die grundlegende Idee des Algorithmus' ist ausgehend von einem Ort den
jeweils besten (kürzesten) nächsten Ort zu bereisen. Von dem neu gefundenen
Ort ausgehend wird nun der nächstbestgelegene Ort angereist u.s.w. .
Übertragen auf das vorangestellte Beispiel bedeutet dies folgendes :
1.)
Nehme das Ortepaar mit dem größten Savingwert (FD)
2.)
Durchlaufe die Savingliste zum nächsten Ortepaar, welches sich an
das bereits vorhandene links oder rechts anketten läßt (FB) und führe
die Tour fort (BFD)
3.)
Wiederhole Schritt 2 bis die Tour komplett ist (BFDCE)
4.)
Von den jeweiligen Endpunkten führt die Tour zum Ausgangspunkt
zurück, so daß schließlich die gesuchte Rundreise entstanden ist (A-
BFDCE-A).
Kapitel 3 : Kurzpräsentation der angewandten Verfahren
13
3.2 Inselalgorithmus
Der Inselalgorithmus ist eine Erweiterung des Algorithmus des besten
Nachbarn. Hier werden Ortepaare auch dann berücksichtigt, wenn sie nicht an
das Ausgangsortepaar angekettet werden konnten. Es entstehen dadurch
sogenannte Inseln, an die jeweils wieder Ortepaare angekettet werden können.
Durch diese Erweiterung werden mehr größere Savingwerte berücksichtigt als
beim Algorithmus des besten Nachbarn.
Am Beispiel verdeutlicht ergeben sich folgende Schritte bis zur Ermittlung der
Tour :
1.)
Nehme das Ortepaar mit dem größten Savingwert (FD)
2.)
Nehme das Ortepaar mit dem nächstgrößten Savingwert (FB) und
prüfe ob eine Ankettung an bisheriges Ortepaar (FD) möglich ist. Ist
dies der Fall so erfolgt die Ankettung und die Tour wird fortgeführt
(BFD). Ist dies nicht der Fall so deklariere das Ortepaar als Insel.
3.)
Nehme das Ortepaar mit dem nächstgrößten Savingwert und prüfe :
a) Ankettung an Ausgangsortepaar möglich (falls ja erfolgt die
Ankettung)
b) Ankettung an vorhandene Inseln möglich (falls ja erfolgt die
Ankettung)
c) Kann das Ortepaar eine Insel mit dem Ausgangsortepaar
verbinden (falls ja erfolgt die Verkettung)
d) Kann das Ortepaar zwei Inseln (falls vorhanden) miteinander
verbinden (falls ja erfolgt die Verkettung)
e) Fallen a) ,b), c) und d) negativ aus, so deklariere Ortepaar als
neue Insel
4.)
Wiederhole Schritt 3 bis die Tour komplett ist (BFDCE)
5.)
Von den jeweiligen Endpunkten führt die Tour zum Ausgangspunkt
zurück, so daß schließlich die gesuchte Rundreise entstanden ist (A-
BFDCE-A).
Kapitel 3 : Kurzpräsentation der angewandten Verfahren
14
Bei der Durchführung der hier vorgestellten Algorithmen muß darauf geachtet
werden, daß eine gebildete Teilkette nicht geschlossen wird, bevor nicht alle zu
bereisenden Orte integriert wurden.
3.3 Vollenumeration
Innerhalb der Vollenumeration wird jede mögliche Tour zusammengestellt.
Basierend auf dem Eingangsbeispiel wären 5! = 120 Touren möglich (A steht
als Start- und Zielpunkt fest). Es werden also 120 Touren aufgestellt und die
kürzeste ermittelt.
Das Kernproblem der Vollenumeration besteht in der nicht ponentiell
ansteigenden Zahl der möglichen Touren bei steigender Anzahl der zu
bereisenden Orte (vgl. Kapitel 1 : Einleitung), so daß vorhandene
Rechnerkapazitäten schnell ausgelastet sein können.
Zudem spielt aus betriebswirtschaftlicher Sicht der Zeitfaktor eine
entscheidende Rolle, so daß die Vollenumeration zur Ermittlung der kürzesten
Tour entfällt. Vielmehr gilt es einen Algorithmus zu finden, der sich so weit wie
möglich an das Optimum annähert und das Ergebnis in einer angemessenen
Zeitspanne präsentieren kann.
Kapitel 3 : Kurzpräsentation der angewandten Verfahren
15
3.4 Anmerkung zur Länge einer Tour
Bezugnehmend auf das Kapitel 2.6 : Längenbetrachtungen kann die Länge
einer Tour auf zwei verschiedene Arten berechnet werden. Zum Einen können
die jeweiligen Potentiale aus der Entfernungsmatrix aufsummiert werden
(Variante 1) und zum Anderen kann die Länge einer Tour retrograd aus den
ermittelten Savingwerten ermittelt werden (Variante 2).
Beide Varianten seien am Eingangsbeispiel demonstriert :
Variante 1:
(3-04) Tour :
T = A-BFDCE-A
Länge
:
)
(
)
,
(
)
,
(
)
,
(
)
,
(
)
(
)
(
E
p
E
C
d
C
D
d
D
F
d
F
B
d
B
p
L
T
+
+
+
+
+
=
59
10
8
6
9
14
12
=
+
+
+
+
+
=
Variante 2 :
(3-05) Tour :
T = A-BFDCE-A
Länge
:
=
-
=
n
i
T
i
T
S
x
p
L
1
)
(
)
(
)
(
2
(
)
=
+
+
+
+
+
=
n
i
i
F
p
E
p
D
p
C
p
B
p
A
p
x
p
1
)
(
)
(
)
(
)
(
)
(
)
(
2
)
(
2
(
)
110
19
10
10
4
12
0
2
=
+
+
+
+
+
=
)
,
(
)
,
(
)
,
(
)
,
(
)
(
E
C
s
C
D
s
D
F
s
F
B
s
S
T
+
+
+
=
51
6
8
20
17
=
+
+
+
=
59
51
110
=
-
=
T
L
Kapitel 4 : Visual Basic 6.0 Programm
16
4. Visual Basic 6.0 Programm
In diesem Abschnitt werden die wesentlichen Elemente des Visual Basic 6.0
Programms näher erläutert und hinreichend kommentiert. Das Programm erfüllt
folgendes Anforderungsprofil :
1.)
Ausgehend von einer bestehenden Datenbanktabelle ist eine variable
Auswahl von Daten für die durchzuführende Berechnung möglich
2.) Desweiteren können beliebig viele Datenbanktabellenelemente
hinzugefügt oder entfernt werden.
3.) Die ausgewählten Elemente können von den in Abschnitt 3
deklarierten Verfahren zur Berechnung genutzt werden.
4.)
Die Ergebnisse der angewandten Verfahren werden auf Basis der
allgemeinen Abschätzung nach Chebychev-Markov statistisch
ausgewertet.
5.)
Aufgrund der angewandten Menüstruktur innerhalb des Programms
ist eine spätere Ergänzung der Berechnungsverfahren unter Nutzung
der bis dato gewonnenen Erkenntnisse möglich.
Hinweis : Um eine optimale Darstellung des Programms zur Laufzeit zu
gewährleisten, sollte die Bildschirmauflösung auf 1024x768 Pixel eingestellt
sein.
4.1 Datenbankentwurf
Die Basis des Visual Basic 6.0 Programms besteht aus einer Datenbanktabelle
in MSAccess 2000 mit dem Namen ,,Entfernungsmatrix". Die Tabelle setzt sich
aus den Spalten ,,ID", ,,Startort" sowie je einer Spalte mit der entsprechenden
Elementbezeichnung zusammen. Die Spalte ,,ID" bildet innerhalb der Tabelle
den primary Key und weist jedem Datensatz eine eindeutige Kennzeichnung in
Form einer fortlaufenden Nummer zu. In der Spalte ,,Startort" werden die
entsprechenden Elementbezeichnungen (dieselben Bezeichnungen wie in den
Spaltenbezeichnungen) eingetragen. Bei der Namensgebung muß darauf
geachtet werden, daß die Bezeichnung keinerlei Sonderzeichen enthält, da
Kapitel 4 : Visual Basic 6.0 Programm
17
diese von dem im Programm eingesetzten SQL-Befehlen nicht unterstützt
werden.
Die übrigen Spalten sind vom Datentyp integer und enthalten die jeweiligen
Daten, welche die Beziehungen der Elemente zueinander angeben.
4.2 Datenbankzugriff
Die Verbindung zur MSAccess-Datenbank wird durch das Connection-Objekt
aus der ADO 2.1 Libary hergestellt. Die wichtigsten Eigenschaften dieses
Objektes sind die Provider-Eigenschaft und die ConnectionString-Eigenschaft.
Die Provider-Eigenschaft stellt die zu unterstützenden Datenbanktreiber zur
Verfügung. In diesem Programm wurde der ,,Microsoft.Jet.OLEDB.4.0"-Provider
verwendet, da es sich bei der MSAccess-Datenbank um eine Microsoft Jet-
Datenbank handelt. Die ConnectionString-Eigenschaft enthält die komplette
Pfadbezeichnung der zu benutzenden Datenquelle.
Innerhalb des Programms wurde ein CommonDialog-Objekt verwendet, um die
Adresse der Datenquelle zu ermitteln.
Nachdem die Verbindung zur Datenbank mit der Open-Methode des
Connection-Objektes realisiert wurde, wird das Recordset-Objekt der ADO 2.1
Libary verwendet, um auf die Daten zuzugreifen.
An dieser Stelle werden Befehle der Datenbankprogrammiersprache SQL an
die Source-Eigenschaft des Recordset-Objektes übergeben, um die
gewünschten Resultate zu erzielen.
Über die weitere Verwendung der erwähnten Objekte sei auf die Visual Basic
Online-Dokumentation unter der Referenz ,,Plattform SDK|Datenbank-
Dienste|Microsoft Datenzugriffs-SDK|- ADO Programmers Reference"
verwiesen.
Kapitel 4 : Visual Basic 6.0 Programm
18
4.3 Datenbankmanipulation
Dieses Kapitel zeigt die Möglichkeiten auf, wie gewünschte Veränderungen am
vorhandenen Datenbestand herbeiführt werden können.
4.3.1 Elemente hinzufügen
Das Modul ,,Elemente hinzufügen" bietet die Möglichkeit einen vorhandenen
Datenbestand um weitere Elemente zu ergänzen ohne gleich eine neue
Datenbanktabelle anlegen zu müssen. So kann es zum Beispiel im Rahmen
einer Tourenplanung nach Ablauf einer bestimmten Zeit vorkommen, daß ein
neuer Ort in die bestehende Route integriert werden muß. Im nachfolgenden
Struktogramm sind die Hauptbestandteile des Moduls enthalten :
recordsetaufbau_standard
laeufer = rs_standard.RecordCount
neuerOrt = InputBox
sql1 = "ALTER TABLE Entfernungsmatrix ADD " & neuerOrt & " INT NOT NULL"
id_neuerort = laeufer + 1
recordsetaufbau (source = sql1)
sql3 = "INSERT INTO Entfernungsmatrix VALUES(" & id_neuerOrt & "," & neuerOrt & speicher & ",0)"
recordsetaufbau (source = sql3)
For i = 1 to laeufer
ReDim wert(i to i)
wert (i) = InputBox
speicher = speicher + "," + wert (i)
sql2 = "UPDATE Entfernungsmatrix SET " & neuerOrt & "=" & wert (i) & " WHERE Startort ='" &
rs_standard!startort & "'"
recordsetaufbau (source = sql2)
rs_standard.MoveNext
Abb.1 : ,,Elemente hinzufügen"
Kapitel 4 : Visual Basic 6.0 Programm
19
In der ersten Anweisung des Moduls wird die Prozedur
,,recordsetaufbau_standard" im Modul ,,Allgemein" aufgerufen. In dieser
Prozedur wird per Recordset (rs_standard) ein Zugriff auf die Datenbanktabelle
,,Entfernungsmatrix" gewährleistet. Die Variable ,,laeufer" aus der zweiten
Anweisung liest die Anzahl der vorhandenen Datensätze aus der
Datenbanktabelle aus. Dies geschieht mittels der RecordCount-Methode des
Recordset-Objektes.
Danach wird der Name des neu aufzunehmenden Elementes in der Variable
,,neuerOrt" abgelegt. Der Name wird durch den Benutzer in Form einer
einfachen InputBox eingegeben. In der nachfolgenden Anweisung wird der
Stringvariablen ,,sql1" das SQL-Kommando für das Erweitern der
Datenbanktabelle übergeben.
Anschließend wird in der Variablen ,,id_neuerOrt" die ID (primary Key) des
aufzunehmenden Elementes ermittelt, in dem die Variable ,,laeufer" um ,,eins"
erhöht wird.
Der Inhalt der Variablen ,,sql1" wird nun an die Source-Eigenschaft eines
Recordset-Objektes übergeben und das Recordset-Objekt mittels Open-
Methode geöffnet. Das Ausführen der Open-Methode bewirkt eine sofortige
Änderung innerhalb der vorhandenen Datenbanktabelle, mit dem Ergebnis, daß
das aufzunehmende Element als neue Spalte angelegt wurde.
In der nun folgenden Schleife werden die neu aufzunehmenden Spaltenwerte
ermittelt und in die Datenbanktabelle eingelesen.
In der ersten Anweisung innerhalb der Schleife wird die Variable ,,wert"
entsprechend des Schleifenindizeswertes neu dimensioniert. Mittels einer
InputBox wird der Benutzer aufgefordert, die entsprechenden Daten
einzupflegen, wobei im Text der InputBox ein Verweis auf den jeweiligen
Datensatz der Datenbanktabelle eingefügt ist. Die Eingabe wird in der Variablen
,,wert" abgelegt.
Die Variable ,,speicher" hält alle Inhalte der Variablen ,,wert" per Kommata
getrennt fest und bildet die Basis für das spätere Einfügen der Zeilenwerte. In
der sich anschließenden Anweisung wird das SQL-Kommando für das Einlesen
der Spaltenwerte in der Variablen ,,sql2" abgelegt. Anschließend wird ein
Recordset-Objekt mit der Source-Eigenschaft ,,sql2" per Open-Methode
Kapitel 4 : Visual Basic 6.0 Programm
20
geöffnet, so daß der eingegebene Wert in die entsprechende Spalte der
Datenbanktabelle eingefügt wurde.
In der letzten Anweisung wird der Zeiger der Datenbanktabelle auf den
nächsten Datensatz gesetzt.
Die Schleife läuft nun solange durch bis sämtliche Datensätze durchlaufen und
die entsprechenden Eingaben getätigt wurden. Die Variable ,,sql3" enthält den
SQL-Befehl für das Einfügen der relevanten Zeilenwerte und dient dem
nachfolgenden Recordset-Objekt als Source-Eigenschaft.
Die Datenbanktabelle wurde jetzt um das gewünschte Element erweitert.
4.3.2 Elemente entfernen
Das Modul ,,Elemente entfernen" dient der Entfernung ausgewählter Elemente
aus der Datenbanktabelle. Am nachfolgenden Struktogramm wird die
Wirkungsweise des Moduls näher erläutert.
For j = 0 to k
List1.selected(j) = true
Wahr
Falsch
next j
sql5 = ""
Wahr
Falsch
sql5 = "DELETE
FROM
Entfernungsmatrix
WHERE Startort='" &
List1.List(j) & "'"
sql5 = sql5 & " OR
Startort='" &
List1.List(j) & "'"
sql6 = ""
Wahr
Falsch
sql6 = "ALTER
TABLE
Entfernungsmatrix
DROP " & List1.List(j)
sql6 = sql6 & "," &
List1.List(j)
Abb.2 : ,,Elemente entfernen"
Beim Aufruf der Prozedur ,,Element(e) löschen" wird zunächst ein Zugriff auf die
aktuelle Datenbanktabelle erzeugt und die darin enthaltenen
Elementbezeichnungen in eine ListBox eingetragen. Der Benutzer aktiviert die
Kapitel 4 : Visual Basic 6.0 Programm
21
zu entfernenden Elemente anhand von Kontrollkästchen neben den jeweiligen
Listeneinträgen und bestätigt seine Angaben mittels eines CommandButton,
wodurch die Schleife aus Abb.2 ,,Elemente entfernen" ausgelöst wird.
Der Schleifenindex k wurde mit dem Wert k = List1.ListCount 1 initialisiert.
Innerhalb der Schleife wird nun jedes Kontrollkästchen des jeweiligen
Listeneintrages überprüft. Wurde ein Eintrag aktiviert, so werden die Variablen
,,sql5" und ,,sql6" mit einem SQL-Befehl belegt. Die Variable ,,sql5" enthält das
Kommando für das Löschen der entsprechenden Zeilen und die Variable ,,sql6"
für das Löschen der relevanten Spalten der Datenbanktabelle.
Die Inhalte der beiden Variablen werden in einem letzten Schritt an die Source-
Eigenschaften zweier Recordset-Objekte übergeben.
Mit der Ausführung der Recordsets sind die gewünschten Elemente aus der
Datenbanktabelle entfernt worden.
4.4 Klassenmodul Tourenverkettung
Das Klassenmodul ,,Tourenverkettung" bildet das Herzstück der umgesetzten
Algorithmen. Bevor ein Ortepaar an ein anderes angekettet werden kann,
müssen diverse Möglichkeiten überprüft werden. Es sollen zunächst sämtliche
notwendige Überprüfungsarbeiten an kleinen Beispielen visualisiert werden, um
anschließend auf die Wirkungsweise des Moduls ,,Tourenverkettung" näher
eingehen zu können.
Nachfolgendes Ortepaar aus einer beliebigen Savingliste sei als Basis
bezeichnet und stellt das Ausgangsortepaar dar, an welches nun angekettet
werden soll : -A,B- .
Nehmen wir an unser zu kontrollierendes Ortepaar hätte folgende Gestalt :
-F,B- . Für eine mögliche Ankettung muß nun folgendes überprüft
werden :
1.)
Ist der linke Teil des anzukettenden Ortepaares gleich des linken
Teils der Basis ?
2.)
Ist der linke Teil des anzukettenden Ortepaares gleich des rechten
Teils der Basis ?
Kapitel 4 : Visual Basic 6.0 Programm
22
3.)
Ist der rechte Teil des anzukettenden Ortepaares gleich des linken
Teils der Basis ?
4.)
Ist der rechte Teil des anzukettenden Ortepaares gleich des rechten
Teils der Basis ?
In unserem Beispiel ist der 4. Fall zutreffend, so daß die Basis nach dem
Prozeß der Ankettung folgende neue Gestalt besitzen würde :
-A,B,F- .
Diese vier zu unterscheidenden Möglichkeiten müssen bei jeder denkbaren
Ankettung überprüft werden. Folgende Ankettungsformen treten bei den
umgesetzten Algorithmen auf :
1.)
Ankettung eines Ortepaares an Basis
1a)
-A,B- (Basis) + -A,F- (anzukettendes Ortepaar)
= -F,A,B-
2.)
Ankettung eines Ortepaares an eine Insel
2a)
-F,G- (Insel) + -G,H- (anzukettendes Ortepaar)
= -F,G,H-
3.)
Verwendung des anzukettenden Ortepaares, um eine Insel mit der
Basis zu verbinden
3a)
-A,B- (Basis) + -F,G- (Insel) + -B,F- (anzukettendes Ortepaar)
=
-A,B,F,G-
4.) Verwendung des anzukettenden Ortepaares, um zwei Inseln
miteinander zu verbinden
4a)
-F,G- (Insel 1) + -K,L- (Insel 2) + -L,F- (anzukettendes Ortepaar)
= -K,L,F,G- .
Für die Ausgabe der Tour sind darüber hinaus zwei weitere Überprüfungen je
Verkettungspunkt nötig :
1.) Wurde das Ortepaar an der linken oder der rechten Seite
angekettet ?
2.)
Mit welchem Teil des Ortepaares erfolgte die Ankettung ?
Nehmen wir an wir wollten die Insel -K,L,M,N- mit der Basis -A,B,C,D- durch
das Ortepaar -N,A- verbinden. Das gewünschte Resultat sollte lauten :
-K,L,M,N,A,B,C,D- . Die einzelnen Elemente der Insel wurden also von links
nach rechts laufend an die Basis angekettet. Hätte das anzukettende Ortepaar
jedoch die Gestalt -D,N- so müßte das Resultat folgende Gestalt besitzen :
Kapitel 4 : Visual Basic 6.0 Programm
23
-A,B,C,D,N,M,L,K- . Das heißt die Elemente der Insel wurden von rechts nach
links in die Basis integriert.
Um alle aufgeführten Möglichkeiten realisieren zu können wurde das
Klassenmodul ,,Tourenverkettung" initialisiert. Ausgangspunkt für diese
Initialisierung war die Absicht eine komplette Zeile einer Savingliste als ein
Objekt zu deklarieren. Das Objekt sollte dann jede einzelne Zelle der Zeile als
Eigenschaft beinhalten. Eine mögliche Zeile in einer Savingliste besitzt folgende
Gestalt :
INDEX ENTFERNUNG ORT 1 ORT 1A
1 1.500
A B
Abb. 3 : ,,Ausschnitt einer Savingliste"
Ein Objekt würde mit der Anweisung ,,Dim Ort as New Tourenverkettung"
erzeugt und mit folgenden Eigenschaften ausgestattet :
1.)
Ort.index = 1
2.)
Ort.entfernung = 1.500
3.)
Ort.grenzelinks = A
4.) Ort.grenzerechts=B
.
Die spezifischen Objekteigenschaften wurden in Form von globalen Variablen
im Klassenmodul realisiert. Mit der Benutzung eines Objektes werden die
globalen Variablen wie eine Eigenschaft ausgelesen. Damit Änderungen der
Eigenschaftswerte wirksam werden, muß die Klasse über
Eigenschaftsprozeduren für Zahlenwerte und Zeichenketten verfügen. Für jede
deklarierte Eigenschaft existieren zwei gleichnamige Eigenschaftsprozeduren.
Mit der ,,Property Get" Prozedur wird die gesetzte Eigenschaft ausgelesen
und mit der ,,Property Let" Prozedur wird einer gesetzten Eigenschaft ein
neuer Inhalt zugewiesen.
Zuzüglich zu den vier elementaren Eigenschaften (s.o.) wurden weitere
Eigenschaften gesetzt, um die Verkettungsprozesse zu visualisieren :
1.) Ort.textlinks
2.) Ort.textrechts
Kapitel 4 : Visual Basic 6.0 Programm
24
3.) Ort.textlinks2
4.) Ort.textrechts2
5.) Ort.offenlinks
6.) Ort.offenrechts.
Die Eigenschaften 1.) und 2.) speichern die Elemente einer Teilkette von links
nach rechts (A,B,C,D), wohingegen die Eigenschaften 3.) und 4.) die Elemente
einer Teilkette von rechts nach links speichern (D,C,B,A).
Die 5.) und 6.) Eigenschaft wird benötigt, um ein vorzeitiges Schliessen von
Teilketten zu verhindern. Diese beiden Eigenschaften sind vom Datentyp
boolean.
Mit den hier aufgezeigten Eigenschaften ist es möglich, jegliche
Ankettungsmöglichkeit der umgesetzten Algorithmen zu realisieren.
4.5 Algorithmen
Die nachfolgenden Module des Visual Basic Programms werden aus rein
programmiertechnischer Sichtweise betrachtet. Hierbei sollen die
entscheidenden Aspekte der Umsetzung herausgearbeitet werden.
4.5.1 Algorithmus des besten Nachbarn
In der Prozedur ,,FormLoad" wird als erster Schritt die sortierte Savingliste
aufgebaut und in einem MSFlexGrid visualisiert. Desweiteren wird eine zur
Laufzeit nicht sichtbare ListBox mit den in die Tour zu integrierenden Elementen
aufgefüllt. Die Liste (Kontrolliste) wird bei jeder Ankettung um die Elemente, die
an der Ankettung beteiligt sind, verkleinert bis lediglich der Start- und Endpunkt
übriggeblieben ist.
Anhand der folgenden vereinfachten Darstellung der Hauptprozedur werden
nun die Verkettungsprozesse erläutert :
Kapitel 4 : Visual Basic 6.0 Programm
25
For i = 2 to speicher
Abbruch > 1
Wahr
Falsch
For j = 1 to List1.ListCount
next i
If List1.List(j) = ort(i).grenzerechts or
List1.List(j) = ort(i).grenzelinks
Wahr
Falsch
next j
Goto beginn
beginn :
Durchlauf der Ankettungsmöglichkeiten
next i
Abb. 4 : ,,Algorithmus des besten Nachbarn"
Nachdem die Objekte anhand der Savingliste initialisiert wurden, wird das
Basisobjekt aus der Kontrolliste entfernt. In der Schleife wird zu Beginn
überprüft, ob das aktuelle Ortepaar aus der Savingliste noch in der Kontrolliste
vorhanden ist. Sind diese Orte bereits in die Tour integriert worden, so wird der
Schleifenindex um ,,eins" erhöht und das nächste Ortepaar wird zur
Untersuchung herangezogen. Andernfalls beginnt die Abfrage der
Ankettungsmöglichkeiten. Die verschiedenen Ankettungsmöglichkeiten (vgl.
Kapitel 4.4 Klassenmodul Tourenverkettung) werden anhand folgendem
Prozedurausschnitt exemplarisch verdeutlicht :
If ort(i).grenzelinks = basis.grenzerechts then
Basis.grenzerechts = ort(i).grenzerechts
Tourtextrechts = tourtextrechts + ,,," + ort(i).grenzerechts
Basis.entfernung = basis.entfernung + ort(i).entfernung
For d = 1 to List1.ListCount
If List1.List(d) = ort(i).grenzerechts then
List1.RemoveItem
(d)
Goto
retour
End
If
Next
d
End If
Kapitel 4 : Visual Basic 6.0 Programm
26
Die Objekteigenschaft ,,grenzelinks" des Objektes ,,ort(i)" wird mit der
Eigenschaft ,,grenzerechts" des Basisobjektes ,,basis" verglichen. Im Falle einer
Übereinstimmung kann das aktuelle Ortepaar an die Basis angekettet werden.
Hierzu wird anschließend die Eigenschaft ,,grenzerechts" des Basisobjektes auf
die Eigenschaft ,,grenzerechts" des Objektes ,,ort(i)" gesetzt, um den neuen
Endpunkt der Tour zu markieren. Im nächsten Schritt wird die neue
Elementreihenfolge in der Variablen ,,tourtextrechts" abgelegt. Danach erfolgt
die Fortführung der Tourenlänge, indem die Eigenschaften ,,entfernung" des
,,basis"- und des ,,ort(i)"-Objektes aufaddiert werden. In einem letzten Schritt
wird nun das neu angekettete Element aus der Kontrolliste entfernt.
Nachdem die Hauptschleife gemäß den Einträgen in der Savingliste
durchgelaufen ist, erfolgt eine weitere Überprüfung, ob sich noch Elemente in
der Kontrolliste befinden. Ist dies der Fall so wird die Schleife ein weiteres Mal
durchlaufen, so lange bis sämtliche Elemente in die Tour integriert wurden.
Nachdem die Tour komplett ist, wird die Ausgabe auf dem Bildschirm
eingeleitet.
In einer weiteren Variante wurde das Modul ,,Bester Nachbar variabel" ins
Leben gerufen. Beim Algorithmus des besten Nachbars wird ein Start- und
Zielpunkt sowie die zu integrierenden Elemente durch den Benutzer
vorgegeben. Innerhalb des variablen Ansatzes gibt der Benutzer lediglich die zu
integrierenden Elemente vor. Jedes Element dieser Menge wird nun einmal als
Start- und Zielpunkt definiert und die Tour wird entwickelt. Das heißt aus den n
ausgewählten Elementen entstehen n Touren, wobei die kürzeste präsentiert
wird. Dieser Ansatz gestaltet sich in der Umsetzung ein wenig aufwendiger, da
bei jeder Tourenzusammenstellung im Vorfeld die Schritte bis zur Entwicklung
der Savingliste durchlaufen werden müssen. Bei jedem neu gesetzten Startort
muß eine neue Savingmatrix aufgebaut werden, weil sich die Savingwerte
durch den neuen Startort verändert haben. Der Verkettungsprozess hingegen
ist derselbe wie zuvor.
Zunächst werden die gewählten Elemente in eine Kontrolliste eingetragen und
in einem fortlaufenden Array abgelegt. Das Array mit der Dimension n gibt
zugleich die Anzahl der Schleifendurchläufe vor.
Es wird nun des erste Element im Array als Startort deklariert. In den folgenden
Schritten wird dann die sortierte Savingliste aufgebaut, anhand derer dann der
Kapitel 4 : Visual Basic 6.0 Programm
27
Verkettungsprozess -analog zum Algorithmus des besten Nachfolgers-
vollzogen wird. Das Entstehen der Savingliste beruht auf SQL-Befehlen, welche
durch die OpenMethode der eingesetzten Recordsets realisiert werden. Das
Ergebnis der Tour wird in einem Array gespeichert. Die bis hierher genannten
Schritte wiederholen sich bis alle n Elemente des Arrays einmal als Startort
deklariert wurden.
Abschließend werden die Ergebnisse in einem MSFlexGrid absteigend sortiert,
so daß die kürzeste Tour in der ersten Zeile des MSFlexGrids zu finden ist.
4.5.2 Inselalgorithmus
Der Inselalgorithmus stellt eine Erweiterung des Algorithmus' des besten
Nachbarn dar, da mehr größere Savingwerte ihre Berücksichtigung finden (vgl.
Kapitel 3.2 : Inselalgorithmus). Durch die Zulassung von Ortepaaren als Inseln,
sprich von Ortepaaren, die zunächst nicht mit anderen Ortepaaren verkettet
werden, entsteht ein erhöhter Speicherbedarf an parallel vorhandenen
Tourenteilen. Desweiteren existieren mehrere Verkettungsmöglichkeiten wie in
Kapitel 4.4 : Klassenmodul Tourenverkettung aufgezeigt wurde.
Zunächst wird wie beim Algorithmus des besten Nachbarn- in der Prozedur
,,FormLoad" die Savingliste erzeugt und eine abzuarbeitende Kontrolliste
initialisiert. Der Hauptunterschied der beiden Verfahren soll an folgendem
Source-Code-Ausschnitt verdeutlicht werden :
Aktuelles Ortepaar noch in Kontrolliste ?
Ja :
Select Case Inselzaehler
Case 0:
Ankettungsüberprüfungen aktuelles
Ortepaar mit Basis
Falls
negativ
:
Inseldimensionierung
Case 1 to Inselzaehler:
Ankettungsüberprüfungen
aktuelles
Ortepaar mit Basis
Ankettungsüberprüfungen aktuelles
Ortepaar mit Insel
Kapitel 4 : Visual Basic 6.0 Programm
28
Falls
negativ
:
Inseldimensionierung
End Select
Nein :
Verbundüberprüfung vorhandener Inseln mit Basis
Verbundüberprüfung von Insel mit Insel
Zunächst wird überprüft, ob sich das aktuelle Ortepaar noch in der Kontrolliste
befindet, das heißt noch in die Tour integriert werden muß. Ist das der Fall, so
erfolgt eine Select-Case-Anweisung, die den Zustand der Variablen
,,Inselzaehler" auswertet. Diese Variable vom Typ integer erhöht sich jedes Mal
um ,,eins" im Falle einer Inseldimensionierung. Im Fall ,,Case 0" sind also keine
Inseln vorhanden und es muß lediglich überprüft werden, ob das aktuelle
Ortepaar an die Basis angekettet werden kann. Diese Überprüfung erfolgt nach
demselben Schema wie zuvor beim Algorithmus des besten Nachbarn. Konnte
keine Verkettung erzeugt werden, so wird das aktuelle Ortepaar als neue Insel
deklariert.
Im Fall ,,Case 1 to inselzaehler" sind bereits Inseln vorhanden. Zunächst wird
ebenfalls überprüft, ob das aktuelle Ortepaar an die Basis angekettet werden
kann. Konnte keine Verkettung erzeugt werden, so wird überprüft, ob sich das
aktuelle Ortepaar an die vorhandenen Inseln anketten läßt. Falls auch diese
Überprüfung negativ ausfällt, wird das aktuelle Ortepaar als neue Insel
dimensioniert.
Ist die Anfangsüberprüfung negativ ausgefallen, so bedeutet dies, das das
aktuelle Ortepaar mit seinen Elementen bereits in die Tour integriert wurde. Das
heißt es gilt nun zu überprüfen, ob das aktuelle Ortepaar Teilketten miteinander
verbinden kann. Eine solche Verbundüberprüfung wird nun exemplarisch
anhand des folgenden Source-Code-Ausschnittes dargestellt :
Kapitel 4 : Visual Basic 6.0 Programm
29
Verbund von Insel(n) mit Basis :
For p = 1 to Inselzaehler
If Insel(p).offenlinks = True and Insel(p).offenrechts = True then
If ort(i).grenzelinks = insel(p).grenzelinks and ort(i).grenzerechts =
basis.grenzelinks or ort(i).grenzelinks = basis.grenzelinks
and
ort(i).grenzerechts
= Insel(p).grenzelinks then
Basis.entfernung = basis.entfernung + Insel(p).entfernung +
ort(i).entfernung
Tourtextlinks = Insel(p).textrechts + ,,," + Insel(p).textlinks +
,,," + tourtextlinks
Basis.grenzelinks
=
Insel(p).grenzerechts
Insel(p).offenlinks
=
True
Insel(p).offenrechts
=
False
Insel(p).grenzelinks
=
,,"
Insel(p).grenzerechts
=
,,"
GoTo
retour
End
If
End
If
Next p
In diesem Ausschnitt wird überprüft, ob die boolschen Eigenschaften des
Inselobjektes den Wert "true" besitzen. Dadurch wird verhindert, daß Teilketten
zu einer Rundreise verbunden werden, obwohl noch Orte in die Tour zu
integrieren sind.
In einem nächsten Schritt erfolgt dann die Verkettungsüberprüfung. Das
Ortepaar wird hier mit der linken Grenze des Inselobjektes und der linken
Grenze des Basisobjektes verglichen. Im Falle der Verkettung würde also das
Inselobjekt an die linke Grenze des Basisobjektes angekettet werden. In der
folgenden Anweisung werden die Elemente der neuen Teiltour in der Variablen
"tourtextlinks" festgehalten. Anschließend wird die neue linke Grenze des
Basisobjektes definiert.
Kapitel 4 : Visual Basic 6.0 Programm
30
Abschließend werden die boolschen Eigenschaften des Inselobjektes
aktualisiert und die Grenzen entfernt, da es sich jetzt ja nicht mehr um eine
Insel handelt, sondern um eine erweiterte Basis.
Der Inselalgorithmus wurde ebenfalls mit einer variablen Variante ausgestattet,
welche analog zum "Algorithmus des besten Nachbarn variabel" aufgebaut
wurde (vgl. Kapitel 4.5.1 : Algorithmus des besten Nachbarn).
4.5.3 Vollenumeration
Zu Beginn der Prozedur wird jedem ausgewählten Element eine Zahl
zugeordnet. Mit Hilfe der so entstandenen Zahlenreihe werden dann alle
möglichen Permutationen erzeugt. Sowie eine Permutation entstanden ist, wird
die Zahlenreihe in die ursprünglichen Elementbezeichnungen zurücktransferiert
und die Länge der Tour errechnet. Das Ergebnis der Tour wird anschließend in
einem Array gespeichert. Nachdem die nächste Permutation, das heißt die
nächste Tour, erzeugt wurde, kommt es zu einem Längenvergleich der bisher
ermittelten Touren. Das Array wird nun mit der kürzeren der beiden Touren
belegt. Nach Durchlauf aller Permutationen ist somit nur die kürzeste aller
Touren in dem Array enthalten.
Der genaue Ablauf der Permutationserzeugung soll an einem kleinen Beispiel
veranschaulicht werden. Nehmen wir an die Tour besteht aus den zu
bereisenden Elementen ,,A", ,,B" und ,,C". Zunächst erfolgt nun die
Zahlenzuweisung an die Elemente (A-1,B-2,C-3). Die entstandene Zahlenreihe
(1,2,3) wird nun an die Funktion ,,perm" übergeben. Innerhalb dieser Funktion
werden alle möglichen Permutationen erzeugt :
1.) 1,2,3
2.) 1,3,2
3.) 2,1,3
4.) 2,3,1
5.) 3,1,2
6.) 3,2,1.
Kapitel 4 : Visual Basic 6.0 Programm
31
Die entstandenen Folgen werden dann wieder in die Elementbezeichnungen
zurücktransferiert :
1.) A,B,C
2.) A,C,B
3.) B,A,C
4.) B,C,A
5.) C,A,B
6.) C,B,A.
Als nächstes werden den einzelnen Elementbestandteilen einer Tour die
zugehörigen Entfernungswerte aus der Datenbanktabelle zugewiesen.
Ausgehend von der Folge ,,ABC" würde das erste Elementpaar gebildet (AB)
und der entsprechende Entfernungswert aus der Datenbanktabelle ermittelt.
Anschließend wird der Entfernungswert des Elementpaares ,,BC" ermittelt.
Nachdem die Tour in der beschriebenen Weise durchlaufen wurde, wird die
Länge der Tour in einem Ergebnisarray gespeichert.
Das Hauptproblem dieser Prozedur besteht im Durchlauf aller möglichen
Permutationen, so daß vorhandene Rechnerkapazitäten schnell ausgelastet
sein können. Die entwickelte Prozedur berücksichtigt aus diesem Grund nur
Touren, welche aus maximal neun Elementen bestehen. Die Prozedur
,,Vollenumeration" besitzt somit lediglich einen exemplarischen Charakter, der
zugleich die Bedeutung der angewandten Algorithmen hervorhebt.
Kapitel 4 : Visual Basic 6.0 Programm
32
4.6 Wartungs- und Änderungsdienst
Um das Programm mit neuen selbsterstellten Entfernungstabellen nutzen zu
können, muß eine Datenbank gemäß den Konventionen nach Kapitel 4.1
Datenbankentwurf erstellt werden. Der Name der Datenbanktabelle muß
,,Entfernungsmatrix" lauten. Desweiteren sollte darauf geachtet werden, daß die
neu erstellte Datenbank auch nur die Tabelle ,,Entfernungsmatrix" enthält, da es
sonst zu Problemen bei der Programmausführung kommen kann. Im
Vordergrund der Programmerstellung stand die Umsetzung der Algorithmen, so
daß auf eine völlig variable Datenbankverwaltung verzichtet wurde.
Ist es für den Benutzer unabdingbar, die gewählten Konventionen zu nutzen, so
müssen folgende Programmveränderungen vorgenommen werden :
1.) Nach der Herstellung zur Verbindung der Datenbank, muß ein
weiteres Recordset-Objekt mit der OpenSchemaTables-Methode
geöffnet werden und beispielsweise in einer ListBox visualisiert
werden.
2.)
Der Benutzer hat somit die Möglichkeit, aus den in der Datenbank
enthaltenen Tabellen auszuwählen.
3.)
Das Ergebnis der Auswahl muß dann in sämtlichen relevanten SQL-
Befehlen des Programms mit eingebunden werden.
Es sei jedoch darauf hingewiesen, daß die Spaltenbezeichnungen ,,ID" und
,,Startort" der Datenbanktabelle nicht ohne weiteres variabel gehalten werden
können.
Kapitel 5 : Rundreis
ebeispiel mit 25 Element
en
33
5. Rundreisebeispiel mit 25 Elementen
A
lg
o
ri
thm
u
s
R
e
c
he
nze
it
L
ä
n
g
e
d
e
r T
o
u
r
T
o
u
r
in
se
k.
g
e
m
.
Ei
n
h
e
it
BN
0,
16
64
.9
51
An
ch
or
a
g
e
--
-Ho
no
lu
lu
,M
on
tr
e
a
l,
L
o
sA
ng
el
es
,C
hi
ca
g
o
,M
ex
ik
o
S
ta
d
t,
N
e
w
Yor
k,
L
is
sa
bo
n,
Ka
lk
ut
ta
,P
a
ri
s,
M
os
ka
u,
F
ra
n
kf
u
rt
,Da
ka
r,
Car
a
ca
s,
Li
m
a
,B
u
e
n
o
sAi
re
s,
Jo
ha
nn
es
bu
rg
,
N
a
ir
o
b
i,
Ka
ir
o,
Bo
m
b
ay,
H
on
gkon
g,
D
e
lh
i,
Peki
ng
,L
on
don
,M
ia
m
i-
--
An
ch
or
ag
e
BN
-v
ar
ia
be
l
5
,6
0
4
4.
78
8
D
el
hi
--
-B
om
ba
y,
Ka
ir
o,
M
o
sk
a
u
,L
on
do
n,
F
ra
n
kf
ur
t,
P
ar
is
,L
is
sab
o
n
,D
a
kar
,M
o
n
tr
e
al
,
N
e
w
Y
or
k,
M
e
xi
ko
St
ad
t,
B
ue
no
sA
ir
e
s,
L
im
a
,C
a
ra
cas,
M
iam
i,
C
h
ic
ag
o,
L
o
sAng
el
es,
H
o
n
o
lu
lu
,A
n
ch
o
ra
g
e
,P
e
kin
g
,H
o
n
g
ko
n
g
,K
a
lk
u
tt
a
,Jo
h
a
n
n
e
sb
u
rg
,N
a
iro
b
i---D
e
lh
i
In
sel
0
,0
5
3
9.
33
6
A
ncho
ra
g
e
--
-H
on
ol
u
lu
,L
o
sAn
g
e
les,
M
o
n
tr
ea
l,
Ne
w
Y
or
k,
C
h
ic
ag
o,
M
e
xi
koSt
a
d
t,
M
iam
i,
C
a
ra
ca
s,
L
im
a
,B
ue
no
sA
ir
e
s,
Joh
an
ne
sb
ur
g,
N
a
ir
ob
i,
Kai
ro
,D
a
kar
,Li
ss
a
b
o
n
,P
a
ri
s,
F
ra
n
kf
u
rt
,L
on
do
n,
M
o
sk
a
u
,D
e
lhi
,B
om
ba
y,
Ka
lk
u
tt
a
,H
on
gkon
g,
Pe
ki
n
g
--
-A
ncho
ra
g
e
In
se
l-
va
ri
ab
el
6,
10
37
.6
11
Da
ka
r-
--
L
is
sa
b
o
n
,P
a
ri
s,
L
o
n
d
o
n
,F
ra
nk
fu
rt
,M
o
sk
a
u
,Kai
ro
,J
o
ha
nn
es
bu
rg
,N
ai
ro
bi
,B
o
m
ba
y,
D
e
lh
i,
Ka
lk
u
tt
a
,H
on
gkon
g,
Pe
ki
n
g
,A
n
ch
o
ra
ge
,H
on
ol
u
lu,
L
o
sAng
el
es,
M
e
xi
ko
S
ta
d
t,
C
hi
cag
o
,
M
o
n
tre
a
l,
N
e
w
Y
o
rk
,M
ia
m
i,
C
a
ra
ca
s,
L
ima
,B
u
e
n
o
sA
ir
e
s---D
a
ka
r
Sy
s
te
m
P
ro
ze
ss
o
r:
A
M
D
A
thlon
1,0 G
H
z
A
rb
e
its
speic
her
:
128 M
B
D
a
teis
ys
tem
:
32-
B
it
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2001
- ISBN (eBook)
- 9783832443870
- ISBN (Paperback)
- 9783838643878
- Dateigröße
- 717 KB
- Sprache
- Deutsch
- Institution / Hochschule
- Fachhochschule Westküste Heide – unbekannt
- Note
- 1,0
- Schlagworte
- algorithmen travelling salesman problem visual basic
