[PYTHON] Les salles des hommes Pokémon seront installées à 15 endroits à Hokkaido, j'ai donc calculé l'itinéraire optimal

Utilisez "Poke lid" comme données de localisation

Obtenir des informations de localisation

Vous pouvez obtenir des informations cartographiques et des coordonnées sur le site officiel.

Tracer 15 emplacements sur QGIS

Cochez avec la souris ...

Je l'ai fait.

Coordonnées de sortie dans un fichier CSV

Dans l'ordinateur de terrain, ajoutez des coordonnées (longitudinales / latitude) aux attributs. Vous pouvez obtenir la longitude (lon) avec $ x et la latitude (lat) avec $ y.

Et exportez au format CSV.

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

Calcul d'itinéraire optimal

Méthode de calcul

Maintenant que les données ont été préparées, il est temps de commencer. Cependant, je ne sais pas du tout comment calculer l'itinéraire optimal, alors j'ai essayé Google pour le moment. L'optimisation de l'itinéraire de patrouille en de nombreux points de cette manière est communément appelée le problème des patrouilleurs.

(La réponse est sur ... le meilleur ...)

C'est pourquoi j'ai fait référence à cet article. Optimisation de combinaison - Problème typique - Problème de vendeur de circuits - 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))

Le contenu de pokefuta_coordinates.csv est le même que celui du fichier csv précédent. Le résultat est généré lorsque le tableau de longitude et de latitude est utilisé comme nœuds et que chaque distance est créée comme une matrice dist du nombre d'éléments x le nombre d'éléments et transmise à tsp (problème du voyageur de commerce).

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

La première valeur est le coût du voyage. Le deuxième tableau de valeurs de retour indique le chemin à suivre pour minimiser les frais de déplacement. Le premier nœud ([0]) est toujours défini comme point de départ et point de but. Dans le fichier csv que j'ai mentionné précédemment, Shibetsu City est le point de départ. La figure ci-dessous montre cet itinéraire.

Le code lui-même ne semble pas être un problème, il ressemble à l'itinéraire le plus court. Tous les résidents voyagent en hélicoptère privé, il n'y a donc pas de problème avec la route maritime. Même s'il s'agit d'un déplacement en voiture, il est efficace de faire le tour de Morimachi et d'Uenokunicho en même temps, donc cela n'affectera pas cette analyse (bien que la différence de distance semble importante, elle affectera l'ordre des patrouilles. Faites qu'il n'existe pas). Il s'agit de l'itinéraire depuis la ville de Shibetsu, mais veuillez consulter certains modèles en fonction de votre plan de voyage (la distance totale du trajet indiquée est une estimation basée sur la distance totale en ligne droite).

Route depuis l'aéroport d'Asahikawa

Distance totale parcourue: 1267 km

Depuis notre aéroport d'Asahikawa, situé dans la ville voisine de Higashi Kagura, et non dans la ville d'Asahikawa, qui est la deuxième plus grande ville d'Hokkaido, et qui bénéficie d'un taux de service incroyable de 99,7% en raison de sa robustesse malgré le mauvais temps, essayez de visiter 15 trous d'homme à Hokkaido. N'est-ce pas?

Itinéraire depuis le nouvel aéroport de Chitose

Distance totale parcourue: 1237 km

Bien qu'il soit la porte d'entrée vers Hokkaido en tant que hub aéroportuaire, vous pouvez en profiter avec différents locataires sans avoir à monter à bord d'un avion.Depuis notre nouvel aéroport de Chitose, vous pouvez parcourir 1200 km pour conquérir le regard!

Itinéraire depuis la gare de Shinkansen Hokuto

Distance totale parcourue: 1239 km

Il semble que nous arriverons enfin de Tokyo sur le Shinkansen dans environ 4 heures, alors pourquoi ne venez-vous pas visiter les regards?

À la fin

Bien que j'aie montré plusieurs plans, il est naturel que l'itinéraire soit devenu circulaire après tout, mais il n'y avait presque aucune différence à part l'ordre. J'ai commencé cet article avec une idée, mais j'ai pu l'écrire plus tôt que prévu (un total d'environ 4 heures). J'ai effectué divers affichages et traitements de données d'informations de position pour mon travail et mes loisirs, mais je n'ai pas eu beaucoup d'expérience avec des analyses telles que cette optimisation, et en fait, ce code est également une méthode de calcul uniquement à l'aide d'une bibliothèque pratique. Etc. restent totalement inconnus. Il y a beaucoup de choses que je ne comprends pas, mais j'espère que ceux qui liront cet article l'apprécieront pour le moment.

Site de référence

Optimisation de combinaison - Problème typique - Problème de vendeur de circuits - Qiita

Lecture de fichiers csv avec python-Qiita

Convertissez les lignes en points avec QGIS et extrayez les coordonnées xy --Qiita