第4回: Google Maps Platform, Directions APIによる地点間情報取得(巡回セールスマン問題への下準備)

• 東京都、大阪府、名古屋県、福岡県、広島県、香川県の6都市間の距離、移動時間をGoogle MapsからDiretions APIを用いて取得する。
• また、各都市の座標はgeocoderを用いて取得する。
• これは、アニーリングを用いた巡回セールスマン問題を解くための下準備。

前回：第3回: アニーリング基礎3. クラスタリング問題、2次元スピンの1次元化
参考：Pythonで地名から住所と座標を割り出すジオコーディングを試してみる, 公式チュートリアル,Qiita: Google Map API で経路情報を取得する
Keyword：Google Maps Platform, Directions API

1. geocoderによる座標の取得

尚、geocoderの使い方は、Pythonで地名から住所と座標を割り出すジオコーディングを試してみるを参考にした。

1.1 geocoderのインストール

pip install geocoder

1.2 座標の取得

始めに、場所を指定すれば、緯度、経度を返す関数を作成する。

import geocoder
def _latlng(_location):
  _ans = geocoder.osm(_location, timeout=1.0)
  ### geocoderから情報を取得できたか確認
  if _ans.ok == True:
    ### 取得した結果を辞書に変換
    _ans = _ans.json
    ### 後でgoogle map apiに渡すことを考え、[,]を[%2C]に置き換えて、緯度経度を並べる。
    _latlng = str(_ans["lat"]) +"%2C"+str(_ans["lng"])
  else:
    _latlng = "error"
    print("Error: ロケーションが見つかりません。")
  return _latlng

続いて、指定の都市の座標を取得する。

### 取得したい座標の都市をリスト化
target_city = ["東京都","大阪府","名古屋県","福岡県","広島県","香川県"]
_N = len(target_city)

### 定義した緯度経度取得するlatlng関数で緯度経度に変換する
_target_latlng = [_latlng(_tar) for _tar in target_city]
_target_latlng

<Output>
['35.6828387%2C139.7594549',
 '34.6198813%2C135.490357',
 '35.1706972%2C136.8816286',
 '33.6251241%2C130.6180016',
 '34.5666725%2C132.753565',
 '34.2480104%2C134.0586579']

2. Google / Directions APIによる地点間情報取得

尚、apiの使い方は、公式チュートリアル、およびQiita: Google Map API で経路情報を取得するを参考にした。

2.1 移動距離と移動時間取得する関数の定義

###ライブラリのインポート
import requests

###APIコード
google_api_key = "AIzaSyCXLky3XXXXXXXXXXXXXXXXXX" #APIキーは各自取得願います。

###移動距離と移動時間を取得する関数の定義
def _google_direction(_origin,_destination,_mode="driving"):
  ###APIリクエストの作成
  _mode = "driving"
  _url = f"https://maps.googleapis.com/maps/api/directions/json?destination={_destination}&origin={_origin}&mode={_mode}&key={google_api_key}"

  ###APIデータの取得
  _response = requests.get(_url).json()

  ###移動距離、移動時間の取得
  #Jsonファイルからルート情報の取得
  _route = _response["routes"][0]["legs"][0]
  #移動距離の抽出
  _distance = int(_route["distance"]["value"])/1000
  #移動時間の抽出
  _duration = int(_route["duration"]["value"])/60
  return[_distance,_duration]

2.2 地点間に移動距離と移動時間の取得

都市間の移動距離、移動時間を$6×6$の行列で表現する。同じ都市は移動できない為、対角成分は0となる。また、上下三角行列は略同じ数値となる。計算結果確認の為、とりあえず、対角成分を除くすべての成分の計算を行う。

###ライブラリのインポート
import numpy as np

###出力用の行列を準備
_distance_inf = np.zeros(_N**2).reshape(_N,_N)
_duration_inf = np.zeros(_N**2).reshape(_N,_N)

###組み合わせ事に移動距離、移動時間を取得する
for _x in range(_N):
  for _y in range(_N):
    if not _x == _y:
      _result = _google_direction(_target_latlng[_x],_target_latlng[_y],"driving")
      #print(f"{_x}:{target_city[_x]}-{_y}:{target_city[_y]}:{_result}")
      _distance_inf[_x][_y] = round(_result[0],0)
      _duration_inf[_x][_y] = round(_result[1],0)

