1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@mshdtksk

Gemini が決めた旅程は本当に効率的か？ Google Maps Platform と数理最適化を Cloud Run 上で組合せて検証する

1
Posted at

はじめに

　生成AIの普及により，旅行プランの作成をLLMに任せることが一般的になりつつある．Gemini に「京都で歴史とカフェを巡りたい」と伝えれば，もっともらしい旅程が数秒で返ってくる．しかしながら，その訪問順が本当に効率的である保証はどこにもない．出発地点を固定した15地点の訪問順は

15! = 1,307,674,368,000

通り存在し，全列挙は現実的ではない．LLM は意図理解や候補提示は得意である一方，制約を厳密に守りながら巨大な組合せの中から最良の解を選ぶことは苦手である．逆に，数理最適化は制約下での厳密な探索が得意である一方，現実の道路状況・施設情報・標高といったデータを自ら持たない．

　そこで本記事では，この両者の間を Google Maps Platform で接続し，「Gemini が意図を構造化し，Google Maps Platform が現実を数値化し，数理最適化が訪問順を決定する」という分業型の1日旅行プランナー「Michi」を構築し，Cloud Run 上で公開した事例について述べる．あわせて，同じ訪問地点集合に対して Gemini に順番だけを決めさせ，数理最適化の結果と公平に比較する検証を行ったので，その設計についても紹介する．

　本記事の構成は次のとおりである．第1章で作成したアプリの概要を，第2章で全体アーキテクチャを述べる．第3章では Google Maps Platform の4つのAPIをどのように最適化モデルの入力へ変換したかを，第4章では数理最適化モデル（選択型TSP）の定式化を述べる．第5章で Gemini との比較実験の設計を，第6章で Cloud Run・Secret Manager を用いた実行基盤と運用上の工夫を述べ，第7章で現状の課題と今後の改善を整理する．

1. 作ったもの

　「Michi」は，自然文の希望から1日旅行プランを生成するWebアプリである．

  • 入力：自然文（例：「鎌倉で寺社とカフェを巡りたい」），日付，出発・帰着時刻，出発地点
  • 出力：訪問地点，訪問順，各地点の予定時刻，地図（マーカーと順路）

　デモは以下のURLから誰でも試すことができる．

https://michi-trip-planner-hdjsogf5hq-an.a.run.app

　また，ソースコードは以下のGitHubリポジトリで公開している．本稿で述べる Google Maps API の呼び出し・数理モデル・Cloud Run へのデプロイ構成の実装は，いずれもこのリポジトリで確認できる．

https://github.com/mshdtksk/google-map-tsp

image.png

　特徴は，単に「候補を出す」のではなく，予測移動時間・渋滞遅延・推定待ち時間・上り高低差という4つの現実コストを考慮した訪問順を，数理最適化ソルバー（Gurobi）で決定する点にある．さらに，同じ訪問地点集合を使った Gemini の参考案を並べて表示し，両案を同じ指標で事後評価できるようにした．

2. 全体アーキテクチャ

　システム全体のデータの流れを次に示す．

　役割分担は次のとおりである．

コンポーネント 役割
Gemini API 人間の曖昧な希望を検索条件（エリア・テーマ・検索語・移動手段）へ変換する
Google Maps Platform 現実世界の地点・移動時間・渋滞・標高を数値化する
Gurobi 制約を満たす巡回順を最適化する
Cloud Run ＋ Streamlit 入力・比較・地図・時刻表を表示する

　本システムでは，Google Maps Platform を「地図を表示するツール」としてではなく，最適化モデルへパラメーターを供給するデータ基盤として用いている．地図は結果の可視化にも使うが，本質的な価値は Places・Routes・Elevation が返す数値データにある．

3. Google Maps Platform を最適化モデルの入力に変換する

3.1 Places API (New)：候補地点集合を作る

　Text Search を利用し，Gemini が生成した検索語から実在施設を検索する．取得項目は Place ID，施設名，住所，緯度・経度，評価，口コミ数，施設カテゴリ，Google Maps URI である．

