ドライブ、観光地巡りを効率化！Google Maps PlatformとOR-Toolsを使ったTSP解決方法

前置き

車で観光を楽しむ際、多くの観光スポットを効率よく巡るための最適な順番を計算する手法を試しました。
「Google Maps Platform」のDistance Matrix APIを活用して地点間の距離情報を取得し、そのデータを基にGoogle OR-Toolsを用いて巡回セールスマン問題（TSP）を解きました。

最終的に、多数の観光スポットを効率的に訪れるための最適なルートを計算し、その結果をブラウザ上で視覚的に確認できる形に仕上げました。これにより、ドライブのルート決めが簡単かつ直感的になり、計画の負担を大幅に軽減できました！

---

作成手順

1. GoogleMaps の指定リストを CSV にする[1]

1. GoogleMapsのハンバーガーボタンをクリック

2. 「Googleマップでのデータについて」をクリック
   

3. 「マップデータをダウンロードする」をクリック

4. 「サービスをもっと見る」をクリック

5. 「Saved」にチェックを入れ、「次のステップ」をクリック
   

6. 何も変更せず、「エクスポートする」をクリック

7. 数分後、メールにリンクが登場したらダウンロード
   

2. 取得した CSV からタイトルのみ取得

 $ pip install pandas

extract_titles.py

import pandas as pd

# CSVファイルを読み込み、"タイトル"列をリストで取得
titles = pd.read_csv("最適化テスト用.csv")["タイトル"].dropna().tolist()

# タイトル一覧を表示
print(titles)

出力例

['東京ドイツ村', '原岡桟橋 (岡本桟橋)', '道の駅 富楽里とみやま パーキングエリア', '海ほたるPA']

3. GoogleCloud の設定[2]

1. 新しいプロジェクトを作成
2. プロダクトの「マップの埋め込み」をクリックする
   
3. 「Distance Matrix API」、「Geocoding API」を ENABLE にする
   
4. 「Keys」をクリックし、APIキーを取得

4. 緯度 緯度を取得[3][4]

 $ pip install googlemaps

get_lat_lng.py

import googlemaps

# Google Maps APIキーを設定
googleapikey = 'API keyを設定する'
gmaps = googlemaps.Client(key=googleapikey)

# 入力リスト
places = ['東京ドイツ村', '原岡桟橋 (岡本桟橋)', '道の駅 富楽里とみやま パーキングエリア', '海ほたるPA']

# 出力リストを初期化
lat_lng_list = []

for place in places:
    result = gmaps.geocode(place)
    if result:
        lat = result[0]["geometry"]["location"]["lat"]
        lng = result[0]["geometry"]["location"]["lng"]
        lat_lng_list.append((lat, lng))

print(lat_lng_list)

出力例

[(35.4056432, 140.0539067), (35.044254, 139.8311644), (35.1002396, 139.8560761), (35.4637979, 139.8753237)]

5. 距離行列を取得[5][6]

geo_distance_matrix.py

import googlemaps

# Google Maps APIキーを設定
API_KEY = "API keyを設定する"
gmaps = googlemaps.Client(key=API_KEY)

# 地点リスト
locations = [(35.4056432, 140.0539067), (35.044254, 139.8311644), (35.1002396, 139.8560761), (35.4637979, 139.8753237)]

# Google Maps Distance Matrix API を使用して距離行列を取得
matrix_response = gmaps.distance_matrix(
    origins=locations, 
    destinations=locations, 
    mode="driving"
)

# 距離行列を抽出して配列に整形
distance_matrix = []
for row in matrix_response['rows']:
    distance_row = [element['distance']['value'] for element in row['elements']]
    distance_matrix.append(distance_row)

print(distance_matrix)

出力例

[[0, 61576, 52626, 50606], [59971, 0, 12868, 83121], [66430, 9919, 0, 89580], [26713, 61033, 52082, 1616]]

6. 巡回セールスマン問題を解く[7]

 $ pip install ortools

公式ドキュメントそのままです。

tsp_solver.py

"""Simple Travelling Salesperson Problem (TSP) between cities."""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = [
        [0, 61576, 52626, 50606],
        [59971, 0, 12868, 83121],
        [66430, 9919, 0, 89580],
        [26713, 61033, 52082, 1616]
    ]
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()} miles")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {manager.IndexToNode(index)} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    print(plan_output)
    plan_output += f"Route distance: {route_distance}miles\n"


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)


    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution)


if __name__ == "__main__":
    main()

出力例

Objective: 172379 miles
Route for vehicle 0:
 0 -> 2 -> 1 -> 3 -> 0

6. 少し修正し、1つにまとめる

上記のソースコードを実行したところ、観光スポットが11個以上になると「MAX_ELEMENTS_EXCEEDED」というエラーが発生しました。これは、出発地と目的地の組み合わせ（origins × destinations）が1リクエストあたりの上限である100要素を超えたためです。[8][9]

この制限を回避するため、リクエストを小さなチャンクに分割して送信する方法に修正しました。また、出力結果を数字ではなく観光スポットのタイトルで表示するよう改善しました。

RouteOptimizer.py

import pandas as pd
import googlemaps
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def extract_titles(file_path):
    # CSVファイルを読み込み、"タイトル"列をリストで取得
    return pd.read_csv(file_path)["タイトル"].dropna().tolist()

