---

wegfind.jpg

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

---

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 

---

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.]

---

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

---

dijkstra01.JPG

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 

---

Vielen Dank soweit.

Ja dein anderer Code würde mich auch interessieren.

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

dijkstra_01.spp.jpg

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.]

---

dijkstra03.JPG

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.]

---

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

---

Noch eine gute Seite dazu:
http://wwwmayr.informatik.tu-muenchen.de/skripten/ead_ws9899_html/node81.html

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

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

---

Danke,

hat sich erledigt. Die Datei wurde zwar als Jpeg gespeichert aber wenn man es von eM Plantmanager aus startet, funktioniert es. 

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Die jpg-Erweiterung ist ein kleines workaround, da
eMPlant-Dateien (*.spp) in den Foren nicht upgeloaded werden duerfen.

------------------
Der Simulator

---

Dijkstra_Wege.JPG

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

---

@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

---

@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

---

d01.jpg d01.spp.jpg

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

---

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

---

Nun, die dynamische Wegfindung wurde ja schon besprochen
s.  http://ww3.cad.de/foren/ubb/Forum262/HTML/000112.shtml#000007
und funktioniert mit dem selbstprogrammierten Dijkstra-Algorithmus

Ich muss mal gucken, ob ich das Modell d03.spp noch irgendwo habe

------------------
Der Simulator

---

d03.JPG d03.spp.jpg

anbei ein einfaches Beispiel zur dynamischen Routenberechnung via Dijkstra-Algorithmus

------------------
Der Simulator

---

d04.JPG d04.spp.jpg

sowie ein direkter Vergleich (dynamisch/statisch)

------------------
Der Simulator

---

Ich bin jetzt offiziell beeindruckt, sowohl von den Fähigkeiten des eM-Plant, als auch von Dir, Simulator. 

Viele Grüße!!!

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Ü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

---

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

---

@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

---

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

---

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

---

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

---

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

---

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

---

Danke für den Hinweis.

Ich teste gerade im Bezug auf eM-Plant das Machbare. Dabei gehe ich etwas weiter als für das, wofür das Programm eigentlich entwickelt wurde. Vielen Dank nochmals!

Gruß

Eine Antwort auf diesen Beitrag verfassen (mit Zitat/Zitat des Beitrags) IP

---

Und was untersuchst Du da genau ?

------------------
Der Simulator

---

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

---

Ich weis, dass der user "OPA" aus diesem Forum eine Bausteinbibliothek
fuer freie Bewegungen entwickelt hat. Schau mal auf seine homepage.

------------------
Der Simulator

---

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

---

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