　候補数を抑えるため，次のスコアで事前に並べ替えて絞り込みを行う．

score_j = rating_j \times \log_{10}(reviewCount_j + 10)

　注意点として，このスコアは最終的な訪問順ではない．最適化へ投入する候補を絞るための前処理であり，順番を決めるのはあくまで数理最適化である．また，Place ID による重複排除を行うことで，同一施設が複数の検索語にヒットした場合の二重登録を防いでいる．

3.2 Routes API：移動コストを行列化する

　computeRouteMatrix を使い，すべての候補地点間について予測移動時間・通常時移動時間・距離・経路の有無を取得する．候補が $n$ 地点なら必要な要素数は概ね $n^2$ となる．

　車移動では渋滞を反映するため，次を指定する．

  • travelMode = DRIVE
  • routingPreference = TRAFFIC_AWARE
  • ユーザーが選んだ旅行日時を departureTime として指定

　渋滞遅延は，交通状況を反映した予測時間と通常時の差分として算出する．

c_{ij} = \max(0,\ t_{ij}^{traffic} - t_{ij}^{static})

　実装で気を付けるべき点を2つ挙げる．1つ目は公共交通（TRANSIT）の制限である．TRANSIT の Route Matrix は1リクエスト100要素までであり，16地点では256要素になるため，出発地点側を $6\times16 + 6\times16 + 4\times16 = 256$ のように分割してリクエストし，取得後に元の行列へ統合した．2つ目は到達不能経路の扱いである．ROUTE_NOT_FOUND を0分として扱うと「移動時間ゼロの魔法の経路」が生まれ，最適化が積極的にその区間を選んでしまう．そのため到達不能区間は高いコストのまま保持し，公共交通で取得できない区間は徒歩経路で補完した．

3.3 Elevation API：坂の負担を非対称コストにする

　各候補地点の緯度・経度から標高を取得し，地点 $i$ から $j$ への上り標高差を次のように定義する．

h^+_{ij} = \max(0,\ elevation_j - elevation_i)

　同じ2地点でも，A から B が上りなら B から A は下りになる．旅行時の負担として上りのみをペナルティ化するため，コスト行列は非対称になる．重みは上り100mを10分相当（$0.1 h^+_{ij}$）として評価した．これにより，単に距離が短い経路ではなく坂の負担が小さい経路を選びやすくなる．徒歩や自転車の旅程では特に効果が大きいと考えられる．

3.4 Maps JavaScript API：結果を可視化する

　最適化の結果は，番号付きマーカー，到着予定時刻，訪問順を結ぶポリライン，全地点が収まる自動ズームで表示する．旅程内の施設名は Places API が返した googleMapsUri へリンクし，ワンクリックで施設ページを確認できるようにした．なお，現状の地図上の線は訪問順を示す直線であり道路形状そのものではない（移動時間の計算自体は Routes API の道路ネットワークに基づく）．

3.5 データ対応表

実装パラメーター 取得元 最適化での用途
施設名・座標・評価・口コミ数・カテゴリ Places API (New) 候補集合・事前順位付け・待ち時間推定
予測移動時間・通常時移動時間 Routes API 辺コスト・渋滞遅延・時間制約
標高 Elevation API 上り高低差ペナルティ
マーカー・地図・リンク Maps JavaScript API 結果の可視化

4. 数理最適化モデル：選択型TSP

4.1 問題の位置づけ

　通常のTSPはすべての都市を1回ずつ訪問して出発地へ戻る最短巡回路を求めるが，本システムでは候補15地点すべてが時間内に入るとは限らない．そのため，訪問地点の選択を含む選択型TSP（Selective TSP）として，混合整数線形計画問題（MILP）で定式化した．

　決定変数は次のとおりである．

  • $x_{ij} \in {0,1}$：地点 $i$ から $j$ へ移動するか
  • $y_i \in {0,1}$：地点 $i$ を訪問するか
  • $u_i$：MTZ部分巡回路除去用の訪問順序変数（連続）

