ich habe 12 Postalische Adressen in NRW und möchte jetzt die Mitte finden, das fas alle die gleiche Anfahrt haben.
Parameter:
12 Adressen [ PLZ, Ort, Straße, Hausnummer ]
Maximalgeschwindigkeit 80 km/h da LKW
Routing sollte nur Straßen benutzen
Das Ergebnis sollte eine Karte mit 12 Wegen zu einem gefunden Mittelpunkt.
Dann würde ich vom gefunden/errechnetem Mittelpunkt eine Adresse suchen wo sich alle dann treffen.
Ich würde auch ein Script nehmen (python, etc.) aber auch eine Oberfläche.
Leider hat hier die Suche im Forum und auch im Netz zu diesem Thema nicht weitergeholfen.
Wer einen Tipp hat oder ein gute Quelle zum durchlesen, darüber würde ich mich freuen.
Ganz einfach: Such dir einen Punkt der möglichst weit weg liegt. Zum Beispiel in Kasachstan. Dann werden alle in etwa die gleiche Anfahrtszeit haben.
Ansonsten behaupte ich, dass die Aufgabe nicht sinnvoll lösbar ist. Wenn du irgendwas in der Mitte der Teilnehmer wählst, wirst du immer einige haben mit langer Anfahrt und einige mit kurzer Anfahrt. “fast alle” ist nicht möglich.
Also leb damit und such einfach irgendeinen größeren Parkplatz der halbwegs zentral liegt. Oder fahr nach Kasachstan.
Das Problem ist nicht ganz trivial, ich würde dazu raten, das per Hand zu machen (wenn das nicht jeden Tag wieder neu geschehen soll).
Es dürfte bei 12 Orten kaum einen Punkt geben, der genau in der Mitte liegt.
Druck dir eine Karte aus, auf der alle Punkte eingezeichnet sind und verbinde alle Punkte mit allen.
Die Stellen in dem Knäuel, bei denen sich die meisten Linien treffen, sind schon mal gute Kandidaten.
Wenn es allerdings genauer sein soll, müssen (und sollen vermutlich auch) die Abstände zwischen den Orten durch die Wegzeiten ersetzt werden (oder ggf. durch eine Funktion, die auch noch den Spritverbrauch, die Uhrzeit und Ähnliches berücksichtigt).
Dann rücken einige Punkte zusammen, während andere auseinander driften.
Auch so ein Graph liefert dann Anhaltspunkte, wo das Zentrallager (oder was auch immer) günstig zu platzieren wäre.
Für jeden der Kandidaten errechnet man dann die Summe der Abstände/Zeiten zu den 12 Orten und vergleicht die Summen miteinander.
Eventuell wird man das nochmal ändern, etwa weil ein Autobahnstück ständig Staus aufweist, oder alle Fahrer beschäftigt sein sollen und nicht die einen 8 Stunden unterwegs sein sollen, während ein paar andere nur gerade umparken müssen…
Die gute alte Wetware Brain 1.0 liefert da noch immer recht brauchbare Ergebnisse.
Ansonsten: Vielleicht Logistik studieren (oder in dem Zusammenhang suchen, ob es mittlerweile bezahlbare und nicht nur scharlatanische Software für gibt).
Da kommen mitunter lustige Sachen bei raus… Zu mindestens kann man sich so dem (theoretischen) Zentrum recht gut annähern. Insgesamt erinnert mich das an das Problem des Handlungsreisenden…
Bei mehr als drei Adressen ist die Aufgabe “gleiche Anfahrt” nicht lösbar.
Das sieht man an einem Modell ohne Straßen nur mit Entfernung:
Bei zwei Punkten liegen die Punkte gleicher Entfernung auf der Mittelsenkrechten, bei drei Punkten auf dem Schnittpunkt aller drei Mittelsenkrechten, dem Umkreismittelpunkt. Ein vierter Punkt hat nur dann die selbe Entfernung, wenn er auf dem Umkreis liegt.
Wenn man als Maßzahl eine per Router berechnete Zeit (Isochrone) und nicht die Entfernung per Luftlinie nimmt, wird es aufwendiger, aber am Prinzip ändert es nichts.
Im Prinzip machbar sind nur Minimierungslösungen etwa der Art:
Die Summe aller Zeiten vom Startpunkt soll minimal werden.
Die Summe der Abweichungen von einem Mittelwert der Zeiten soll minimal werden (“ungefähr gleich”).
Heuristisch ließe sich das so angehen (ohne Gewähr):
Einen Startort (Kreuzung) auswählen und Summenwert ermitteln
Von der Kreuzung in alle Richtungen einen neuen Punkt wählen und Summenwert von dort aus ermitteln
In Richtung der geringeren Werte die nächste Kreuzung wählen und von dort aus dasselbe wiederholen.
Wenn sich in alle Richtungen (außer der Herkunft) ein höherer Wert ergibt: Diesen Zweig beenden.
Zwischen der Kreuzung mit dem niedrigsten Wert, die zum Schluss übrig bleibt und der Nachbarkreuzung mit dem nächst niedrigen Wert liegt der gesuchte Ort.
Achtung:
Je nach gewähltem Startpunkt findet man u.U. nur ein lokales, nicht das absolute Minimum.
Der Aufwand nimmt mit jedem Schritt exponentiell zu (wie beim Handlungsreisenden).
Anderes Verfahren (Monte Carlo): Man nimmt ein paar (oder viele, je nach Belohnung) Punkte, berechnet den Summenwert und nimmt den niedrigsten.
Ich würde die Adressen geokoordieren (sprich die geographische Koordinaten bestimmen),
dann aus dem Koordinaten einen Mittel"punkt" = Zielpunkt bilden.
Zu diesem Zielpunkt alle Teilnehmer routen. Wenn es signifikante Ungleichgewichte gibt (von Norden kann man auf einer
Autobahn heranrauschen, von Süden muss man sich durch ein Straßengewirr kämpfen), dann den Zielpunkt entsprechend verschieben.
Wahrscheinlich kommt es aber auch eine verkehrsgünstige Lage des Zielpunktes an.
Da Yan, Zhou Zhao and Wilfred Ng: Efficient Algorithms for Finding Optimal Meeting Point on Road Networks. Proceedings of the VLDB Endowment,Vol. 4, No. 11. 2011. http://www.vldb.org/pvldb/vol4/p968-yan.pdf
Profil suchen für einen Router deiner Wahl (brouter beispielsweise), das deinen Routinganforderungen entspricht (LKW-Routing, Durchfahrtshöhen?) oder eins nehmen und anpassen
OSM-Daten nach PostGIS importieren
Algorithmus für den OMP implementieren, dabei für die Distanzberechnung nicht die euklidische Distanz/Dijkstra nehmen, sondern den Router mit deinem Profil ansprechen (als lokal aufgesetzten Server? Du willst und darfst vermutlich nicht die öffentliche BRouter-Instanz mit Millionen von Abfragen DoSsen ).
Hinterher Paper schreiben und auf der FOSSGIS veröffentlichen, incl. Vortrag
Zeitrahmen: je nachdem wie gut du programmieren kannst und wieviel Zeit du da reinstecken kannst: > 8 Wochen.
Hier ist die Maßzahl die Summe aller Kosten zu den Endpunkten. Das ist eine der Möglichkeiten (s.o.) und u.U. nicht das was der Thread-Ersteller im Sinne hatte.
Da airjump sich hier aber nicht mehr geäußert hat, hatte er sich das möglicherweise etwas einfacher vorgestellt und dürfte vielleicht auch von der Implementierung des Algorithmus von Yan et al etwas überfordert sein.
Trotzdem: Es ist als Nebeneffekt immer wieder interessant, auf was für Probleme man in diesem Projekt stößt, auch wenn die Zahl der Lösungen deutlich kleiner als die der Probleme ist.
Das ist mMn müßig, solange airjump sich nicht äußert.
Das kam mir auch in den Sinn, denn Routing in Computernetzen und Routing auf Straßennetzen haben in bestimmten Konstellationen (kleinere Gebiete) viele Ähnlichkeiten.
Gefordert war “fast alle haben die gleiche Anfahrt”.
Das Paper löst das für “Summe aller Wege ist minimal”.
Eine sinnvolle Optimierung, die dem Threadersteller noch nahe kommt, wäre “Das Maximum der Weglängen ist minimal”.
Dann kann es zwar immernoch einige geben, die nur eine ganz kurze Strecke haben, aber es gibt dann auch niemanden, der eine ewig lange Strecke hat.
Würde ein Teilnehmer in Kasachstan wohnen und alle anderen in NRW, wäre “Summe aller Wege ist minimal” irgendwo der Treffpunkt in NRW. Einer muss dann ewig weit fahren, der Rest nur recht kurze Strecken. Bei “Das Maximum der Weglängen ist minimal” wäre der Treffpunkt vielleicht in Moskau. Die Gesamtlänge ist dann ewig lang, weil jeder nach Moskau muss. Aber der eine muss eben auch nicht ganz bis NRW.
).