Streamlit で実住所に対する巡回セールスマン問題をGoogleMapに出力するアプリ

概要

Streamlit で実住所に対する巡回セールスマン問題をGoogleMapに出力するアプリについて解説する．今回は，入力として実住所を入力し，入力した実住所を巡回する（近似）最適解をGoogleMapに出力することを考える．このとき，実住所間の距離は，GoogleMapAPIを用いて，その時の移動時間（移動距離）を取得し，巡回セールスマン問題を解く際の入力情報とする．

UI

使い方はシンプルで，住所を入力し，解の探索アルゴリズムを選択し，最適ルートを表示のボタンを押す．住所は以下10カ所を入力した．

東京都千代田区丸の内1丁目9-1
東京都中央区銀座4丁目12-15
東京都港区赤坂9丁目7-1
東京都新宿区西新宿2丁目8-1
東京都文京区本郷7丁目3-1
東京都台東区浅草2丁目3-1
東京都墨田区押上1丁目1-2
東京都渋谷区宇田川町1丁目1-1
東京都世田谷区三軒茶屋2丁目15-14
東京都江東区豊洲3丁目6-1

結果は，以下のように出力される．
まずは，訪問順序である．

次に，GoogleMapへの出力結果である．

参考までに，GoogleMapAPIを用いて取得した住所間の移動時間（移動距離）は以下となる．この数値は，取得するタイミング（日時，時刻）で異なる．また，行きと帰りの移動時間は対象ではない（非可換性）．実行する度に，GoogleMapAPIを利用するため，使い過ぎに注意いただきたい．

サンプルコード

import streamlit as st
import pandas as pd
import numpy as np
import requests
from geopy.distance import geodesic
import itertools
import time
import folium

# Google Maps API設定
GOOGLE_MAPS_API_KEY = "<GOOGLEMAPAPIKEY>"

# **全列挙型アルゴリズム**（Brute Force）
def solve_tsp_brute_force(dist_matrix):
    locations_count = len(dist_matrix)
    min_distance = float('inf')
    min_route = None
    for perm in itertools.permutations(range(locations_count)):
        route_distance = 0
        for i in range(locations_count - 1):
            route_distance += dist_matrix[perm[i], perm[i + 1]]
        route_distance += dist_matrix[perm[-1], perm[0]]  # 戻る距離
        if route_distance < min_distance:
            min_distance = route_distance
            min_route = perm
    return min_route, min_distance

# **近傍法**（Greedy Algorithm）
def solve_tsp_greedy(dist_matrix):
    locations_count = len(dist_matrix)
    unvisited = set(range(locations_count))
    current_location = 0
    route = [current_location]
    total_distance = 0
    unvisited.remove(current_location)
    while unvisited:
        nearest_neighbor = min(unvisited, key=lambda x: dist_matrix[current_location, x])
        route.append(nearest_neighbor)
        total_distance += dist_matrix[current_location, nearest_neighbor]
        current_location = nearest_neighbor
        unvisited.remove(current_location)
    total_distance += dist_matrix[route[-1], route[0]]
    return route, total_distance

# **住所を緯度・経度に変換する関数**
def geocode_address(address):
    url = f"https://maps.googleapis.com/maps/api/geocode/json?address={address}&key={GOOGLE_MAPS_API_KEY}"
    response = requests.get(url)
    data = response.json()
    if data["status"] == "OK":
        lat = data["results"][0]["geometry"]["location"]["lat"]
        lng = data["results"][0]["geometry"]["location"]["lng"]
        return lat, lng
    else:
        return None, None

# **住所間の移動時間を取得する関数**
def get_travel_time_matrix(addresses):
    origins = "|".join(addresses)
    destinations = "|".join(addresses)
    url = f"https://maps.googleapis.com/maps/api/distancematrix/json?origins={origins}&destinations={destinations}&key={GOOGLE_MAPS_API_KEY}"
    response = requests.get(url)
    data = response.json()
    dist_matrix = []
    if data["status"] == "OK":
        for row in data["rows"]:
            dist_matrix.append([element["duration"]["value"] for element in row["elements"]])
    else:
        return None
    return np.array(dist_matrix)

# Streamlit UI
st.title("巡回セールスマン問題")

# 住所をテキストエリアで入力
addresses_input = st.text_area("住所を改行区切りで入力してください（例: 東京都千代田区丸の内1丁目）", height=200)

# アルゴリズム選択
algo_choice = st.radio("アルゴリズムを選択してください:", ("全列挙型アルゴリズム", "近傍法"))

# 地図表示ボタン
if st.button("最適ルートを表示"):
    if addresses_input.strip():
        addresses = addresses_input.strip().split("\n")
        locations = []
        for address in addresses:
            lat, lon = geocode_address(address)
            if lat is not None and lon is not None:
                locations.append((lat, lon))
            else:
                st.error(f"住所 {address} の緯度・経度を取得できませんでした。")
                break
        if locations:
            dist_matrix = get_travel_time_matrix(addresses)
            if dist_matrix is not None:
                st.text("計算中...お待ちください")
                start_time = time.time()
                if algo_choice == "全列挙型アルゴリズム":
                    min_route, min_distance = solve_tsp_brute_force(dist_matrix)
                elif algo_choice == "近傍法":
                    min_route, min_distance = solve_tsp_greedy(dist_matrix)
                end_time = time.time()

                # 計算時間を出力
                st.write(f"計算時間: {end_time - start_time:.2f} 秒")
                st.write(f"最短経路の移動時間: {min_distance / 60:.2f} 分")

                # 訪問順の住所情報を出力
                visit_order = [addresses[i] for i in min_route]
                st.write("訪問順序:")
                for idx, addr in enumerate(visit_order, 1):
                    st.write(f"{idx}. {addr}")

                # 拠点間の移動時間テーブルを出力
                st.write("拠点間の移動時間テーブル (秒):")
                df = pd.DataFrame(
                    dist_matrix,
                    index=[f"住所{i+1}" for i in range(len(addresses))],
                    columns=[f"住所{i+1}" for i in range(len(addresses))]
                )
                st.dataframe(df)

                # 地図に表示
                locations_route = [locations[i] for i in min_route]
                locations_route.append(locations_route[0])
                map_center = locations_route[0]
                m = folium.Map(location=map_center, zoom_start=14)
                for i, loc in enumerate(locations_route):
                    address_info = visit_order[i % len(visit_order)]  # 最後はスタート地点
                    folium.Marker(
                        location=loc,
                        popup=f"訪問順序 {i+1}: {address_info}",
                        icon=folium.Icon(color="blue")
                    ).add_to(m)
                folium.PolyLine(locations_route, color='blue', weight=2.5, opacity=1).add_to(m)
                st.write("訪問順序に沿った最適経路の地図:")
                st.components.v1.html(m._repr_html_(), height=600)
            else:
                st.error("移動時間の取得に失敗しました。APIキーや住所の確認をしてください。")
    else:
        st.warning("住所を入力してください。")