Live-Forum - Die aktuellen Beiträge
Anzeige
Anzeige
HERBERS
Excel-Forum (Archiv)
20+ Jahre Excel-Kompetenz: Von Anwendern, für Anwender
Inhaltsverzeichnis

Entfernungsmatrix aus mehreren Tabellenblättern

Entfernungsmatrix aus mehreren Tabellenblättern
19.11.2017 23:16:49
Steinert
Hallo zusammen,
ich verzweifle gerade an folgendem Problem:
Ich will zwischen allen Berliner S-Bahn Haltestellen die zeitliche Dauer in einer Matrix darstellen.
Mein Ziel ist das Travelling Salesman Problem zu lösen. Also die Reihenfolge zu finden, in der alle Stationen genau einmal in der kürzesten Zeit abgefahren werden (aber bei Endhaltestellen müssen Stationen mehrmals besucht werden).
Durch das Streichen von Zwischenhaltestellen hab ich nur noch 35 Stationen bzw. Knoten und diese in einer Matrix dargestellt.
In den dahinterliegende 15 Tabellenblättern jeweils die Fahrpläne der 15 S-Bahnlinien.
Ich möchte gerne, dass Excel mir die Entfernungsmatrix aus den Fahrpläne befüllt. Also die (mittlere) Fahrtzeit von Station A zu Station B, und dann in den Tabellenblättern sucht welche S-Bahn-Linien von A nach B fahren, dann jeweils die Ankunftszeit von B - Abfahrtszeit von A=Fahrtzeit und bei mehreren Linien den Mittelwert bildet und den dann in die Matrix ganz vorne einträgt.
Versteht ihr was ich meine?
Ich weiß einfach nicht wie ich sowas in Formeln beschreiben kann?
Wäre echt super, wenn ihr mir auf die Sprünge helfen könntet Smile
Danke euch!

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

Betreff
Datum
Anwender
Anzeige
Entfernungsmatrix aus mehreren Tabellenblättern
20.11.2017 10:32:15
Steinert
Guten Morgen,
vielen Dank für eure schnelle Hilfe :)
Mein Problem ist aber gerade noch nicht das Lösen des TSP.
Da gibt's einige fertige Codes für alle möglichen Solver, von VBA, C++, online....
Da kann mich auch noch ne Freundin unterstützen.
Mein Problem ist gerade zuerst die Entfernungs-bzw. Distanzmatrix (von/nach) in Tabellenblatt 1 auf Basis der Fahrpläne(Tabellenblätter 2-16)aufzubauen:
Ich bekomme es einfach nicht hin eine Formel aufzustellen, die eben Excel dazu bringt die Fahrtzeiten
zwischen 2 Stationen in die Matrix einzutragen. Excel soll in den Tabellenblättern (15 Blätter=15 S-Bahnlinien) suchen, welche S-Bahnlinien die Station A und B anfahren und jeweils die (mittlere) Fahrtzeit berechnen, also immer Ankunftszeit(B)-Abfahrtszeit(A), die Fahrtzeiten über mögliche Linien aufsummieren, das Mittel bilden und in der Distanzmatrix eintragen.
Fällt euch da ein Formelansatz ein?
Genau, in dem Link oben sind meine Anlagen in einem anderen Forum (leider hat es hier nicht funktioniert?)
Versteht ihr was ich meine?
Anzeige
Tod eines Handlungsreisenden
20.11.2017 07:16:45
WF
Hi,
Excel ist damit vollkommen überfordert.
Das Traveling Salesman Problem ist nur näherungsweise mit heuristischen Verfahren des Operations Research lösbar.
Deine 35 Bahnhöfe ergeben =FAKULTÄT(35) Möglichkeiten. Das ist eine 40-stellige Zahl.
WF
Eine Eingrenzung ggü dem TSP und WF:
20.11.2017 07:40:24
lupo1
Wenn man auf das PDF guckt (in einem der Crosspostings, shame on you!), begreift man, dass die Reise von einem (möglichst hochrangigen?) Umsteigepunkt aus BEGINNEN muss.
Hat man von diesem Punkt aus alle "Zweige" ABGEARBEITET, begibt man sich auf direktem Wege zum nächsten Knotenpunkt (man geht also nicht über Los) und verfährt dort entsprechend.
Problem für eine Optimierung sind nun nur noch die Interdependenzen, Lagen und Hierarchien der Knotenpunkte. Aber zumindest ist die Anzahl FAKULTÄT(35) hier nicht richtig für die zu analysierenden Möglichkeiten, da es bei einem Bahnnetz um vorgegebene Zweige geht, bei Straßen hingegen um beliebige Verbindungen.
Anzeige
Hinzu kommt noch "umgekehrte Rekursion"
20.11.2017 07:46:50
lupo1
a) vom Knoten fährt man zum entferntesten Bahnhof.
b) Von dem aus arbeitet man bei der Rückkehr die zuerst nächsten Abzweigungen ab.
c) Auch in diesen Abzweigungen fährt man wieder zum entferntesten ("abgezweigtesten") Bahnhof zuerst. Dann weiter mit b)
Dieses Verfahren wird umgekehrt etwa zum Verzeichnis-Durchsuchen durchgeführt, welches auf normaler Rekursion beruht.
Ausnahme zu Beginn, wenigstens erwähnt.
20.11.2017 08:21:03
lupo1
1
|  2
| /
|/
| 3
|/
|
K
Beim allerersten Start (und nur dann!) fährt man natürlich nicht von K aus 1, 2 und 3 ab, sondern man fährt von 1 über 2 über 3 nach K (dadurch spart man einmal K bis zu 1).
Erst dann beginnt man immer bei den verschiedenen K für den jeweils nächsten Zweig, da man ja nicht anders kann (keine Unterbrechnung).
Anzeige

349 Forumthreads zu ähnlichen Themen

Anzeige
Anzeige
Anzeige
Anzeige

Beliebteste Forumthreads (12 Monate)

Anzeige

Beliebteste Forumthreads (12 Monate)

Anzeige
Anzeige
Anzeige