数年の空き時間があり、ウォーキングが好きで、おいしいスナック料理が好きで、日本が好きなら、私たちはあなたのためのツアーを持っています。 40,426の日本のコンビニエンスストアに歩いて行くための旅行セールスマン問題（TSP）を解決しました。 往復の総時間は35,578,434秒、または411日18時間53分54秒です。 そのような旅で毎秒を数える可能性は低いですが、このレベルの精度は、これは単なる良いルートではなく、40,426ストップのTSPに最適なソリューションであると指摘しています。

問題自体は、オープンソースルーティングマシン（OSRM）を使用して作成され、店舗のペアごとに817,110,525店舗間の移動時間の表を作成しました。私たちの計算は、最適な証明とともにツアーを生成しました。つまり、OSRMの移動時間で測定すると、ツアーが可能な限り短いことを保証します。

それは難しい計算でした。非常に大まかな見積もりでは、プロセッサコアが1つしかない場合（私たちの場合は、Intel Xeon Gold 5218 CPU @ 2.30GHzの一部）、総実行時間は約43年になります。議論は計算ページで見つけることができます。

「日本のどの都市でも散歩してみてください。コンビニエンスストアを通らずに数ブロック進むのは難しいでしょう。ワンストップショップは至る所に街並みが散りばめている。地元の人々に知られているように、こんびに遍在しているので、それらのない日本での生活を想像するのは難しいです。」

「多くの住民にとって、こんにと呼ばれる55,000以上の陽気でジングルに満ちた店は、日常生活に欠かせないものです。何百万人もの人々が毎日店に集まり、食べ物を受け取り、荷物を送り、請求書を支払います。

「日本の生活は、こんびとしてよく知られているユビニアストア（コンビニエンスストア）と深く結びついています。それらは全国の約55,600か所で見つけることができます。"

素晴らしいHomemateウェブサイトには、コンビニエンスストアカテゴリの45,485店舗が掲載されています。これらから、主要チェーンのセブンイレブン、ファミリーマート、ローソン、ミニストップ、デイリー山崎、セイコマートを組み合わせた、リストには徒歩方向が含まれている40,426のコンビニの場所を抽出しました。ニュース記事で言及された55,000以上の場所がないのは残念ですが、それでも国中を巡るツアーには本当に素晴らしい選択です。

データページで、40,426コンビニの緯度経度座標のリストを見つけることができます。

下の図は、konbini40426ツアーのインタラクティブマップのスクリーンショットです。左側のメニューでは、9つのリージョンから1つを選択して表示できます。右上では、カラーストリートマップまたはストリートラベルのないグレースケールマップを選択できます。このメニューのすぐ下に、ストップマーカーを表示するか、ツアーエッジを表示するか、またはその両方を表示するかを選択できます。画像をクリックすると、地図を見ることができます。

ここには、サイト全体に表示されるさまざまな地図図面で使用されるポイントマーカーの鍵です。

インタラクティブマップの表示に問題がある場合は、以下の図面をクリックして、ツアーの高解像度画像を表示できます。都市地域のクローズアップビューについては、Citiesページをご覧ください。

新聞、人気ジャーナル、ブログ、科学プレスリリースは、現在の世代のコンピューターでは、TSPの小さなインスタンスでさえ解決できないと定期的に報告しています。典型的な例は、ワシントンポストからの次の引用です。

「たとえば、22都市間の最も効率的なルートを計算するには、ラップトップコンピュータに1,000年かかります。」

このようなステートメントは、TSPを解決する唯一の方法は、可能な各ツアーを1つずつチェックすることであると仮定します。それは間違いなく私たちの40,426の停留所では機能しません。 この場合のツアー数はおおよそ 1.5の後に168670のゼロが続く.

この膨大な数の可能な解決策は恐ろしいですが、TSPのこの大きな例を解決できないという意味ではありません。私たちの攻撃は、非常に優れたTSPソリューションを計算するためのLKHコードと、品質保証を生成するための「切断平面法」として知られているものを適用するためのConcordeコードを組み合わせたものです。計算ページで、これらのツールの適用方法に関する簡単な説明を見ることができます。

切断平面法をざっと垣間見るには、サイエンティフィック・アメリカンの短い記事でプロセスを説明する方法は次のとおりです。

「アイデアは、ヨギ・ベラのアドバイスに従うことです。「道の分岐路に着いたら、それを取ってください。」線形プログラミングと呼ばれるツールを使用すると、道路を使用するかどうかをすぐに決定するのではなく、都市のペアを結ぶ道路に分数を割り当てることができます。このモデルでは、フォークの両枝に沿って半分のセールスマンを送っても問題ありません。」

「このプロセスは、すべての都市について、到着道路と出発道路に割り当てられた分数がそれぞれ1つに加算されるという要件から始まります。その後、段階的に、さらに制限が追加され、それぞれが道路に割り当てられた分数の合計が含まれます。線形プログラミングは最終的に、各道路の最良の決定、したがって可能な限り最短のルートを示しています。

数分あれば、講演のビデオをご覧ください最適なツアーは国立数学博物館、この方法が詳細に説明されています。

ランス・フォートナウの記事50年のP対NPと不可能な可能性で素晴らしい議論を見つけることができます。

汎用最適化方法の開発とテストの手段として、旅行セールスマン問題の大きな例を使用しています。世界は限られたリソースを持っており、数学的最適化とオペレーション研究の応用数学分野の目的は、これらのリソースを可能な限り効率的に使用するのに役立つツールを作成することです。

数学的モデリングとその産業、商業、医学、環境への影響に関する一般的な情報については、数学の研究と教育を支援する多くの協会を指します。American Mathematical Society、Mathematical Association of America、Mathematical Optimization Society、INFORMS（オペレーションズリサーチ）、およびSIAM（応用数学）。

日本では、主要な5年間の研究プロジェクトであるAFSAには、計算離散最適化のアプリケーションを成功させるために不可欠なツールをカバーする革新的なアルゴリズムと最適化の研究が含まれています。

ウィリアム・クック、組み合わせと最適化、ウォータールー大学、カナダ
Daniel Espinoza、Google、研究開発、米国
Marcos Goycoolea、ビジネススクール、アドルフォ・イバネス大学、チリ
Keld Helsgaun、コンピュータサイエンス、ロスキルデ大学、デンマーク

計算で発生した膨大な数の線形プログラミングモデルは、IBM CPLEX Optimizerで解決されました。優れたソフトウェア学術研究に無料で利用できるようにしてくれたIBMに感謝します。

ツアーの地図図は、Leafletモバイルフレンドリーなインタラクティブマップ用のオープンソースJavaScriptライブラリを使用して作成され、OpenStreetMap、Carto Basemaps、Stadia Mapsによって構築されたマップタイルを使用します。

コンビニエンスストアの場所は、日本全国の小売店を検索できるHomemateのウェブサイトから取得されました。

ポイントツーポイント歩行時間の表は、オープンソースルーティングマシン（OSRM）で作成されました。