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.

スクリーンショット 2019-12-02 21.11.10.png

Pokemon Manhole "Poke Lid"

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.

スクリーンショット 2019-12-02 21.18.01.png

Plot 15 locations on QGIS

Tick with the mouse ...

スクリーンショット 2019-12-02 21.20.01.png

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.

スクリーンショット 2019-12-02 21.24.29.png

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.

スクリーンショット 2019-12-02 21.29.03.png

スクリーンショット 2019-12-02 21.31.18.png (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.

スクリーンショット 2019-12-02 22.23.25.png

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

スクリーンショット 2019-12-02 22.57.22.png

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

スクリーンショット 2019-12-02 22.56.15.png

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

スクリーンショット 2019-12-02 22.54.53.png

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

Recommended Posts

Pokemon manholes will be set up at 15 locations in Hokkaido, so I calculated the optimal route.
I tried to predict the horses that will be in the top 3 with LightGBM
I bought Sipeed Lichee Zero so I set it up for the time being