def get_lat_lng_list(places, gmaps):
    # 緯度と経度を取得
    lat_lng_list = []
    for place in places:
        result = gmaps.geocode(place)
        if result:
            lat = result[0]["geometry"]["location"]["lat"]
            lng = result[0]["geometry"]["location"]["lng"]
            lat_lng_list.append((lat, lng))
    return lat_lng_list

def get_distance_matrix(locations, gmaps, chunk_size=10):
    # 距離行列をチャンクに分けて取得
    n = len(locations)
    distance_matrix = [[0]*n for _ in range(n)]
    
    for i in range(0, n, chunk_size):
        for j in range(0, n, chunk_size):
            origins = locations[i:i+chunk_size]
            destinations = locations[j:j+chunk_size]
            response = gmaps.distance_matrix(
                origins=origins, 
                destinations=destinations, 
                mode="driving"
            )
            for oi, origin_row in enumerate(response['rows']):
                for di, element in enumerate(origin_row['elements']):
                    distance_matrix[i+oi][j+di] = element['distance']['value']
    
    return distance_matrix

def create_data_model(distance_matrix):
    """Stores the data for the problem."""
    data = {}
    data["distance_matrix"] = distance_matrix
    data["num_vehicles"] = 1
    data["depot"] = 0
    return data

def print_solution(manager, routing, solution,titles):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()} miles")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += f" {titles[manager.IndexToNode(index)]} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += f" {manager.IndexToNode(index)}\n"
    print(plan_output)
    plan_output += f"Route distance: {route_distance}miles\n"

def solve_tsp(data,titles):
    """TSPを解く"""
     # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)


    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["distance_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution,titles)

def main(file_path, api_key):
    """エントリーポイント"""
    gmaps = googlemaps.Client(key=api_key)

    # タイトル列を取得
    titles = extract_titles(file_path)

    # 緯度経度を取得
    locations = get_lat_lng_list(titles, gmaps)

    # 距離行列を取得
    distance_matrix = get_distance_matrix(locations, gmaps)
    #print(distance_matrix)
    
    # TSPを解く
    data = create_data_model(distance_matrix)
    solve_tsp(data,titles)

if __name__ == "__main__":
    # 入力パラメータ
    FILE_PATH = "./最適化テスト用.csv"
    API_KEY = "API keyを設定する"  # Google Maps APIキーを設定

    main(FILE_PATH, API_KEY)

出力結果

Objective: 172379 miles
Route for vehicle 0:
 東京ドイツ村 -> 道の駅 富楽里とみやま パーキングエリア -> 原岡桟橋 (岡本桟橋) -> 海ほたるPA -> 0

7. ブラウザで表示したい

以下の関数と既存のソースコードを一部修正しました。

RouteOptimizer.py

def generate_google_maps_url(route, titles):
    origin = titles[route[0]]  # 出発地
    destination = titles[route[-1]]  # 目的地
    waypoints = "|".join(titles[i] for i in route[1:-1])  # 経由地（途中地点）

    # Google MapsのURLを生成
    url = (
        f"https://www.google.com/maps/dir/?api=1"
        f"&origin={origin}"
        f"&destination={destination}"
        f"&waypoints={waypoints}"
        f"&travelmode=driving"
    )

    # URLをブラウザで開く
    print("Generated Google Maps URL:", url)
    webbrowser.open(url)

def print_solution(manager, routing, solution,titles):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()} miles")
    index = routing.Start(0)
    plan_output = "Route for vehicle 0:\n"
+   route =[] #ルート順序を格納
    route_distance = 0
    while not routing.IsEnd(index):
+       route.append(manager.IndexToNode(index))  # ルート順序を収集
        plan_output += f" {titles[manager.IndexToNode(index)]} ->"
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
+   route.append(manager.IndexToNode(index))  # 最後にデポ地点を追加
    plan_output += f" {manager.IndexToNode(index)}\n"
    print(plan_output)
    plan_output += f"Route distance: {route_distance}miles\n"

+   # Google Maps URLを生成して表示
+   generate_google_maps_url(route, titles)

出力結果

Objective: 172379 miles
Route for vehicle 0:
 東京ドイツ村 -> 道の駅 富楽里とみやま パーキングエリア -> 原岡桟橋 (岡本桟橋) -> 海ほたるPA -> 0

Generated Google Maps URL: https://www.google.com/maps/dir/?api=1&origin=東京ドイツ村&destination=東京ドイツ村&waypoints=道の駅 富楽里とみやま パーキングエ リア|原岡桟橋 (岡本桟橋)|海ほたるPA&travelmode=driving

---

参考サイト

• [0] 旅行プランは最短ルートがいい【巡回セールスマン問題】
• [1] Google MAPの「自分のリスト」データをCSVに書き出す！
• [2] Google Mapのキーの取得方法
• [3] Pythonでジオコーディング(Geocoder/Googlemaps)
• [4] ジオコーディングのリクエストとレスポンス
• [5] Distance Matrix API
• [6] Google Maps API を利用して、指定した地点間の移動距離と時間を取得しよう！【Python】
• [7] 巡回セールスマン問題
• [8] Why I keep getting an error of MAX_ELEMENTS_EXCEEDED when I don't overpass the daily free number of requests?
• [9] Distance Matrix API の使用量と請求額
• [10] Maps URLs

まとめ

今回は、Google Maps API を利用して観光地の最適ルートを計算するものです。計算結果はブラウザで確認できるようにしており、実際のドライブに導入しても直感的に利用可能になりました。