Algorithmen zur optimalen Lokalisierung von Punkten

Ich versuche, Standorte, an denen tatsächlich mehrere tausend Einrichtungen gebaut wurden, mit Orten zu vergleichen, an denen sie optimal positioniert sind, um die Reisezeiten der Bevölkerung zu minimieren (dargestellt durch Zensusblock- oder Traktschwerpunkte). Ich habe Probleme, alles zu finden, um Punkte optimal zu lokalisieren.

Ich habe eine Vorstellung davon, wie ich diese Orte auswählen soll, aber die schiere Anzahl der Punkte, die im Raum platziert werden müssen, bedeutet, dass jeder nicht geschickt optimierte Algorithmus eine lange Zeit, möglicherweise Jahre, dauern wird. Daher meine Frage: Gibt es Standardalgorithmen für die Auswahl, wo eine feste Anzahl von Punkten lokalisiert werden soll ?

Ich werde letztendlich jeden Algorithmus, den ich finde, als Ausgangspunkt nehmen und ihn anpassen, um mehr Informationen zu integrieren, als nur die Bevölkerungszahl zählt. Daher würde die bevorzugte Antwort eine detaillierte Beschreibung des Algorithmus oder Codes enthalten oder in einer Open-Source-Sprache geschrieben sein, damit ich ihn replizieren und erweitern kann. Wenn ArcGIS jedoch eine praktische Funktion für diese Optimierung hat, würde ich gerne damit beginnen.

point algorithm optimization Ari B. Friedman
quelle

Es wäre hilfreich, eine klarere - vorzugsweise quantitative - Beschreibung dessen zu haben, was "optimal" bedeutet. Interessieren Sie sich beispielsweise für die durchschnittliche Hin- und Rückfahrt zur nächstgelegenen Einrichtung oder für ein anderes Maß an Nähe? Möchten Sie unabhängig von Ihrem Maß für die Reisekosten die Kosten der vorhandenen Konfiguration mit den besten Kosten vergleichen, die durch den Umzug einer vorhandenen Einrichtung erzielt werden könnten, oder möchten Sie auch zulassen, dass Einrichtungen insgesamt entfernt werden? Das Entfernen einer Einrichtung erhöht zwar die durchschnittliche Reisezeit, senkt jedoch die Kosten für den Bau und die Wartung der Einrichtungen.

whuber

@whuber Im Moment bin ich nur daran interessiert, eine vernünftige Funktion der Entfernung zu minimieren (entweder in Luftlinie oder auf dem Quadrat davon). Das eventuelle Optimierungsproblem umfasst die von Ihnen identifizierten Faktoren und mehr (Kosten für den Umzug einer Einrichtung usw.). Aber im Moment wollte ich nur eine Standardmethode für die Auswahl von Standorten, um die Entfernung zu minimieren, sowohl weil dies ein Ausgangspunkt für die Hinwendung zum ultimativen Algorithmus ist, als auch weil ich am Zaun bin, dieses Projekt fortzusetzen und die gröbere Schätzung untersuchen möchte bevor Sie es verfeinern.

Ari B. Friedman

Antworten:

Vielleicht möchten Sie den K-Means-Clustering-Algorithmus ausprobieren .

Beim Data Mining ist k-means Clustering eine Methode der Clusteranalyse, die darauf abzielt, n Beobachtungen in k Cluster zu unterteilen, in denen jede Beobachtung zum Cluster mit dem nächsten Mittelwert gehört. Dies führt zu einer Aufteilung des Datenraums in Voronoi-Zellen.

Hier ist eine andere Definition :

k-means Clustering ist eine Methode zum Klassifizieren / Gruppieren von Elementen in k Gruppen (wobei k die Anzahl der vorgewählten Gruppen ist). Die Gruppierung erfolgt durch Minimieren der Summe der quadratischen Abstände (euklidischen Abstände) zwischen Elementen und dem entsprechenden Schwerpunkt.

Ein Schwerpunkt ist "der Schwerpunkt eines geometrischen Objekts mit gleichmäßiger Dichte", obwohl wir hier mittlere Vektoren als Schwerpunkte betrachten.

Geben Sie hier die Bildbeschreibung ein

Abbildung 1. Ein Cluster-Streudiagramm. Die schwarzen Punkte sind Datenpunkte. Die roten Linien veranschaulichen die Partitionen, die mit dem k-means-Algorithmus erstellt wurden. Die blauen Punkte repräsentieren die Schwerpunkte, die die Partitionen definieren

In Ihrer Situation wäre der Zensusblock oder die Spurschwerpunkte die Eingabe und die Anzahl der Punkte N die Anzahl der Cluster. Hier ist ein Tutorial , um Ihnen den Einstieg zu erleichtern.

RK
quelle

Interessant. Ich hatte nie an K-Mittel dafür gedacht, aber ich denke, die Zentroide haben eher die Eigenschaft, die ich will.

Ari B. Friedman

Vielleicht möchten Sie es testen und sehen, wie es funktioniert :)

Es scheint eine gute Leistung bei Beispieldaten zu erzielen, aber der Implementierung von R fehlt die Fähigkeit zur Gewichtung (in diesem Fall nach Grundgesamtheit). Möglicherweise muss ich die Funktion neu schreiben, um eine Gewichtung zu ermöglichen. Da geht mein Wochenende ;-)

Ari B. Friedman

Seien Sie vorsichtig: k-means lokalisiert Punkte für die meisten Reiseprobleme nicht optimal. Es ist optimal, wenn die Kosten einer Reise proportional zum Quadrat ihrer Entfernung sind. Die Lösung für typische Kosten, die in einem linearen Verhältnis zur Entfernung stehen, ist äußerst schwierig zu erhalten.

whuber

@whuber In der Tat. Dies wird in einer kurzen Darstellung mit detailliertem Code (Fortran und C ++) hier deutlich . Die Reisekosten beziehen sich auf die Notfallversorgung, sodass überlineare Reisekosten nicht völlig unangemessen sind, obwohl es unwahrscheinlich ist, dass der Platz genau richtig ist.

Ari B. Friedman

Ich habe 1996 einen Artikel über dieses Problem mitgeschrieben

Modellierung und Optimierung von Strömungen unter Verwendung paralleler räumlicher Interaktionsmodelle (1996), Turton & Openshaw, VERFAHREN VON EURO-PAR'96, BAND II.

Sie können eine Kopie von Citeseer herunterladen

Wir haben auch geschrieben

Turton I., Openshaw S. (1997) Parallele räumliche Interaktionsmodelle. Geographische und Umweltmodellierung, Band 1, Nummer 2, Seiten 179-197.

Ich kann jedoch keine Online-Kopie finden.

Ian Turton
quelle