konbini40426の完全な計算は、Linuxサーバーの1つの単一のプロセッサコアで実行した場合、合計で約43年のコンピューター時間を使用しました。主な計算は、2024年10月と11月にウォータールー大学で10台のサーバーのネットワークで実行され、それぞれ32コアでした。TSP計算は、サーバーが日常のプロジェクトで忙しくないときに実行されました。
OSRM距離表の初期チェックの後、私はkonbini40426 TSPLIBファイルをLKHコードの作成者であり、オールラウンドツアーファインディングエキスパートであるKeld Helsgaunに送信しました。16時間後、ケルドは「LKH+MERGEは35578434の長さのコンビニツアーを発見した」と書いた。別の1週間後、ケルドはこの同じ長さのツアーをさらに2つ見つけました。大規模なマップインスタンスでのLKH結果に関する過去の経験に基づいて、この時点で、35578434はkonbini40426の可能な最短値に非常に近いに違いないと確信していました。それが近いだけでなく、実際には最適であることを最終的に証明するまでにさらに8週間かかりました。
最適性証明を生成する計算では、標準的な慣行に従い、最もよく知られているツアーの長さよりも1の上限で分岐してバウンド検索を開始し、検索に最適な解を再現するように強制しました（実行中のチェックとして）。しかし、最初に強い境界を持つことは、計算に大いに役立ちました。
最初のバウンドは、いくつかの方法でコンコルドコードをガイドします。これにより、ブランチアンドバウンド検索でサブプロブレムを剪定できます。これにより、コードは最初のバウンドよりも優れたツアーにいられないエッジを排除できます。切断面を見つけるために、より速いルーチンと遅いルーチンを切り替えるための公差を設定します。
しかし、konbini40426など、私たちが研究する最大の例では、LKHツアーが提供する最大の助けは、人間の決定側にあります。13,571-stop セブンイレブンツアーなど、より控えめなサイズのインスタンスの場合、通常、デフォルト設定でコンコルドスタートボタンを押して、最適な解決策を待つことができます。これは、解決プロセスの潜在的な改善を研究するために、解決可能性の限界を押し広げている最大のケースには当てはまりません。ここでは、その場で調整を行い、切断平面法と分岐バウンド検索を切り替え、新しい切断平面ルーチンの実験、分岐ルールのテストなどを行っています。これらの選択は、私たちが計算している下限と、最も有名なツアーによって与えられた上限の間のギャップに大きく依存します。だからLKH+MERGEに行く。
ツアーが可能な限り短いことを証明する鍵は、TSPインスタンスの線形プログラミング（LP）リラクゼーションを構築することです。つまり、すべてのTSPツアーが候補ソリューションであるようなLPモデルです。最適なLP値（または、より一般的には、デュアルLPソリューションの値）がβの場合、どのツアーもβより短い長さを持つことはできません。つまり、βはTSPの下限であり、ツアーの長さに品質保証を確立する手段を提供します。
TSPのLPモデルは、すべてのポイントツーポイント接続に0と1の間の（おそらく小数）値を割り当てます。ポイントツーポイント接続は、一対のストップを結合します。これはリンクまたはエッジと呼ばれます。ツアーは、すべてのリンクが0または1のいずれかに割り当てられるLPソリューションとして表現できます。値1に割り当てられたリンクは、ツアーで使用されるリンクに対応します。LPの制約は、すべてのツアーソリューションで満たされるルールです。次数方程式と呼ばれる基本的なルールは、停止ごとに、停止を満たすリンクの値が2に加算されなければならないということです。サブツアー不等式と呼ばれる重要なさらなるルールは、ストップSのサブセットに対して、一方の端がSにあり、もう一方の端がSにないリンクの値は少なくとも2つでなければならないということです。
すべての値が0または1を持ち、すべての次数方程式と部分不等式を満たすLP解はツアーです。素晴らしいが、LPソリューションには分数値があるかもしれない。これは、切断平面法の困難な作業が始まる場所です。このプロセスは、より多くのルールを追加し、下限βを増やし、LPソリューションをすべての0-1値に近づけます。
10月には、コンコルドのカッティングプレーン方式の実装を使用して、LPの品質を繰り返し改善し、つまり生成される下限を増やすために、LPのリラクゼーションをゆっくりと構築しました。
次の2つの図では、konbini40426で得られたLPソリューションを示しています。図面では、リンクは、0から1までのLP値に対して、白から赤、黒に徐々に変化する色合いで着色されています。値0のリンクは白で着色され（画像をすっきりと保つために、0.01未満の値を持つリンクは描画しません）、値0.5のリンクは赤で着色され、値1のリンクは黒で着色されます。
日本全体の画像では、エッジの多くが黒であることがわかります。これは、追加したLPルールが、リンクに割り当てられた値を制限する良い仕事をしていることを意味します。しかし、2番目の画像のように、より多くの作業が必要なカラフルな領域があります。私たちの計算では、LPソリューションのこれらの領域を処理するために、切断平面法と分岐およびバウンド検索を組み合わせています。
分岐とバウンドの検索は、候補ツアーのセットを2つの小さなセットに繰り返し分割することで、下限の価値を高めようとします。たとえば、2つの停留所間のリンクを選択し、残りのツアーをリンクを確実に使用するものと、リンクを使用しないものに分割する場合があります。したがって、単一の親から2つの新しい子サブ問題を作成します。各子にカッティングプレーン法を適用すると、それぞれの場合に親から与えられたLP境界を改善し、全体的な下限を増やすことができます。
以下の日本全画像では、下限β = 35574287を提供するLPモデルに最適なソリューションを示しています。これは強力なLPモデルです。26347リンクに値1を割り当て、下限と35578434ツアーの長さの間にわずか4147秒のギャップを与えます。それにもかかわらず、分岐ステップはバウンドを改善することができます。
このLPモデルでは、コンコルドは、以下の全日本画像で赤で強調表示された地域で分岐することを選択しました。LPソリューションのこの領域は、2番目の画像で展開され、一連の停止は青いディスクで示されます。
一方の端が示されたセットにあり、もう一方の端がセットにないリンクの合計は2.8です。ツアーは偶数回セットに出入りする必要があるため、これは分岐に最適です。問題を2つの子サブ問題に分割しました。1つのサブ問題には、セットに出入りするリンクが最大2に加算されなければならないという制約があり、2番目のサブ問題には、セットに出入りするリンクの合計が少なくとも4にしなければならないという制約があります。切断面を追加すると、最初のサブ問題に35577076の境界が、2番目のサブ問題に35576908の境界が得られます。どのツアーも2つのサブ問題のいずれかに対する候補LPソリューションでなければならないため、どのツアーでも少なくとも35576908の長さでなければならないことがわかっています。分岐ステップは、4147秒から1526秒にギャップを改善します。そして、各サブ問題に分岐することで、プロセスを継続できます。
分岐してバインドされた検索の優れた副作用は、プロセスが最初のLPモデルを改善できる切断面を特定できることです。これにより、より良いモデルから検索を再開する可能性があります。以下の表には、konbini40426のそのような繰り返し実行の結果が表示されます。「LPバウンド」列には、連続したブランチアンドバウンド検索を開始するために使用されるLPモデルによって与えられた値が表示されます。TSPは最終的に5回目の実行で解決され、合計113,651のサブ問題を使用しました。
| ラン | LPバウンド | B&Bバウンド | ギャップ | Subproblems | コア年 |
|---|---|---|---|---|---|
| 1 | 35569297 | 35578030 | 404 | 18301 | 1.9 | 2 | 35571235 | 35578286 | 148 | 119463 | 4.9 |
| 3 | 35573063 | 35578054 | 380 | 809 | 0.2 |
| 4 | 35573649 | 35578328 | 106 | 47915 | 11.8 |
| 5 | 35574032 | 35578434 | 最適な | 113651 | 23.4 |
| 6 | 35574287 | 35578246 | 188 | 871 | 1.9 |
| 7 | 35574350 | 35578199 | 235 | 1101 | 0.9 |
| 8 | 35574368 | — | — | — | — |
konbini40426を解決した後でも、私たちは3つの追加実行で問題を研究し続け、常により強力なLPバウンディングテクニックを探しました。
以下の画像は、konbini40426を解決するために使用される分岐バウンド検索（実行5）のスナップショットであり、それぞれが指定された日付の検索ツリーを示しています。ツリーのアクティブなノード（まだ処理されていないサブ問題を表すもの）は、赤またはマゼンタに着色されています。赤いノードは、分岐ステップの後、切断平面手順の追加ラウンドをまだ通過していないノードです。ノードの高さは、LP緩和の最適値を示します。
各画像の上部には、検索によって確立された下限とアクティブなサブ問題の数が表示されます。検索がより良い下限に進むにつれて、アクティブなノードの赤/マゼンタ線が画像をゆっくりと下ることに注意してください。
画像をクリックすると、高解像度バージョンが表示されます。
ツアーマップの図面は、Leafletモバイルフレンドリーなインタラクティブマップ用のオープンソースJavaScriptライブラリを使用して作成され、OpenStreetMap、Carto Basemaps、Stadia Mapsによって構築されたマップタイルを使用します。