Programming Serendipity

気まぐれに大まかに生きるブログ

埼玉県の市町村をすべて回る場合の最短経路

Python

ふと気になったので調査してみた

緯度経度データ集め

GSI HOME PAGE - 国土地理院

とりあえず共通して使えそうな市町村の座標情報と言えば役所の住所なので、↑の国土地理院の情報から緯度経度を抜き出す

これを十進データに直すには、度 + (分 / 60) + (秒 / 3600) でよいらしい。実際にやってみると、敷地内のまんまんなかというわけにはいかないものの、別の土地を指したりはしてないようなのでこれでよし。

とりあえずプロット

有効桁数を稼ぐために緯度を-35、経度を-139して、pythonとmatplotlibでプロットしてみる

import matplotlib.pyplot as plt

poslist=[
    [0.648888888889,0.8569444444444],
# 以下データ省略
]

# plot
plt.plot(
    [p[0] for p in poslist], 
    [p[1] for p in poslist], 
    'ro')
plt.show()

見た感じ、左下がぽっかり空いてるが、これは秩父と飯能がそれぞれ役所の位置が偏ってるのでこれで合ってるみたい。上辺のほうも、一筆書きできそう。（ちなみに埼玉県にした理由も、なんとなく全体的にばらけてて数が多く、領域全体が丸っぽくてデコボコが少ないというのもある）

自治体コード順をそのままルートにするとこんな感じ

焼きなまし法(simulated annealing)によるヒューリスティクスの計算

埼玉県は、さいたま市の区役所と県庁も含めて74カ所の役所があるので、すべての地点からすべての地点への移動の組み合わせの最短経路を厳密に求めようとすると、 $74! \fallingdotseq 3.3 \times10^{107}$ 回の計算が必要になってしまい、演算が現実的でない。

そこで、厳密でなくともある程度の精度の結果を出す方法がいくつか開発されているが、焼きなまし法がなんだかよさそうなので試してみた。

…といいたいところだったが、python-tspというそのものズバリなライブラリを見つけてしまったので、自前で実装する気力がうせてしまった。

import matplotlib.pyplot as plt
import math
import numpy as np
from python_tsp.distances import great_circle_distance_matrix
from python_tsp.heuristics import solve_tsp_simulated_annealing

sources = np.array([
    [0.648888888889,0.8569444444444],
# データ省略
])

distance_matrix = great_circle_distance_matrix(sources)
permutation, distance = solve_tsp_simulated_annealing(distance_matrix)

print(permutation)

なんというスクリプトキディ…いいんです、結果が得られれば。ソースコードを読んで勉強するので許してください。

ということで得られた結果がこちら。

地図にプロットするとこんな感じ。

いつかこのコースで旅してみたい。

ファイルから受け取る

これだけだとさすがに怠惰すぎるので、もう少し工夫してtab separated valueから読み取れるように改修してみた

# tvp_sa.py
import sys
import matplotlib.pyplot as plt
import math
import numpy as np
from python_tsp.distances import great_circle_distance_matrix
from python_tsp.heuristics import solve_tsp_simulated_annealing

args = sys.argv
if len(args) <= 1:
    print("usage: tvp_sa.py filename")
    quit()

sources = np.arange(0).reshape(0, 2)
result = np.arange(0).reshape(0, 2)
names = []

# read
with open(args[1], mode="r", encoding="utf-8") as fp:
    lines = fp.readlines()
    for line in lines:
        name, x, y = line.split('\t')
        names.append(name)
        sources = np.append(sources, np.array([[float(x), float(y)]]), axis=0)

# calc
distance_matrix = great_circle_distance_matrix(sources)
permutation, distance = solve_tsp_simulated_annealing(distance_matrix)

# arrange result
for x in range(len(permutation)):
    result = np.append(result, np.array([sources[permutation[x]]]), axis=0)

# plot
plt.plot(
    [p[0] for p in result], 
    [p[1] for p in result], 
    color="red",
    marker='o',
    linestyle="solid",
    linewidth=1,
    markersize=4)
plt.title('SA Order length:' + str(distance))
plt.show()
# print(result)

# write
with open("result.txt", mode="w", encoding="utf-8") as fp:
    for x in range(len(permutation)):
        print(names[permutation[x]])
        fp.write(names[permutation[x]] + "\n")

入力

弘前市    140.464166666667    40.6030555555556
八戸市   141.488333333333    40.5122222222222
...

2次元配列まわりにてこずった。というかpythonの情報をググろうとするとゴミサイトが大量に出てきて非常に検索しにくい。いつの間にこんな状態になってたのか・・・