Wegeoptimierung
0 
MudGuard
0 0 
Felix Riesterer
0 0 0 
TS
0 Felix Riesterer
0 TS
0 
Gunnar Bittersmann
0
Wegeoptimierung
Moin,
mit der Hilfe dieses Forums, das mich auf leaflet (schieben und zoomen eigener Bilder wie eine Landkarte) aufmerksam machte, kann ich erstmalig die Terminpläne von Messe-Besuchern optisch unterstützen.
Die Termine werden mit einem Programm gebucht, nachdem die Messebesucher ihre Kontaktwünsche eingegeben haben.
Erst jetzt fällt auf, dass die Wege von einem Aussteller zum anderen kreuz und quer durch die Messehallen führen können, weil bisher im Programm keine Wege-Optimierung vorgesehen ist.
Termine 6 - 7 - 8 total bescheuert, 9 - 10 - 11 auch ein Fitness-Programm.
Wer hat sich schon mit Wege-Optimierung beschäftigt und kann mir ein paar Tipps geben für Anfänger?
Die Stand-Nummern sind dem Buchungs-Programm bekannt, aber Entfernungen lassen sich daraus nicht ermitteln. Es müssen wohl die x- und y-Koordinaten hinterlegt werden?
Linuchs
-
Hi,
Die Stand-Nummern sind dem Buchungs-Programm bekannt, aber Entfernungen lassen sich daraus nicht ermitteln. Es müssen wohl die x- und y-Koordinaten hinterlegt werden?
Die Koordinaten der Stände reichen m.E. nicht aus. Das würde nur dann reichen, wenn die tatsächlichen Laufwege mit der kürzesten Verbindung zwischen den Ständen übereinstimmen. Aber da sind ja Hindernisse im Weg - die anderen Stände, nicht-begehbare Flächen, ...
cu,
Andreas a/k/a MudGuard-
Moin,
Die Koordinaten der Stände reichen m.E. nicht aus. Das würde nur dann reichen, wenn die tatsächlichen Laufwege mit der kürzesten Verbindung zwischen den Ständen übereinstimmen. Aber da sind ja Hindernisse im Weg - die anderen Stände, nicht-begehbare Flächen, ...
Nun habe ich ein Problem definiert und du legst die Latte gleich fünf Einheiten höher.
Das Problem ist bekannt und hier könnte schon der erste Tipp kommen. Muss man von jedem Messe-Stand zu jedem anderen die Wege abmessen? Wie machen es denn die Navi-Programme für Fahrzeuge? Ich habe hier von A nach B 15 km Luftlinie, aber beim Fahren werden es locker 50 km, weil eine Fluss ohne Brücken dazwischen ist.
Der erste Lösungsansatz wäre wohl, Folgetermine möglichst in derselben Halle zu machen. Das wäre doch schon ein Erfolg.
Oder "kachelt" man ein Gebiet oder "wabt" man es mit Sechsecken wie Tarifgebiete im Nahverkehr?
Linuchs
-
Lieber Linuchs,
vermutlich haben die Navigationsprogramme ein Netz aus Wegpunkten, welches sie bei Bedarf vermessen, um die kürzeste Strecke von A nach B zu finden. Im Grunde habe ich etwas ähnliches mit JavaScript schon einmal gemacht.
Liebe Grüße,
Felix Riesterer.
-
Lieber Felix,
Im Grunde habe ich etwas ähnliches mit JavaScript schon einmal gemacht.
Die meisten Punkte haben zwei Nachbarn. Ist klar auf einer Strecke. Einen in Fahrtrichtung, einen huinter sich. Manche Punkte haben drei Nachbarn. Das ist dann eine Einmündung? Und der letzte Punkt einer Sackgasse hat nur einen Nachbarn.
Ich sehe aber keinen Punkt mit vier Nachbarn, was für eine Kreuzung wohl nötig wäre.
Wie ist denn das Konzept des Rechnens? Wenn ich nach Westen müsste, aber dort ein Fluss im Weg ist, kann ich im Norden oder im Süden eine Brücke suchen, aber ich entferne mich ja vom Ziel.
Gibt es da eine Grund-Idee? Vergleichbar mit der, dass man aus einem Labyrinth herauskommt, wenn man die linke oder rechte Hand an eine Wand legt und dann mit dieser Hand immer Kontakt zur Wand hält?
Liebe Grüße, Linuchs
-
Wie ist denn das Konzept des Rechnens? Wenn ich nach Westen müsste, aber dort ein Fluss im Weg ist, kann ich im Norden oder im Süden eine Brücke suchen, aber ich entferne mich ja vom Ziel.
Gibt es da eine Grund-Idee? Vergleichbar mit der, dass man aus einem Labyrinth herauskommt, wenn man die linke oder rechte Hand an eine Wand legt und dann mit dieser Hand immer Kontakt zur Wand hält?
Grundlage für das Routing Dijkstra-Algorithmus. Im Netz gibt es eine ganze Reihe von Implementierungen auch in Javascript. In der Praxis habe ich mich aber noch nicht damit befasst. Die größte Hürde ist momentan der Aufbau des Graphen für das Wegenetz (Art der Datenstruktur). Bei einem überschaubaren Bereich wie z.B. ein Messegelände dürfte das aber schon zu machen sein.
-
Hello,
Wie ist denn das Konzept des Rechnens? Wenn ich nach Westen müsste, aber dort ein Fluss im Weg ist, kann ich im Norden oder im Süden eine Brücke suchen, aber ich entferne mich ja vom Ziel.
Gibt es da eine Grund-Idee? Vergleichbar mit der, dass man aus einem Labyrinth herauskommt, wenn man die linke oder rechte Hand an eine Wand legt und dann mit dieser Hand immer Kontakt zur Wand hält?
Grundlage für das Routing Dijkstra-Algorithmus. Im Netz gibt es eine ganze Reihe von Implementierungen auch in Javascript. In der Praxis habe ich mich aber noch nicht damit befasst. Die größte Hürde ist momentan der Aufbau des Graphen für das Wegenetz (Art der Datenstruktur). Bei einem überschaubaren Bereich wie z.B. ein Messegelände dürfte das aber schon zu machen sein.
Du warst schneller ;-)
Wie das genau umgesetzt wird, habe ich leider bisher auch noch nicht durchschaut.
Kürzester Pfad (bewertet)Liebe Grüße
Tom S.--
Die Krawatte ist das Kopftuch des Westens
-
-
Lieber Linuchs,
Die meisten Punkte haben zwei Nachbarn. Ist klar auf einer Strecke. Einen in Fahrtrichtung, einen huinter sich. Manche Punkte haben drei Nachbarn. Das ist dann eine Einmündung? Und der letzte Punkt einer Sackgasse hat nur einen Nachbarn.
richtig beobachtet.
Ich sehe aber keinen Punkt mit vier Nachbarn, was für eine Kreuzung wohl nötig wäre.
Eine solche gab das Hintergrundbild nicht her. Aber mein Script sollte das auch mit Kreuzungen können (ungetestet). Was hält Dich davon ab, das Prinzip zu testen?
Wie ist denn das Konzept des Rechnens? Wenn ich nach Westen müsste, aber dort ein Fluss im Weg ist, kann ich im Norden oder im Süden eine Brücke suchen, aber ich entferne mich ja vom Ziel.
Die Anzahl Schritte (aka Wegpunkte) wird gemessen. Wenn es überhaupt dazu kommt, dass das Ziel erreicht wird, dann wird die Möglichkeit mit den wenigsten Schritten ausgewählt. Es hätte also einen Sinn, Deine Karte mit Wegpunkten (denke Schritte, nicht Ziele!) zu versehen und diese dann in meinem Script einzutragen. Dann sollte der Smiley auch auf Deiner Karte laufen können.
Wenn Du willst, dann sende mir doch ein JPEG per Mail und ich schaue mal, ob ich das hinkriege…
Liebe Grüße,
Felix Riesterer.
-
-
Hello Felix,
vermutlich haben die Navigationsprogramme ein Netz aus Wegpunkten, welches sie bei Bedarf vermessen, um die kürzeste Strecke von A nach B zu finden. Im Grunde habe ich etwas ähnliches mit JavaScript schon einmal gemacht.
Das war die Idee, aus der ich mal ein Spiel machen wollte.
Hast Du dazu eine (deutsche) Doku erstellt?Liebe Grüße
Tom S.--
Die Krawatte ist das Kopftuch des Westens
-
-
-
-
@@Linuchs
Erst jetzt fällt auf, dass die Wege von einem Aussteller zum anderen kreuz und quer durch die Messehallen führen können, weil bisher im Programm keine Wege-Optimierung vorgesehen ist.
Termine 6 - 7 - 8 total bescheuert, 9 - 10 - 11 auch ein Fitness-Programm.
Die Handlungsreisenden haben eben so ihre Probleme.
Die Stand-Nummern sind dem Buchungs-Programm bekannt, aber Entfernungen lassen sich daraus nicht ermitteln. Es müssen wohl die x- und y-Koordinaten hinterlegt werden?
Die werden – wie MudGuard schon sagte – nicht helfen, wenn die Messebesucher nicht Luftlinie durch die Stände laufen können. Du brauchst eine n×n-Matrix mit allen Abständen zwischen jeweils zweien der n Stände.
Die gute Nachricht: Du brauchst nur eine Hälfte der Matrix – wenn denn der Abstand von A nach B gleich dem von B nach A ist. Das gilt für eine wenig gefüllte Messehalle.
Es kann einen bevorzugten Rundgang geben und, wenn die Hütte voll ist, nicht ratsam sein, gegen den Strom zu schwimmen. Dann ist der Weg von A nach B ein anderer als der von B nach A; die Matrix also nicht symmetrisch.
LLAP 🖖
--
“When UX doesn’t consider all users, shouldn’t it be known as ‘Some User Experience’ or... SUX? #a11y” —Billy Gregory -
Erstmal danke für eure Gedanken und Links.
Die Termine werden in mehreren Buchungsläufen ermittelt. Da gibt es die grünen, das sind Vorträge und Workshops nur zu bestimmten Zeiten. Die werden zuerst gebucht. Besucher sind nur zu bestimmten Zeiten anwesend (ein Tag oder beide Tage, später kommend, eher gehend). Buchungen für Besucher-Gruppen müssen berücksichtigen, dass alle Teilnehmer der Gruppe diesen Termin frei haben. Und, und, und.
Ich denke, eine erste Optimierung läuft darauf hinaus, nach Abschluss der Buchungen rote Termine eines Einzel-Besuchers zeitlich zu vertauschen. Aber wie?
Ich sortiere nach Uhrzeit und versuche, auch die Stand-Nummern auf- oder absteigend zuzuordnen, immerhin sind benachbarte Nummern in der Nähe zueinander. Welche Konsequenz hat das? Morgens drängelt sich alles auf den Ständen mit kleiner Nummer, bei den hohen Nummern gähnende Leere?
Das bisherige "Zufallsprinzip" hat ja auch die Auslastung zufällig über die Messezeit verteilt.
Linuchs
-
Hallo Linuchs,
Die Termine werden in mehreren Buchungsläufen ermittelt. Da gibt es die grünen, das sind Vorträge und Workshops nur zu bestimmten Zeiten. Die werden zuerst gebucht. Besucher sind nur zu bestimmten Zeiten anwesend (ein Tag oder beide Tage, später kommend, eher gehend). Buchungen für Besucher-Gruppen müssen berücksichtigen, dass alle Teilnehmer der Gruppe diesen Termin frei haben. Und, und, und.
Du sagst es: Und, und, und. Wenn Du Dich wirklich daran wagen möchtest, musst Du Dir darüber im Klaren sein, dass das eine äußerst komplexe und sehr schwierig zu lösende Problemstellung ist. Die Wegoptimierung ist wahrscheinlich das mit Abstand am einfachsten zu lösende Problem. Eigentlich hast Du aber ein klassisches Scheduling-Problem, bei welchem die Wegoptimierung nur einen kleinen Teil darstellt.
Du möchtest die Messestände und Veranstaltungen (resource) optimal ausnutzen, d.h. die Besucher (job) sollen optimal auf Ressourcen verteilt werden (task). Dabei muss eine Vielzahl von Restriktionen (constraints) beachtet werden. Du hast also eine NP-vollständige Problemstellung.
Exakte Verfahren, welche immer die gültige „beste Lösung“ finden (z.B. Brute Force oder Branch-and-Bound), scheiden daher aus zwei Gründen aus: Erstens benötigen sie viel zu viel Rechenzeit und zweitens kannst Du nicht garantieren, dass es überhaupt eine Lösung gibt, welche alle Restriktionen auflösen kann.
Das ist auch eigentlich der wichtigste Punkt: Du musst Dir bevor Du überhaupt anfangen kannst über alle möglichen Restriktionen im Klaren sein. Außerdem darüber, was passieren soll, wenn irgendeine Restriktion auf keinen Fall eingehalten werden kann (Beispiel: Ein Besucher kann zeitlich nicht an zwei Orten gleichzeitig sein).
Zuletzt musst Du Dir vorher Gedanken machen, mit welchem Optimierungsergebnis Du zufrieden wärst. Üblicherweise definiert man Zielgrößen (objectives bzw. targets oder goals), bei deren Erreichen Gewinne (rewards) vergeben werden. Ein Algorithmus versucht dann, diese Gewinne zu maximieren. Dass Du Dir vorher genau Gedanken über das alles machen und mögliche Szenarien entwickeln musst, ist u.a. im No-free-Lunch-Theorem beschrieben: Es existiert kein Algorithmus, der für alle Fälle am besten geeignet ist.
Was Du benötigst sind also Heuristiken, welche die Problemstellung optimieren. Unterscheiden musst Du zwischen Eröffnungs- und Verbesserungsheuristiken. Bei der Eröffnung wird überhaupt erstmal eine gültige Lösung erzeugt, die anschließend verbessert werden kann. Deine zufällige Terminvergabe wäre ein Beispiel dafür, würdest Du auch die Restriktionen beachten; i.Allg. ist dieses Vorgehen aber das denkbar schlechteste.
An anderer Stelle hattest Du gefragt, wie Navis das machen. @Gunnar Bittersmann hatte zudem das Problem des Handlungsreisenden ins Spiel gebracht. Navis haben üblicherweise einen vielstufigen Optimierungsprozess, d.h. sie verwenden mehrere Optimierungsstufen hintereinander. Grundlage dafür ist ein - von @Felix Riesterer angesprochnes - engmaschiges Netz von Wegpunkten. Diese Wegpunkte bilden Knoten und werden durch Kanten miteinander verbunden - @osm sprach den Dijkstra-Algorithmus an, bei welchem das recht anschaulich ist. Die insgesamt eingesetzten Algorithmen orientieren sich dann am Problem des Handlungsreisenden ohne Rückkehr. Zur Planung der Route sind die Straßen und Wegpunkte zusätzlich gewichtet, was den angesprochenen rewards entspricht.
So, nach dem ganzen allgemeinen Vorgeplänkel: Aus meiner eigenen Erfahrung heraus raus kann ich Dir empfehlen, Dich zuerst einmal mit dem Problem des Handlungsreisenden und den zugehörigen Algorithmen zu beschäftigen. Das Problem ist gut untersucht und man kann dabei sehr viel lernen. Alles andere ist für den Anfang viel zu viel und man wird nur mit großen Schwierigkeiten überhaupt etwas brauchbares produzieren.
Für den ersten Einstieg könntest Du Dir für die Eröffnung sowas wie den Sweep-Algorithmus oder die Nächster-Nachbar-Heuristik ansehen. Für die Verbesserung bspw. Simulierte Abkühlung, Evolutionäre und dabei insbes. Genetische Algorithmen oder die Ameisenkolonie (hier übrigens eine sehr schicke, weil anschauliche, Implementierung). Darüber hinaus gibt es noch unzählige andere Verfahren.
Wie gesagt halte ich persönlich das für einen guten Start um sich mit der Materie auseinanderzusetzen. Wenn Du konkrete Fragen hast, kann man Dir auch sicher einen Wink in die richtige Richtung geben. Ansonsten ist aus meiner Sicht die Problemstellung aber zu komplex, um allgemein hier im Forum besprochen werden zu können.
Gruß und viel Erfolg
Dennis
-