2025/04/24 00:20 Shortest walking tour to 81,998 bars in Korea – TSP solved in 178 days
ロボ子、大変なのじゃ！韓国国内の81,998軒ものバーを巡るセールスマン問題が解決されたらしいぞ！
それはすごいですね、博士！ 巡回セールスマン問題（TSP）の事例ですね。81,998軒とは、かなり大規模ですね。
そうなんじゃ！ しかも、Open Source Routing Machine（OSRM）を使って、地点間の移動時間を計算したらしいぞ。なんと、3,361,795,003もの組み合わせを計算したんだって！
33億以上の組み合わせですか！ それは天文学的な数字ですね。OSRMを使った移動時間計算も興味深いです。
最短ルートは、歩行時間で178日以上かかるらしいぞ！
178日！気が遠くなりそうです。2021年に解決されたオランダの57,912ストップツアーよりも大きいとは、驚きです。
そうみたいじゃな。ロスキレ大学とウォータールー大学で計算されたみたいじゃ。線形計画法を使って最適なルートを決定したらしいぞ。IBM CPLEX Optimizerを使ったとか。
線形計画法ですか。都市のペアを結ぶ道路に、道路の一部を通ることを許容して、最適なルートを決定するのですね。興味深いです。
今回のデータは、韓国警察庁が管理するデータベースから取得したらしいぞ。基礎科学研究所のオウム・サンイル博士が取得したみたいじゃな。
巡回セールスマン問題は、汎用最適化手法を開発・テストする手段として使われることが多いですよね。今回の事例もその一環でしょうか。
その通りじゃ！今回の事例は、最適化技術の進歩を示す良い例じゃな。私たちも、この技術を応用して、何か面白いものが作れないかのう？
そうですね。例えば、配送ルートの最適化や、工場の生産スケジューリングなど、様々な分野に応用できそうですね。
おお！それは良いアイデアじゃ！ ロボ子、今度一緒に、最適化アルゴリズムについて勉強してみようかの。
はい、喜んで！ ところで博士、178日間バーを巡り続けるセールスマンは、肝臓が心配ですね。
確かに！ 178日も飲み続けたら、体の方が先に音を上げるのじゃ！ まさに「酔いどれセールスマン問題」じゃな！
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。