Konaviはどうやって最適ルートを見つけるの？

旅行ルートを組むのが難しい理由

ソウルで複数の観光地を回る順番を決めるとき、ほとんどの人は地図を広げて近い場所同士をまとめてルートを作ります。直線距離だけ見れば、この方法はかなり合理的に見えます。

しかし、実際に公共交通を使うと話が変わります。地図上ではすぐ隣なのに、地下鉄の路線がつながっておらず2〜3回乗り換えが必要な場所もあれば、逆に遠く見えても同じ路線上にあって1本で行ける場所もあります。ソウルの公共交通ネットワークは複雑なため、直線距離と実際の移動時間の差は予想以上に大きいのです。

さらに、ソウルの公共交通は非対称でもあります。AからBへの所要時間とBからAへの所要時間が異なります。地下鉄の乗り換え構造やバス路線の方向によって、片方がずっと長くかかることが多く、訪問順序を逆にするだけで合計移動時間が大きく変わることがあります。

結局、地図を見ただけでは最適な順番を判断するのは難しいのです。Konaviはこの問題を実際の公共交通所要時間データと数学的最適化アルゴリズムで解決します。

ステップ1：実際の公共交通時間の収集

Konaviは写真が登録されたすべての観光地間のすべての方向の組み合わせについて、公共交通の所要時間を事前に計算してデータベースに保存しています。観光地は随時追加され、新しいスポットが登録されるたびに組み合わせも更新されます。

このデータは韓国の公共交通専門APIであるODsayから取得しています。Googleマップは韓国の公共交通ルートを正確に計算できないため、Konaviは韓国の交通データに特化したODsayを使用しています。

事前にキャッシュされたデータのおかげで、ルート検索時にAPIを大量に呼び出す必要がなく、素早く結果を提供できます。リアルタイムで計算が必要なのは出発地から各観光地までの時間だけです。この場合も出発地→観光地の方向のみ計算します。Konaviのルートは出発地から始まり最後の観光地で終わるオープンルートなので、観光地から出発地に戻る時間は不要だからです。

ステップ2：最適順序の計算（Held-Karpアルゴリズム）

すべての場所間の移動時間が揃ったら、KonaviはHeld-Karpアルゴリズムを使って最適な訪問順序を見つけます。

このアルゴリズムは、コンピュータサイエンスで有名な「巡回セールスマン問題（Travelling Salesman Problem）」を解く正確な方法の一つです。主なアイデアは以下の通りです：

• 可能なすべての訪問組み合わせを体系的に探索します
• すでに計算した部分ルートの結果を**記憶（メモ化）**して、重複計算を避けます
• 結果として、すべての順番を一つずつ試すよりはるかに高速に正確な最適解を求めます

Konaviのルートは出発地から始まり、最後の観光地で終わるオープンルートです。出発地に戻る時間は含まないので、最後の場所の近くで夕食を取ったり、宿に向かったり、自由にスケジュールを締めくくることができます。

ステップ3：外れ値検出（遠い場所のお知らせ）

最適ルートを計算した後でも、選んだ場所の一つが他の場所から離れた位置にあり、全体の移動時間を大幅に増やしている場合があります。

Konaviはこのような場所を自動的に検出します：

• 各場所を一つずつ外して、その場所なしでルートを再計算します
• 特定の場所を外したとき、合計移動時間が30%以上減り、節約できる時間が40分以上であれば、その場所を外れ値と判定します

外れ値が見つかった場合、Konaviはその場所を外すことを提案します。もちろんそのまま含めることもできますし、代わりに近くの別の観光地と入れ替えることもできます。

ステップ4：近くのおすすめ観光地

外れ値を除外したり場所を入れ替えたいとき、Konaviは現在のルートに最も少ない追加時間で挿入できる観光地をおすすめします。

単純に直線距離が近い場所ではなく、実際のルートのどの区間に入れたときに迂回が最も少ない場所を探します。例えば、A→Bの区間にCを挿入するとA→C→Bになりますが、このとき追加される時間（A→C + C→B − A→B）が最も小さい場所を上位に表示します。

まとめ

• 公共交通データ — 写真登録スポット間のすべての方向の組み合わせの実際の所要時間を事前キャッシュし、正確かつ高速に計算します。
• Held-Karp最適化 — 数学的に最短の訪問順序を計算し、保証された最適解を提供します。
• 外れ値検出 — 全体の移動時間を大幅に増やす場所を自動的に特定してお知らせします。
• 近くのおすすめ — 最小限の迂回で挿入できる代替スポットを提案します。