[PYTHON] Pokemon Man Hallen werden an 15 Orten in Hokkaido eingerichtet, also habe ich die optimale Route berechnet

Verwenden Sie "Poke Deckel" als Standortinformationsdaten

Standortinformationen abrufen

Karteninformationen und Koordinaten erhalten Sie auf der offiziellen Website.

Zeichnen Sie 15 Standorte in QGIS

Mit der Maus ankreuzen ...

Ich habs gemacht.

Ausgabekoordinaten in CSV-Datei

Fügen Sie im Feldcomputer den Attributen Koordinaten (Längs- / Breitengrad) hinzu. Sie können den Längengrad (lon) mit $ x und den Breitengrad (lat) mit $ y erhalten.

Und als CSV exportieren.

['Shibetsu Stadt', '44.1759660664951', '142.392400060057']
['Hifucho', '43.8750601338394', '142.471656275175']
['Ashikaga Stadt', '43.2442234401681', '143.546750238874']
['Ishikari Stadt', '43.5859009826181', '141.423896468599']
['Eba City', '42.8971470864568', '141.585830729499']
['See Toya', '42.5661295066754', '140.819057243298']
['Morimachi', '42.1088651156221', '140.572905228496']
['Ueno Kunimachi', '41.8084126507218', '140.095325019279']
['Tenshio Stadt', '44.8845377760538', '141.747994037888']
['Wakauchi Stadt', '45.4170905393652', '141.676181866153']
['Reiche Stadt', '45.1033949651183', '141.778599640962']
['Monbetsu Stadt', '44.334669948041', '143.37218366193']
['Engaru Stadt', '44.0218720548609', '143.497163771181']
['Ozora Stadt', '43.9155408070508', '144.171387033476']
['Shintokucho', '43.0826784443182', '142.832912172283']

Optimale Routenberechnung

Rechenmethode

Nachdem die Daten vorbereitet wurden, ist es Zeit zu beginnen. Ich weiß jedoch überhaupt nicht, wie ich die optimale Route berechnen soll, deshalb habe ich vorerst Google ausprobiert. Diese Optimierung der Patrouillenrouten an vielen Stellen wird allgemein als Patrouillenverkäuferproblem bezeichnet.

(Die Antwort ist auf ... das Beste ...)

Deshalb habe ich auf diesen Artikel verwiesen. Kombinationsoptimierung - Typisches Problem - Problem mit Schaltkreisverkäufern - Qiita

Code

https://github.com/Kanahiro/-pokefuta_analyzer

import csv
import numpy as np
from scipy.spatial import distance
from ortoolpy import tsp

asahikawa_airport = [142.4541427, 43.6708414]
shinchitose_airport = [141.6811815, 42.7876057]
shinkansen_hokuto = [140.6486832, 41.9046279]

start_point = shinkansen_hokuto
nodes = [start_point]

with open('./pokefuta_coordinates.csv') as f:
    reader = csv.reader(f)
    header = next(f)
    for row in reader:
        nodes.append([ row[2], row[1] ])

dist = distance.cdist(nodes, nodes)
print(tsp(nodes, dist))

Der Inhalt von pokefuta_coordinates.csv entspricht dem der vorherigen CSV-Datei. Das Ergebnis wird ausgegeben, wenn das Array aus Längen- und Breitengrad als Knoten verwendet wird und jede Entfernung als Matrix dist aus der Anzahl der Elemente x der Anzahl der Elemente erstellt und an tsp übergeben wird (Problem des Handlungsreisenden).

(12.651143975005297, [0, 10, 9, 8, 3, 5, 7, 6, 4, 14, 2, 13, 12, 11, 1])

Der erste Wert sind die Reisekosten. Das zweite Array von Rückgabewerten zeigt den Weg, den Sie einschlagen sollten, um die Reisekosten zu minimieren. Der erste Knoten ([0]) wird immer als Start- und Zielpunkt festgelegt. In der zuvor erwähnten CSV-Datei ist Shibetsu City der Ausgangspunkt. Die folgende Abbildung zeigt diese Route.

Der Code selbst scheint kein Problem zu sein, er scheint der kürzeste Weg zu sein. Alle Bewohner reisen mit einem privaten Hubschrauber, so dass der Seeweg kein Problem darstellt. Nun, selbst wenn Sie mit dem Auto anreisen, ist es effizient, Morimachi und Uenokunicho gleichzeitig zu erkunden, sodass diese Analyse nicht beeinflusst wird (der Entfernungsunterschied scheint groß zu sein, aber die Reihenfolge der Patrouillen wird beeinflusst. Mach es nicht existent). Dies ist die Route von Shibetsu City, aber bitte sehen Sie sich einige Muster gemäß Ihrem Reiseplan an (die angezeigte Gesamtreiseentfernung ist eine Schätzung basierend auf der gesamten geraden Entfernung).

Route vom Flughafen Asahikawa

Gesamtfahrstrecke: 1267 km

Von unserem Flughafen Asahikawa, der sich in der benachbarten Stadt Higashi Kagura befindet, nicht in der Stadt Asahikawa, der zweitgrößten Stadt in Hokkaido, die aufgrund ihrer Robustheit trotz schlechten Wetters eine erstaunliche Servicerate von 99,7% aufweist, werden wir 15 Mannlöcher in Hokkaido besuchen. Ist es nicht?

Route vom Flughafen New Chitose

Gesamtfahrstrecke: 1237 km

Obwohl es das Tor zu Hokkaido als Drehkreuzflughafen ist, können Sie es mit verschiedenen Mietern genießen, ohne in ein Flugzeug steigen zu müssen. Von unserem neuen Flughafen Chitose aus können Sie 1200 km fahren, um das Mannloch zu erobern!

Route vom Bahnhof Shinkansen Hokuto

Gesamtfahrstrecke: 1239 km

Es scheint, dass wir in ungefähr 4 Stunden endlich aus Tokio auf dem Shinkansen ankommen werden. Warum kommst du nicht und besuchst die Mannlöcher?

Am Ende

Obwohl ich mehrere Pläne gezeigt habe, ist es natürlich, dass die Route doch kreisförmig wurde, aber es gab fast keinen Unterschied außer der Reihenfolge. Ich habe diesen Artikel mit einer Idee begonnen, konnte ihn aber früher als erwartet schreiben (insgesamt ca. 4 Stunden). Das Anzeigen und Verarbeiten von Standortinformationsdaten wurde je nach meiner Arbeit und meinen Hobbys auf verschiedene Arten durchgeführt, aber ich habe nicht viel Erfahrung mit Analysen wie dieser Optimierung, und tatsächlich ist dieser Code auch eine Berechnungsmethode nur mit Hilfe einer praktischen Bibliothek. Usw. bleiben völlig unbekannt. Es gibt viele Dinge, die ich nicht verstehe, aber ich hoffe, dass diejenigen, die diesen Artikel lesen, ihn vorerst genießen werden.

Referenzseite

Kombinationsoptimierung - Typisches Problem - Problem mit Schaltkreisverkäufern - Qiita

Lesen von CSV-Dateien mit Python-Qiita

Konvertieren Sie Linien mit QGIS in Punkte und extrahieren Sie xy-Koordinaten - Qiita