###テスト
_distance_inf
_durantion_inf

<Output>
array([[   0.,  505.,  347., 1073.,  779.,  685.],
       [ 504.,    0.,  176.,  604.,  310.,  200.],
       [ 348.,  176.,    0.,  744.,  450.,  356.],
       [1073.,  607.,  744.,    0.,  319.,  475.],
       [ 778.,  312.,  450.,  315.,    0.,  181.],
       [ 684.,  198.,  356.,  475.,  181.,    0.]])

array([[  0., 368., 258., 781., 580., 496.],
       [366.,   0., 146., 457., 255., 159.],
       [256., 146.,   0., 559., 358., 274.],
       [780., 461., 560.,   0., 268., 370.],
       [576., 256., 356., 264.,   0., 165.],
       [494., 162., 274., 368., 167.,   0.]])

結果を見ると。上下三角行列に於いて、若干の誤差が出ているが、往路、復路で若干の距離の違い、所要時間の違いは発生するものと考えられる。最後に、地点リストを入力すれば、距離一覧と所要時間一覧を返す一連の関数にまとめる。

3. 関数化

###ライブラリのインポート
import geocoder
import requests
import numpy as np

###Google API Keyの設定
google_api_key = "AIzaSyCXLky3XXXXXXXXXXXXXXXXXX" #APIキーは各自取得願います。

target_city = ["東京都","大阪府","名古屋県","福岡県","広島県","香川県"]

#===座標取得関数
def _latlng(_location):
  _ans = geocoder.osm(_location, timeout=1.0)
  ### geocoderから情報を取得できたか確認
  if _ans.ok == True:
    ### 取得した結果を辞書に変換
    _ans = _ans.json
    ### 後でgoogle mapに代入しやすくするために、検索用のフォーマットに変換する。
    _latlng = str(_ans["lat"]) +"%2C"+str(_ans["lng"])
  else:
    _latlng = "error"
    print("Error: ロケーションが見つかりません。")
  return _latlng

#==移動距離と移動時間を取得する関数
def _google_direction(_origin,_destination,_mode="driving"):
  ###APIリクエストの作成
  _mode = "driving"
  _url = f"https://maps.googleapis.com/maps/api/directions/json?destination={_destination}&origin={_origin}&mode={_mode}&key={google_api_key}"

  ###APIデータの取得
  _response = requests.get(_url).json()

  ###移動距離、移動時間の取得
  #Jsonファイルからルート情報の取得
  _route = _response["routes"][0]["legs"][0]
  #移動距離の抽出
  _distance = int(_route["distance"]["value"])/1000
  #移動時間の抽出
  _duration = int(_route["duration"]["value"])/60
  return[_distance,_duration]

def get_dist_time(*target_city):
  ###対象とする都市数の取得
  _N = len(target_city)

  ###出力用の行列を準備
  _distance_inf = np.zeros(_N**2).reshape(_N,_N)
  _duration_inf = np.zeros(_N**2).reshape(_N,_N)

  ### 定義した緯度経度取得するlatlng関数で緯度経度に変換する
  _target_latlng = [_latlng(_tar) for _tar in target_city]
  _target_latlng

  ###組み合わせ事に移動距離、移動時間を取得する
  for _x in range(_N):
    for _y in range(_N):
      if not _x == _y:
        _result = _google_direction(_target_latlng[_x],_target_latlng[_y],"driving")
        #print(f"{_x}:{target_city[_x]}-{_y}:{target_city[_y]}:{_result}")
        _distance_inf[_x][_y] = round(_result[0],0)
        _duration_inf[_x][_y] = round(_result[1],0)
  _result =[_distance_inf,_duration_inf]
  
  ###出力
  return _result

###テスト
get_dist_time(*["大阪","東京","北海道"])

[array([[   0.,  501., 1633.],
        [ 501.,    0., 1313.],
        [1811., 1300.,    0.]]),
array([[   0.,  363., 1462.],
        [ 362.,    0., 1122.],
        [1473., 1121.,    0.]])]

おわりに

都市間の移動距離と移動時間を抽出する関数が整備できたので、続いて本番の巡回セールスマン問題を解いてみる。

今後の課題 : 巡回セールスマン問題
積み残し: 補助スピン$y_{i}$の活用, TTSを用いた探索