4.2 目的関数

　4つの現実コストの加重和を最小化する．

\min \sum_{i \ne j} \left( t_{ij} + \lambda c_{ij} + w_j + \alpha h^+_{ij} \right) x_{ij}
\qquad (\lambda = 1,\ \alpha = 0.1)

　$t_{ij}$ 自体が交通状況を反映した予測時間であり，さらに $c_{ij}$ を加えることで，同じ所要時間でも渋滞依存度が高い経路をより強く避ける設計とした．$w_j$ は施設カテゴリと口コミ数から推定した待ち時間である（詳細は4.5節）．

4.3 制約式

　出発・帰着，流量保存，訪問数，時間予算，部分巡回路除去を制約とする．

\sum_{j \in V'} x_{0j} = 1, \qquad \sum_{i \in V'} x_{i0} = 1

\sum_{j \ne i} x_{ij} = y_i, \qquad \sum_{j \ne i} x_{ji} = y_i \qquad (\forall i \in V')

\sum_{i \in V'} y_i = K

\sum_{i \ne j} \left( t_{ij} + s_j + w_j \right) x_{ij} \le B

u_i - u_j + n x_{ij} \le n - 1 \qquad (i \ne j,\ i,j \in V')

　時間予算 $B$ には移動・滞在 $s_j$・待ち時間を含めるが，高低差は快適性の評価にのみ用い，時計上の経過時間には加えない．最後のMTZ制約は，出発地点を含まない独立した小ループ（例：本体の巡回路とは別に C→D→C が発生する）を除去する定番の制約である．

4.4 訪問数の決め方と求解

　11時間の旅行枠に対して15地点が実行不可能な日もあるため，訪問数 $K$ は次の方式で決める．

for K = min(15, 候補数) down to 10:
    K地点を訪問するTSPを解く
    実行可能解が見つかったら採用

　これは実質的に「訪問数を最大化し，その訪問数の中で総コストを最小化する」という辞書式の2段階優先を表現している．無理な旅程を提示しない，という点が実用上は重要である．

　Gurobi の実行設定は，求解時間上限3秒／訪問数，MIP Gap 2%とし，厳密な最適性証明よりも応答性を優先した．また，Gurobi が未導入・ライセンス利用不可・解が得られない場合に備え，現地点から追加コストが最小の地点を選ぶ最近傍法によるフォールバックを用意した．厳密最適化を基本としつつ，サービスとして停止しないためのヒューリスティックである．

4.5 待ち時間の推定について

　施設のリアルタイム待ち時間は Google Maps API から直接取得していない．施設カテゴリごとの基準値（レストラン20分，カフェ12分，美術館10分，観光名所8分，公園0分 など）に，口コミ数による人気補正 $\min(10,\ \lfloor 2\log_{10}(reviewCount+1) \rfloor)$ を加えた独自推定である．そのため本記事でもアプリ上でも「混雑の実測値」ではなく「施設属性から推定した待ち時間」と明示している．

5. Gemini との公平な比較実験

　本システムでは，LLM の常識的な順番と，現実の移動コストを知る数理最適化の順番を並べて比較できる．比較を公平にするため，実験は次のように設計した．

　まず，数理最適化が選んだ訪問地点集合を Gemini にもそのまま使わせる．比較対象は訪問地点の選択ではなく訪問順だけである．そのうえで，Gemini へ渡す情報を意図的に制限した．

Gemini へ渡す情報 Gemini へ渡さない情報
地点名 移動時間行列・渋滞・推定待ち時間・高低差
施設カテゴリ 住所・座標・口コミ数・旅行時間帯
評価 最適化された訪問順

　これは「人間が旅行雑誌を見て順番を考える」のに近い条件であり，現実の移動コストを知っているのは数理最適化側だけ，という状況を作っている．両案の表示時には，同じ Routes API の行列を使って移動時間・渋滞遅延・推定待ち時間・上り高低差を事後評価するため，Google Maps データを目的関数へ組み込むことの効果だけを比較できる．

　評価指標の読み方は次のとおりである．移動時間が短ければ地理的に効率的，渋滞遅延が小さければ渋滞依存度が低く，待ち時間が小さければ混雑しやすい施設配置を回避しており，上り高低差が小さければ身体的負担が小さい．ただし，目的関数は複数指標の加重和であるため，単一指標だけで優劣を決めるべきではない点には注意が必要である．

image.png

image.png

　実行例では，Gemini 案は観光ガイド的に自然な並びになる一方，地図上で経路が交差したり，同じ方面を行き来したりする傾向が見られた．数値は入力条件や実行日時により異なるため，実際の比較結果は上記のデモにて確認できる．

6. Cloud Run と Secret Manager による実行基盤

　アプリは Cloud Run（asia-northeast1）で公開した．構成は次のとおりである．

項目 設定
CPU ／ メモリ 1 vCPU ／ 1Gi
インスタンス数 最小0 〜 最大3
タイムアウト 300秒
コンテナ 非rootユーザーで実行

　最小インスタンス0のスケールトゥゼロ構成により，個人開発のデモアプリでも維持費を抑えられる．リクエストが来たときだけ起動し，Gurobi の求解を含めても300秒のタイムアウト内で応答が返る．

　セキュリティ面では，Gemini APIキー・Google Maps APIキー・Gurobi WLSライセンス情報を Docker イメージに含めず，Secret Manager から実行時に注入する構成とした．Cloud Run 専用のサービスアカウントを作成し，必要な Secret Manager の読取権限だけを付与している．あわせて，APIキーをエラー画面やログへ表示しない実装とした．

　そのほか，運用上の細かな工夫を挙げる．

  • Google API の 429／5xx エラーは指数バックオフ付きで再試行する
  • Google API が返す配列形式・辞書形式双方のエラーレスポンスに対応する
  • Gemini 出力に含まれる重複・対象外インデックスを補正する
  • API 呼び出し数（と費用）は候補数の二乗で増えるため，候補数を20件以下に制限する

7. 現状の課題と今後の改善

　本システムには現時点で次の課題が残っている．待ち時間はリアルタイム値ではなく推定であること，営業時間・休業日や食事時間帯を制約に含めていないこと，地図上の線が道路形状ではなく概略直線であること，移動時間行列が出発時点の予測であり各訪問時刻ごとの再計算ではないこと，である．

　改善の方向性としては，Places API の営業時間を Time Window 制約として組み込むこと，各区間の予定出発時刻で Routes API を再評価すること，Routes API のルートポリラインによる実道路描画，API結果のキャッシュ，重み $\lambda$・$\alpha$ のユーザー調整，複数日・複数車両問題への拡張が挙げられる．

8. まとめ

　本記事では，Gemini・Google Maps Platform・数理最適化を分業させた1日旅行プランナーを Cloud Run 上に構築した事例について述べた．Google Maps Platform は地図表示ツールにとどまらず，Places が「どこへ行くか」の候補を，Routes が「何分かかるか」の行列を，Elevation が「どれだけ上るか」を供給する，最適化モデルのデータ基盤として機能する．また，LLM と数理最適化は競合ではなく分業の関係にあり，Gemini が自然文の入口（意図の構造化）を担い，訪問順という組合せ最適化を数理最適化が担うことで，説明可能な意思決定が実現できる．さらに，Cloud Run のスケールトゥゼロと Secret Manager による実行時注入を組み合わせることで，商用ソルバーを含むデモアプリを低コストかつ安全に公開できる．

　特定の事例に対する限られた検証に基づいており，待ち時間推定や時間帯依存の移動時間には更なる改善が必要であるが，「Google Maps が現実をモデル化し，数理最適化が意思決定を行う」という構成は，旅行プランに限らず配送計画・施設配置・人員手配など実社会の幅広い課題に適用できると考えられる．LLM だけでは手が届かない「厳密に決める」領域にこそ，Google Cloud を活用する余地があるといえる．

参考

1
0
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
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?