韓国の81,998軒の酒場を巡る最短徒歩ルート

 (math.uwaterloo.ca)
2 ポイント 投稿者 GN⁺ 2025-04-25 | 2件のコメント | WhatsAppで共有
  • 巡回セールスマン問題（TSP） は、韓国の81,998軒のバーを訪れる最短ルートを見つける問題で、Open Source Routing Machine (OSRM) を使って解かれた
  • このルートは 178日 以上かかる 最適ルート であり、OSRM の計算によって証明された
  • LKH code と Concorde code を用いて cutting-plane method を適用し、大規模な TSP 問題を解決した
  • 数理最適化 と オペレーションズ・リサーチ は、資源効率を高めるためのツール開発に重点を置いている
  • 研究は Roskilde University と University of Waterloo で行われ、IBM CPLEX Optimizer と Leaflet ライブラリが使用された

韓国の81,998軒のバーを訪れる最短ルート

  • 巡回セールスマン問題（TSP） は、韓国の81,998軒のバーを訪れる最短ルートを見つける問題で、Open Source Routing Machine (OSRM) を使って解かれた
  • このルートは 178日 以上かかる 最適ルート であり、OSRM の計算によって証明された
  • LKH code と Concorde code を用いて cutting-plane method を適用し、大規模な TSP 問題を解決した

大規模TSP問題の解決

  • 数理最適化 と オペレーションズ・リサーチ は、資源効率を高めるためのツール開発に重点を置いている
  • 研究は Roskilde University と University of Waterloo で行われ、IBM CPLEX Optimizer と Leaflet ライブラリが使用された

研究チームと謝辞

  • 研究チームは William Cook、Daniel Espinoza、Marcos Goycoolea、Keld Helsgaun で構成されている
  • IBM の CPLEX Optimizer と Leaflet ライブラリを用いて研究が行われた
  • 韓国警察庁 のデータベースを通じて、韓国のバーの位置情報を確保した

関連記事

2件のコメント

 
xguru 2025-04-25

韓国の81,998軒の酒場をすべて巡る最短の徒歩ルートは178日 という記事を、GeekNewsアカウントで Hacker News に投稿したのですが。
多くの投票を集めて6時間トップを維持した末に人気記事となり、再び GN+ に逆輸入（？）されましたね。

その記事には英語版も一緒にあったのでそうしてみたのですが、今後は英語を含む記事をときどき Hacker News 側にも投稿してみようと思います。
 
GN⁺ 2025-04-25
Hacker Newsのコメント
  • 1.33億個の頂点を含むTSPソリューションが印象的
    • このツアーは最短経路の1.0038倍の長さ
    • Bell Labsの確率的アルゴリズムを使うと結果がどれほど悪くなるのか気になる
  • 古典的なTSPアプローチの説明
    • すべてのノードを任意の経路でつなぐ
    • 経路を2か所で切って3つの部分にする
    • 3つの部分を6通りの可能な方法で並べ替え、最も短いものを選ぶ
    • 改善がなくなるまで2〜3の手順を繰り返す
    • 最適な結果を保証するわけではないが、ほとんどの実問題では最適かそれに非常に近い
  • 総距離に触れていないのが奇妙
    • 移動時間を解決することが目的だが、実際の移動距離を知るのも興味深いはず
    • 消費カロリーを計算したり、最短距離経路からどれほど外れているか確認できる
  • オハイオ州サイズの国にほぼ8万2千軒のバーがあるという考えに圧倒される
  • COVIDの期間中、CityStridesを使って町のすべての通りを歩く目標を立てた
    • 歩いた距離を追跡し、町の何パーセントを歩いたか教えてくれる
    • 経路を最適化はしなかったが、重複なしでできるだけ多くの距離を歩くのは楽しい頭の体操だった
    • 自動化ツールも面白いかもしれないが、手作業でやることが旅の一部だった
    • CityStridesのサイトを見て回ると、人々のLifeMapsを見ることができる
    • 驚くほどたくさん歩く人もいる
  • 60年代のアイルランド軍で尋ねられていた質問を思い出した
    • "Bachelor's WalkからCollins Barracksまで、バーを通らずに行くには？"
    • 答えは"すべてのバーに入ること"だった
  • このデータセットを見つけたのは印象的だが、より難しいというほどではない
    • 最後の巡回セールスマンの最高記録を破ることと、計算を終えられないことの間にある微妙なバランス
  • NPが再びPのように見える
    • 学校では13が最大だと習い、80年代には教授が15まで進歩させた
    • その後20、20,000、今回は80,000が証明された
    • World TSPページでは記録が100万
    • 現在の最大の証明済み最適値は3,178,031
    • CUDAでやるべきで、普通のCでやるべきではない
  • Branch-and-boundは「教科書に載っている」アルゴリズム
    • LPソルバーをブラックボックスと見なすなら、本質的には非常に単純だがとても有用
  • 新しいバーがいくつか開き、いくつかは閉まったようだ
    • 再計算の時間だ