韓国の81,998軒の酒場をすべて巡る最短徒歩ルートは178日

 (math.uwaterloo.ca)
23 ポイント 投稿者 xguru 2025-04-23 | 10件のコメント | WhatsAppで共有
  • ウォータールー大学のウィリアム・クック教授が、81,998軒の韓国の酒場を訪れる最短ルートとして巡回セールスマン問題（TSP）を計算した世界初の事例
  • Open Source Routing Machine (OSRM) を用いて約33億組の徒歩時間を計算し、数学的に最適であることを証明
  • 計算結果では、休まず歩いた場合の所要時間は合計15,386,177秒、つまり178日1時間56分17秒
  • TSP最適化にはLKHとConcordeのツールが使われ、切除平面法が適用された
  • これまで最多訪問ルートだったオランダの57,912地点ルートを上回る、世界最大規模の道路ベースTSP解決事例

韓国のすべての酒場を歩く巡回セールスマン問題（Traveling Salesman Problem）

  • 韓国にある81,998軒の酒場をすべて訪れ、再び出発点に戻る最短ルートを計算
  • 世界で初めて、これほど多くの場所を含むTSP問題を最適に解決
  • 酒場間の合計3,361,795,003組の徒歩時間を**OSRM - Open Source Routing Machine** で計算
  • 数学的に、このルートより短いルートは存在しない
  • この問題は、TSP問題として訪問地点数基準で史上最大規模

最短ルートの所要時間

  • 計算された最適ルートを休まず歩くと、合計15,386,177秒を要する
  • これは178日1時間56分17秒に相当する
  • 実際には歩く途中で休んだり飲んだりするため、正確に終えるのは難しい
  • OSRMベースの徒歩時間では、1秒たりとも短縮できない最適ルート

TSPの歴史的文脈と記録更新

  • これまでの最大記録はオランダの57,912地点の自転車ルートだった
  • 今回のkorea81998ルートは、それを上回る規模のTSP問題解決事例
  • 計算は2024年12月から2025年3月まで、ロスキレ大学とウォータールー大学で実施
  • 詳しい計算内容は別途計算ページで確認できる

ルートの可視化方法

  • ルートはインタラクティブ地図で確認でき、7つの地域に分けて探索可能
  • さまざまな可視化モード（カラー距離マップ、グレースケールなど）を提供
  • ルートの一部について高解像度画像も別途提供
  • 都市ごとのクローズアップ表示は都市ページで提供される

TSP解法戦略と誤解

  • 一部メディアでは「22都市だけでも1000年かかる」と報じられるが、これはすべてのルートを無作為に試す場合を意味する
  • 実際には高度な最適化手法によって、多数の地点でも解くことが可能
  • korea81998 の場合、可能なルート数は2の後ろに0が367,308個続く数に達する
  • 解法には**LKH(Lin-Kernighan Heuristic)アルゴリズム** と Concorde TSP Solver - 切除平面法 が組み合わせて使われた

切除平面法の概念要約

  • 線形計画法を基盤とする
  • 道路を使うかどうかではなく、接続の度合いを0〜1の数値で表現
  • 段階的に制約条件を追加しながら最短ルートを見つける
  • 詳しい説明はScientific AmericanとYouTube講演で確認できる

P対NP問題

  • TSP問題はNP完全問題であり、P対NP問題の代表例
  • 関連する興味深い議論はランス・フォートナウ教授の論文で紹介されている
  • この問題は計算機科学で最も有名な未解決問題の一つ

数理最適化の意義

  • このプロジェクトは汎用最適化手法の実験であり、発展のための基盤でもある
  • 産業、商業、医療、環境分野での応用可能性が高い
  • 数理モデリングは、限られた資源を効果的に使うための重要な道具

研究チーム紹介

  • William Cook: カナダ・ウォータールー大学
  • Daniel Espinoza: チリ・Alicanto Labs
  • Marcos Goycoolea: チリ・アドルフォ・イバニェス大学
  • Keld Helsgaun: デンマーク・ロスキレ大学

謝辞

  • IBM CPLEX Optimizer: 学術研究向けに無償提供してくれたことに感謝
  • 地図はLeaflet、OpenStreetMap、Carto、Stadia Mapsを用いて作成
  • オム・サンイル博士が韓国警察庁データに基づく酒場位置データを提供
  • 徒歩時間の計算には**OSRM** を活用

他国のTSPプロジェクト事例

  • 日本: コンビニ40,426店
  • 英国: 酒場49,687軒
  • 米国: 歴史的場所49,603か所
  • オランダ: 記念物57,912か所

追加学習資料

関連記事

10件のコメント

 
ep6tri 2025-04-24

英語版ページは https://www.math.uwaterloo.ca/tsp/korea/index.html です。
このツアーは確かに非現実的です。陸地から済州島や鬱陵島へ移動する際、船で移動する海路は考慮されていないようです。この図を見れば分かります: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png

訪問にかかる推定時間を正確に計算することが目的なのではなく、TSPを現実のデータで解いたことに意義があるのでしょう。
 
skshin 2025-04-23

島との移動はどうするの？ 徒歩で？
 
halfenif 2025-04-23

walking and ferry と出ているのを見ると、どうやら船に乗るようです。
 
woalsdnd 2025-04-23

リアルタイムで新規開業や閉業が発生する場合は、どうすればよいのでしょうか？
 
majorika 2025-04-23

> 私は2024年3月に大田にあるKAISTでTSPの講義を行う予定で、大田TSPツアー向けの地域データセットを探していました。2023年12月、オム・サンイル博士から「警察庁が作成した全国の酒場データセットが必要ですか？ 最新ファイルは1,000ウォンで、90,680件の項目があります」とメールが届きました。すごい。1,000ウォンが1ドル未満かどうかをまず確認し（為替レートが逆になっていないか確認しておいてよかったです）、それから「ありがとうございます！」と返信しました。

https://www.math.uwaterloo.ca/tsp/korea/sk_data.html
 
kimjoin2 2025-04-23

わあ、こんな背景があったんですね。整理して共有してくださりありがとうございます
 
kimjoin2 2025-04-23

韓国が対象として選ばれた理由も気になりますね 👀
 
firea32 2025-04-28

1000ウォンで質の高いデータを得られるという点も一役買っていたのでしょう :)
 
halfenif 2025-04-23

> 私は2024年3月に大田にあるKAISTでTSPの講義を行う予定で、大田TSPツアー向けの地域データセットを探していました。

おそらく韓国で講演することになっていたので、関連情報を探していたのだと思います。
 
bbulbum 2025-04-23

韓国に酒場が多いから、これをテーマにしたのかな..