[PYTHON] Pokemon manholes will be set up at 15 locations in Hokkaido, so I calculated the optimal route.
Introduction
Around the end of November, it was reported on the official website and various news sites that a Pokemon manhole will be set up in Hokkaido.
Fifteen places are evenly scattered all over the road, and it seems to be quite difficult to complete. My hometown is also a target for installation, as a Pokemon lover, as a person who goes to the geo road, and because I found a good story of the Advent calendar, I calculated the optimum route to go around all 15 places in Hokkaido Want to try! I thought </ b>.
Use "Poke lid" as location information data
Get location information
You can get map information and coordinates on the official website.
Plot 15 locations on QGIS
Tick with the mouse ...
I did it.
Output coordinates to CSV file
In the field calculator, add the coordinates (longitude / latitude) to the attribute. You can get longitude (lon) with $ x and latitude (lat) with $ y.
And export as CSV.
['Shibetsu City', '44.1759660664951', '142.392400060057']
['Pippu Town', '43.8750601338394', '142.471656275175']
['Ashoro Town', '43.2442234401681', '143.546750238874']
['Ishikari City', '43.5859009826181', '141.423896468599']
['Eniwa City', '42.8971470864568', '141.585830729499']
['Toyako Town', '42.5661295066754', '140.819057243298']
['Morimachi', '42.1088651156221', '140.572905228496']
['Kaminokuni Town', '41.8084126507218', '140.095325019279']
['Teshio Town', '44.8845377760538', '141.747994037888']
['Wakkanai City', '45.4170905393652', '141.676181866153']
['Toyotomi Town', '45.1033949651183', '141.778599640962']
['Monbetsu City', '44.334669948041', '143.37218366193']
['Engaru Town', '44.0218720548609', '143.497163771181']
['Ozora Town', '43.9155408070508', '144.171387033476']
['Shintoku Town', '43.0826784443182', '142.832912172283']
Optimal route calculation
Calculation method
Now that the data preparation is complete, it's time to start. However, I don't know how to calculate the optimal route at all, so I tried Google for the time being. This optimization of the traveling route at many points is commonly referred to as the traveling salesman problem.
(The answer is on ... the best ...)
That's why I referred to this article. Combinatorial optimization-Typical problem-Traveling salesman problem-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))
The contents of pokefuta_coordinates.csv are the same as the previous csv file. Using the longitude / latitude array as nodes, create a matrix dist with the number of elements x the number of elements for each distance, and pass it to tsp (traveling salesman problem) to output the result.
(12.651143975005297, [0, 10, 9, 8, 3, 5, 7, 6, 4, 14, 2, 13, 12, 11, 1])
The first value is the travel cost. The second array of return values shows the route to take to minimize travel costs. The first node ([0]) is always set as the start point and goal point. In the csv file I mentioned earlier, Shibetsu City is the starting point. The figure below shows this route.
The code itself doesn't seem to be a problem, it looks like the shortest path. All the residents travel by private helicopter, so there is no problem with the sea route. Well, even if you are traveling by car, it is efficient to go around Mori-cho and Kaminokuni-cho at the same time, so it will not affect this analysis (although the distance divergence seems to be large, it will affect the order of patrols. Make it not exist). This is the route from Shibetsu City, but please see some patterns according to your travel plan (the total travel distance shown is an estimate based on the total straight line distance).
Route from Asahikawa Airport
Total travel distance: 1267km
From our Asahikawa Airport, which is located in Higashikagura Town, which is next to the city, not in Asahikawa City, which is the second largest city in Hokkaido, and boasts an amazing 99.7% service rate due to its robustness despite bad weather, try visiting 15 manholes in Hokkaido. Isn't it?
Route from New Chitose Airport
Total distance traveled: 1237km
Although it is the gateway to Hokkaido as a hub airport, you can enjoy manholes with a 1200km drive from our New Chitose Airport, which can be enjoyed by various tenants without boarding an airplane!
Route from Shinkansen Hokuto Station
Total distance traveled: 1239km
It's finally here. It's about 4 hours from Tokyo on the Shinkansen, so why don't you come and visit the manholes?
At the end
Although I showed multiple plans, it is natural that the route became circular after all, but there was almost no difference except for the order. I started this article with an idea, but I was able to write it earlier than I expected (a total of about 4 hours). I've been doing various display and processing of location information data for my work and hobbies, but I haven't had much experience with analysis like this optimization, and in fact, this code is also a calculation method only with the help of a convenient library. Etc. remain completely unknown. There are many things I don't understand, but I hope that those who read this article will enjoy it for the time being.
Reference site
Combinatorial optimization-Typical problem-Traveling salesman problem-Qiita
Reading csv file with python --Qiita
Convert lines to points with QGIS and retrieve xy coordinates-Qiita