Wegeoptimierung

Beiträge zum Forumthread

Beiträge zu diesem Forumthread

Betreff

Datum

Anwender

AW: Wegeoptimierung

11.05.2007 10:03:00

ingUR

AW: Wegeoptimierung

12.05.2007 22:03:00

Coach

AW: Wegeoptimierung

13.05.2007 01:47:00

ingUR

AW: Wegeoptimierung

13.05.2007 09:42:37

Coach

AW: Wegeoptimierung

13.05.2007 11:16:49

ingUR

AW: Wegeoptimierung

13.05.2007 23:25:54

Markus

Hallo, Markus,
Zellenformel dafür diese Aufgaben zu entwickeln scheint mir nicht der geeignete Weg zu sein, da es auf eine variable Indexberechnung in einer Matrix, basierend auf der zuletzt ermittelten Stelle einer Minimumbetrachtung hinauslaufen würde. Zudem wäre noch zu unterscheiden, ob es sich um gerichtete (unsymmetrische Matrix) oder ungerichtete Graphen handelt, die die Knoten verbinden.


A      B    C     D    E
A        -   400  150  400  270
B       600   -   450  320  480
C       150  450   -   300  260
D       400  320  300  -    220
E       270  480  260  220    -

Startknoten A:

suche Min-Wert > 0 in Zeile A; nach Knoten C Länge 150, Spalte C

lösche Zeile 3, Spalte 1 (C n. A und alle Werte der Verbindungen von Knoten A zu den übrigen Knoten, außer Knoten C)
suche Min-Wert > 0 in Zeile C; nach Knoten E Länge 260; lösche analog wie im ersten Schritt

suche Min-Wert > 0 in Zeile E; nach Knoten D Länge 220; lösche analog wie im ersten Schritt

suche Min-Wert > 0 in Zeile D; nach Knoten B Länge 320; lösche analog wie im ersten Schritt

suche Min-Wert > 0 in Zeile B; nach Knoten A Länge 400; zum Startpunkt A zurückgekehrt
Route: r=(A-C-E-D-B)
Weg: c(r)=150+260+220+320+400=1350
Soweit die einfache Wegbeschreibung (Ermittlung "Bester Nachloger"). Das sollte als Ausgangsbasis für ein VBA-Makro an Beschreibung dienen können, das dann ausgebaut werden kann. Ich hoffe, es reicht für einen erfolgreichen Start Deines Projekts, der zu einem Makro führt, das dann ausgebaut werden kann und zu dem ggf. gezielt EXCEL-Fragen gestellt werden können. Dei Gesamtlösung würde den Rahmen einer Beantwortung einer EXCEL-Frage sprengen und käme einer Projektentwicklung gleich.
Gruß,
Uwe

Hallo, @Coach,
zuerst einmal Gratualation zu Deinen Formeln.
Deine Berechnungen sind richtig und auch die Erkenntnis trifft zu (auch der Zahlenwert stimmt), dass die Methode der "Besten Nachfolger" nicht unbedingt zum optimalen Ergebnis führen muß, da der Startpunkt willkürlich ist.
Selbst würde ich nicht "in Versuchung geraten", dieses Problem mit Zellenformeln anzugehen, denn die Veränderung auf das Lösungsverfahren "Sukzessive Einbeziehung" (SE), macht die Arbeit an den Zellenformeln zum Verfahren "Bester Nachfolger" (BN) hinfällig, während VBA-Routinen durchaus mit Elementen aus beiden Verfahren arbeiten könnten.
Beim (SE)-Verfahren wird im Gegensatz zum (BN)-Verfahren von einer Basisstrecke ausgegangen, die mit Hin- und Rückweg ferststeht. Nun wird sukzessiv untersucht, welcher Knoten als nächster in diese bisherige Route einzubeziehen ist. Es ergibt sich so für die erste Iteration, der Einbeziehung eines dritten Knotens, die Untersuchung in drei Schritten, für jeden mögliche Reihenfolge ein Schritt.
Basis: C-E-C: L(C-E-C)=260+260=520 (Hin und Rück)
1.Iteration 1.Schritt: Knoten mit maximaler kürzester Entfernung zur Strecke C-E
MAX( Min[(A-C);(A-E)]=150; Min[(B-C);(B-E)]=450; Min[(D-C);(D-E)]=220 )
Ergebnis ist Min[(B-C);(B-E)]=450, also wird nun Knoten B eingebunden:
1.Iteration 2.Schritt: Knoten B einbinden L(C-B-E-C)=260+450+480=1190
2.Iteration 1.Schritt: Knoten mit maximaler kürzester Entfernung zur Strecke C-B-E-C
MAX( Min[(A-B);(A-C);(A-E)]=150; Min[(D-B);(D-C);(D-E)]=220 )
Ergebnis ist Min[(D-B);(B-C);(B-E)]=220, also wird nun Knoten D eingebunden:
2.Iteration 2.Schritt: Knoten D zwischn C und E einbinden L(C-B-E-D-C)=450+480+220+300=1450
2.Iteration 3.Schritt: Knoten D zwischn E und B einbinden L(C-B-D-E-C)=450+320+220+260=1250
2.Iteration 4.Schritt: Knoten D zwischn B und C einbinden L(C-D-B-E-C)=300+320+480+260=1360
2.Iteration 5.Schritt: Geringster Weg L(C-B-D-E-C)=450+320+220+260=1250
3.Iteration 1.Schritt: Knoten mit maximaler kürzester Entfernung zur Strecke C-E-D-B-C
Min[(A-B);(A-C);(A-D);(A-E)]=150
3.Iteration 2.Schritt: Knoten A zwischn C und E einbinden L(C-A-E-D-B-C)=1410
3.Iteration 3.Schritt: Knoten A zwischn E und D einbinden L(C-E-A-D-B-C)=1700
3.Iteration 4.Schritt: Knoten A zwischn D und B einbinden L(C-E-D-A-B-C)=1730
3.Iteration 5.Schritt: Knoten A zwischn B und C einbinden L(C-E-D-B-A-C)=1350
Der Knoten A ist also zwischen B und C anzuordnen, so das die gesamte Route r=(C-E-D-B-A-C) = (C-A-B-E-C) ist und L(r)=1350 lang ist.
Mit diesem (SE)-Verfahren ist das Ergebnis nun eindeutig, denn auch D-B-A-C-E-D liefert 1350, die Reihenfolge bleibt egal welcher Startpunkt auf dem "Ring" gewählt wird.
Anders beim (BN)-Verfahren, hier liefert die Suche wie Du schon beschrieben hast, für den Startpunkt C die Länge L=1410. Wird für das (BN)-Verfahren beim Startpunkt E gestartet, sollte sich 1550 ergeben.
Zur Vervollständigung: Für Wege können natürlich auch Kosten zwischen den einzelner Schritten angeschrieben werden.
Mal sehen, ob Deine Lösung, @Coach, den Frager Markus ein Stück weiter bei der Lösung seiner Aufgabe bringt oder bei der Umsetzung einer VBA-Idee. Noch wissen wir nicht, welche Aufgabe wirklich zu lösen ist (gerichtete, ungerichtete Graphen = Verbindungen zwischen den Knoten) und welche Vorarbeiten schon erledigt sind, denn meine Beschreibung hat nur die einfache Aufgabenstellung dargestellt.
Gruß,
Uwe

Beliebteste Forumthreads (12 Monate)

6 Beiträge zum Forumthread Beiträge zu diesem Forumthread

Beliebteste Forumthreads (12 Monate)

Beliebteste Forumthreads (12 Monate)

6
Beiträge zum Forumthread

Beiträge zu diesem Forumthread