Autor
|
Thema: Wegfindung im Strassennetz (7332 mal gelesen)
|
obiwarn Mitglied
Beiträge: 13 Registriert: 05.05.2005
|
erstellt am: 25. Mai. 2005 18:10 <-- editieren / zitieren --> Unities abgeben:
Hallo, ich bin gerade am erstellen einer Simulation für Kombinierten Verkehr (Strasse & Schiene). Mein Problem: Wie soll ein Fahrzeug den kürzesten Weg von z.B. Hamburg nach München finden. Mein Prof. murmelte was von Dijkstra-Algorithmus, aber wie implementiere ich den in eM-Plant? Das Modell besteht zZ. aus einem Strassennetz (Wege) mit jeweiligen Längenangaben. Kreuzungen bestehen immer aus einem Netzwerk (zB Bahnhof) oder einer Einzelstation (also kein Weg stösst direkt an einen nächsten). In der Grafik habe ich das mal vereinfacht dargestellt: Senke produziert LKW mit Zielangabe. LKW soll Online (wichtig da die Strassenbelastung schwankt, also vor jeder Kreuzung den Wegfindealgorithmus erneut ausführen) den kürzesten Weg zur jeweiligen Senke finden. Ich bin dankbar auch für kleine Denkanstösse oder Befehle die einem dabei behilflich sein könnten. Vielleicht hat ja auch jemand schon was ähnliches mal modelliert und kann mir sein spp-File zusenden. Danke im Vorraus Obi Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 25. Mai. 2005 21:01 <-- editieren / zitieren -->
Hi, kleine Info vorab : soweit ich weis, wird der Dijkstra-shortest-path-Algorithmus bereits in eM-Plant verwendet, und zwar (ab Version 7.0) für die Bestimmung der kürzesten Werkerwege zum jeweiligen Arbeitsplatz. Gruss ------------------ DER SIMULATOR |
Ex-Mitglied
|
erstellt am: 05. Jun. 2005 17:15 <-- editieren / zitieren -->
Hi, das könnte Dich vielleicht interessieren: Laut den eng. Release Notes der neuesten Version 7.5 ist der Dijkstra shortest path-Algorithmus auch für Wegenetze implementiert s. eM-Plant-( English Version) http://www.emplant.de/support/index.html ich habe den Algorithmus zwar zwischenzeitlich auch mit SIMTALK programmiert aber da ist noch ein BUG drin.
Gruss ------------------ DER SIMULATOR
[Diese Nachricht wurde von Simulator am 05. Jun. 2005 editiert.] |
obiwarn Mitglied
Beiträge: 13 Registriert: 05.05.2005
|
erstellt am: 08. Jun. 2005 19:36 <-- editieren / zitieren --> Unities abgeben:
Hallo, würde mich sehr freuen wenn du den Code hier posten könntest auch wenn er fehlerhaft ist. Ich freue mich über alle Denkanstösse bezüglich des prinzipiellen Vorgehens. Ein Problem liegt z.B. darin überhaupt erstmal alle Daten aufzunehmen. D.h. wie lese ich z.B. alle Weglängen und ihre jeweiligen Nachfolger (die Einzelstationen) in einen Array ein? Gruss Obi Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 08. Jun. 2005 22:14 <-- editieren / zitieren -->
Hi, hier der 1.Prototyp für die Übertragung der Wege-Werte: liste01 =tabelle mit Zellen vom Typ object; liste02 =tabelle mit Zellen vom Typ real; Wegenetze für den Dijkstra-Algorithmus werden als Knoten & Kanten definiert. Dies ist hier noch nicht implementiert. Aber vielleicht hilft Dir dieser Code schon mal weiter. Code fuer den Dijkstra (mit Bug :-)) kannst Du auch haben wenn Du willst. Gruss ------------------ DER SIMULATOR |
obiwarn Mitglied
Beiträge: 13 Registriert: 05.05.2005
|
erstellt am: 08. Jun. 2005 22:49 <-- editieren / zitieren --> Unities abgeben:
|
Ex-Mitglied
|
erstellt am: 10. Jun. 2005 16:15 <-- editieren / zitieren -->
Hi, so hier hast Du ein Modell (V7.0) mit dem Dijkstra-Algorithmus (ohne BUG :-)) Basis des Algorithmus ist der C-Code von http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm den ich auf SIMTALK portiert habe. Gruss ------------------ DER SIMULATOR [Diese Nachricht wurde von Simulator am 10. Jun. 2005 editiert.] |
Ex-Mitglied
|
erstellt am: 10. Jun. 2005 20:59 <-- editieren / zitieren -->
Hi, so ich habe das Ganze nochmals etwas zusammengefasst und ein exemplarisches Beispiel dazu modelliert. Die Wegenetze werden jetzt autm. eingelesen und indexiert. Der Dijkstra-Algorithmus wird jetzt von jedem Fahrzeug aufgerufen am Ende eines Weges und berechnet dann den kürzesten Restweg zum vorgegebenen Ziel. Ein Aspekt, der sich während der Modellierung ergab: Durch den Dijkstra-Algorithmus reduziert sich Modellierung von Wegenetzen und Zielfindung deutlich, da nun - im Gegensatz zur bisherigen Modellierung - man nicht mehr explizit die Wegstrecke von Quelle->A-> B->C...Ziel direkt/indirekt angeben muß im Modell, sondern diese als "Abfallprodukt" ja jetzt mitberechnet wird! D.h. das Fahrzeug ruft an einer beliebigen Stelle im Wegenetz den Algorithmus mit dem Ziel-Objekt als einzigen Parameter. Es wäre weiterhin durchaus möglich, z.B. die Streckenbelastung bei der Berechnung des kürzesten Restweges auch zu berücksichtigen. Aber ich glaube, dieses Modell zeigt schon ganz gut eine der vielen Facetten von eM-Plant. Gruss
------------------ DER SIMULATOR [Diese Nachricht wurde von Simulator am 12. Jun. 2005 editiert.] |
obiwarn Mitglied
Beiträge: 13 Registriert: 05.05.2005
|
erstellt am: 13. Jun. 2005 00:34 <-- editieren / zitieren --> Unities abgeben:
Tausend Dank für deine Mühen, ich hatte zwischenzeitlich leider schon einen eigenen geschrieben (auch nach Wikipedia) der deinem sehr ähnelt, aber totzdem sind deine Sourcecodes immer wieder eine grosse Hilfe SimTalk zu erlernen. Danke und Gruss Obi Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
93Aero Mitglied Ing
Beiträge: 106 Registriert: 02.12.2004
|
erstellt am: 27. Jun. 2005 11:38 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
|
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 01. Mrz. 2007 11:09 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Hallo Simulator, ich habe eine ähnliche Aufgabenstellung und auch wenn der Dijkstra Code in eM Plant schon implementiert ist, würde mich sehr interessieren, wie Du das Problem damals gelöst hast. Die beigefügte Datei (ohne Bug) kann ich leider nicht öffnen. Gruß Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 01. Mrz. 2007 11:30 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
|
Ex-Mitglied
|
erstellt am: 01. Mrz. 2007 11:34 <-- editieren / zitieren -->
Die jpg-Erweiterung ist ein kleines workaround, da eMPlant-Dateien (*.spp) in den Foren nicht upgeloaded werden duerfen. ------------------ Der Simulator
|
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 01. Mrz. 2007 15:11 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Der Grund warum ich frage ist der. Irgendwie scheint die automatische Wegfindung nicht zu funktionieren. Ich habe mal das Foto beigefügt. Wie man erkennen kann, werden 2 verschiedene Fahrzeuge, jeweils links und rechts in das Raster reinfahren und dann die ausgesuchten Senken ansteuern. Nur fahren sie zuerst nahezu überall hin bevor sie sich in die Senken begeben, bisweilen drehen sie noch ein paar Runden. Allerdings muss ich sagen, dass ich aus deiner Programmierung nicht schlau werde. Du hast Gewichtung und Distanz zum Abfragen eingebaut. Reicht denn nicht eines? Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 01. Mrz. 2007 15:28 <-- editieren / zitieren -->
@1 es werden eigentlich nur die Gewichtungen(=Entfernung) zwischen den Knoten als Eingabe beruecksichtigt. Die Werte in der "distances"-Spalte sind temporäre Werte, die zu Anfang mit einem infinte-Wert (=9999999) initialisiert werden. @2 Könnte sein, dass Du einen Weg-Baustein als Ziel eingeben musst. Du hast Senken als Ziel eingegeben. Konnte dies nicht testen, da ich gerade keine 7.5-Version parat habe. ------------------ Der Simulator |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 01. Mrz. 2007 16:01 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
@1 Ok, das erklärt zumindest dies. Ich werde mich aber noch mehr damit befassen müssen, bevor/ob ich noch mehr fragen stellen kann. Bisher habe ich den ganzen Aufbau noch nicht durchschaut. @2 Ich habe das Ziel jetzt durch einen Wegbaustein ersetzt, allerdings ist das Verhalten das selbe. Die Fahrzeuge fahren nach wie vor ziellos durch die Gegend. Aber die Idee klang schon mal ganz plausibel. Ich vermute einfach, dass eM Plant zwar für sehr einfache Wegfindungen durchaus in der Lage ist, aber bei komlpexeren/umfangreicheren Strukturen scheint es eventuell überfordert zu sein. Ist aber nur der erste Eindruck. Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 01. Mrz. 2007 16:41 <-- editieren / zitieren -->
ganz sicherlich ist eMPlant durch das Modell nicht ueberfordert! so gehts Gib mal als Zielparameter nicht den gesamten Pfad, sondern nur den Namen des Zieles ein. ------------------ Der Simulator |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 01. Mrz. 2007 17:04 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Oh das hat mich ohne Grund entmutigt, denn die Idee das Ziel direkt einzugeben war mir zu Beginn zwar auch gekommen, aber da die Stelle dann rot unterlegt war, hatte ich es wieder nicht weiter verfolgt. Immerhin funktioniert die Wegfindung, allerdings auch nur statisch, denn wenn man das System etwas füllt und damit auch bestimmt Wegbausteine blockiert sind, errechnet das System keine neuen Wege sondern beharrt auf den alten Weg, solange bis dieser wieder freigegeben ist, was u.U. niemals der Fall ist. Aber vielen Dank für Dein Bemühen. Wie immer bekommt man hier immer Hilfe! Danke!! Gruß Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 01. Mrz. 2007 17:10 <-- editieren / zitieren -->
|
Ex-Mitglied
|
erstellt am: 01. Mrz. 2007 19:51 <-- editieren / zitieren -->
anbei ein einfaches Beispiel zur dynamischen Routenberechnung via Dijkstra-Algorithmus ------------------ Der Simulator |
Ex-Mitglied
|
erstellt am: 01. Mrz. 2007 20:25 <-- editieren / zitieren -->
sowie ein direkter Vergleich (dynamisch/statisch) ------------------ Der Simulator |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 02. Mrz. 2007 09:09 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
|
math4fun Mitglied
Beiträge: 167 Registriert: 12.12.2005
|
erstellt am: 05. Mrz. 2007 13:31 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Über die Info-Seite im Tab-Viewer kann man den Bausteinkasten Transport.spp öffnen, der in seinem Assistenten diesen Dijkstra-Algorithmus enthält. Eine gute Erklärung ist in dem Lehrbuch K. Neumann; M. Morlock: Operations Research. Hanser Verlag 1993. enthalten. ------------------ PM www.math4fun.de Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 06. Mrz. 2007 16:13 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Hallo Simulator, ich habe in den letzten Tagen mir den Quell Code angeschaut und hätte ein paar Fragen an Dich. (ich habe mir als Neuling vermutlich eine zu dicke Aufgabe genommen , aber wenn das einmal explizit erklärt ist, sollte es sitzen ) Folgende Frage: 1. in der Methode m_dijkstra self.init : wenn ich den debuggger laufen lasse, springt er in einer Methode, die ich nicht auf dem Interface finde. Könntest Du dazu etwas bitte mehr schreiben? Ich hatte zuerst angenommen, dass sich damit nur die Methode m_dijkstra selbst initialisiert. 2. in der Methode m_dijkstra ab der Zeile js:=destination bin ich mir nicht mehr sicher, was der Zweck ist. Lässt Du hier von der Gegenseite aus (also vom Ziel aus) wieder zurück bis zu Quelle vergleichen? Ich kann das im Bezug auf s_path, der ja eigentlich vom Startpunkt ausgeht, nicht ganz nachvollziehen. 3. in der Methode mStart die Zeile liste := m_dijkstra (str_to_num(obj1.etikett),str_to-num(obj2.etikett)); birgt gleich 2 Dinge, die ich in der Onlinehilfe nicht finden konnte. Wieso werden hier Strings in Real umgewandelt und was hat es mit dem Etikett auf sich? Es wäre wirklich genial wenn Du mir das erklären könntest. Ich plane den selben Code auch in Delmia Quest einzubauen. Dafür muss ich das hier aber erst mal richtig verstanden haben. Vielen Dank!!!
Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 06. Mrz. 2007 17:34 <-- editieren / zitieren -->
@1 init (Methode) bzw. graph (Tabelle) sind benutzerdefinierte Attribute der m_dijkstra- Methode. Wenn Du die Methode oeffnest und den Reiter "Extras" anwählst, kannst Du dort die benutzerdefinierten Attribute definieren bzw. bearbeiten. @2 s_path ist das eigentliche Ergebnis des Algorithmus- also die Liste mit den Knoten (Zwischenzielen) der Route zwischen "source" und "destination". Mit js:=destination; s_path.einfuegen(1,js); wird der definierte Zielknoten in die Tabelle eingetragen und in der folgenden repeat-Schleife alle Zwischenknoten bis zum derzeitigen Standortknoten. @3 Alle Zielobjekte (Wege/Senken) bekommen beim Initialisieren eine Knotennummer (mit denen der Algorithmus arbeitet). Diese Knotenummer wird der Einfachheit halber unter dem Standard-Objektattribut "etikett" (string)abgespeichert, damit nicht ein weiteres Attribut angelegt werden braucht.
Über "objekt.etikett" kann nun auf die Knotennummer zugegriffen werden. Da es sich um ein String-Attribut handelt, wird das Attribut beim Methodenaufruf in einen numerischen Wert umgewandelt. ------------------ Der Simulator
|
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 07. Mrz. 2007 15:17 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Vielen Dank, jetzt wird es lichter im Wald. Ich bin mir nur nicht sicher, ob man die Methode über mehrere Netzwerke verwenden kann, da Du in der Init Methode das netz:=current angeben hast. Gibt es denn eine Möglichkeit via Übergänge in mehreren Netzwerken zu arbeiten? Ich habe zuerst versucht den Pfad zu den Modellen (also netz:=.modelle; ) anzugeben, jedoch eine Fehlermeldung erhalten. Gruß [Diese Nachricht wurde von Ragnar am 07. Mrz. 2007 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 07. Mrz. 2007 17:47 <-- editieren / zitieren -->
was hast Du vor ? ".modelle" ist der Pfad zum Verzeichnis "modelle" und nicht der Pfad zu einem Netzwerk. wenn Deine Wege/Routen in anderen (Sub-)Netzen liegen, kannst Du z.B. ueber eine rekursive Methode alle relevanten Wege "aufspüren". Du kannst aber auch ueber eine Schleife alle (Weg.anzahlkinder) Weg-Instanzen (weg.kindnr(index)) erfragen. ------------------ Der Simulator
|
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 07. Mrz. 2007 19:09 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Servus! Ich versuche nur einige Wegnetze in ein Subnetzwerk zu verlegen. Auf dem Hauptnetzwerk soll nur noch das grobe Layout zu sehen sein, mit Quellen und Zielpunkten. Ich werde dann morgen schauen, wie Du das mit dem "rekursiver" Methode meinst, bzw. inwiefern man nach allen Kindern suchen kann. In der Onlinehilfe war leider nichts angegeben. Den Befehl "netz" kenn ich nur durch Dich, Simulator. Schönen Abend! Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 08. Mrz. 2007 10:35 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Guten Morgen, also ich habe es jetzt geschafft die Methode auch in den Unternetzwerken laufen zu lassen, indem ich die Methode auch in die Unternetzwerke eingefügt habe, dort einen neuen Pfad suchenlasse und damit eine separate Rechnung durchführt, nur ergab sich jetzt das Problem, dass die Übergänge nicht als Ziel ausgewählt werden können. Ich habe nun Wege direkt vor den Übergang gesetzt, die dann die Fahrzeuge rausziehen. Theoretisch könnte ich damit also jetzt leben. Kann man eventuell die Zoomeinstellung von eM-Plant verändern? Ich würde gerne noch weiter rauszoomen, als derzeit möglich. Gruß [Diese Nachricht wurde von Ragnar am 08. Mrz. 2007 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Homer Simpson Mitglied
Beiträge: 345 Registriert: 14.09.2005
|
erstellt am: 08. Mrz. 2007 11:54 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Tatsächlich ist es möglich bis zum Faktor 10 heraus- und hinein-zuzoomen (obwohl ich mich frage, ob dies Sinn macht). Dazu wählt man im Kontextmenü des Netzwerks "Attribute und Methoden anzeigen" aus (wenn das Netzwerk eine Klasse ist, dann öffnet man das Kontextmenü natürlich in der Klassenbibliothek). Im sich öffnenden Fenster doppelklickt man auf den Eintrag "ZoomFaktor" und gibt z.B. "0.1" ein. Sinnvollerweise schaltet man danach das Raster aus. [Diese Nachricht wurde von Homer Simpson am 08. Mrz. 2007 editiert.] Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 08. Mrz. 2007 16:06 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
|
Ex-Mitglied
|
erstellt am: 08. Mrz. 2007 19:20 <-- editieren / zitieren -->
Und was untersuchst Du da genau ? ------------------ Der Simulator |
Ragnar Mitglied Student
Beiträge: 27 Registriert: 26.02.2007
|
erstellt am: 09. Mrz. 2007 08:42 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Guten Morgen, ich untersuche, inwiefern man den eM-Plant von Bewegungen in einem Zimmer bis hin zu größeren Objekten wie ganze Häuserblocks verwenden kann. In diesen Thread waren einige Aspekte, die ich sehr interessant empfand. Dein o.g. gesendetes Beispiel, Simulator, illustriert, dass dies zumindest auf raumgröße sehr gut machbar ist. Gruß Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
Ex-Mitglied
|
erstellt am: 09. Mrz. 2007 10:20 <-- editieren / zitieren -->
Ich weis, dass der user "OPA" aus diesem Forum eine Bausteinbibliothek fuer freie Bewegungen entwickelt hat. Schau mal auf seine homepage. ------------------ Der Simulator |
zigeuner Mitglied Studentin
Beiträge: 9 Registriert: 25.04.2017 Plant Simulation Version 13
|
erstellt am: 09. Jun. 2017 12:00 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Hallo zusammen, derzeit arbeite ich einen Modell mit den kürzesten Wege. Ich finde diesen Thread sehr interessant. Aber ich verstehe eine Quellcode von Methode m_dijktra nicht.
Code: (source,destination : integer) : list
Wie ich verstanden hab, dass (source, destination : integer) Parameter sind. Wieso wird (source,destination : integer) : list kombiniert oder gibt es eine Bedeutung dafür? Wie kann man auf die neue Syntax 2.0 umwandeln? Danke im Voraus. VL Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |
nadin1223 Mitglied Ing.
Beiträge: 949 Registriert: 29.03.2016
|
erstellt am: 09. Jun. 2017 13:45 <-- editieren / zitieren --> Unities abgeben: Nur für obiwarn
Hallo zigeuner, Methodenkopf: Code: /*SimTalk1.0*/ (source,destination : integer) : list
Code: /*SimTalk2.0*/ param source,destination: integer -> list
zwei Integer übergeben-> eine Liste kommt zurück vg Nadin ------------------ „Die einfachste Art an korrekte Informationen zu gelangen ist, etwas Falsches in ein Forum zu posten und auf die Korrektur zu warten.“ Matthew Austern Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP |