LoginSignup
3
3

More than 1 year has passed since last update.

@opt_d(D D)

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

Last updated at Posted at 2022-11-23
  • 東京都、大阪府、名古屋県、福岡県、広島県、香川県の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を用いた探索

3
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
3