Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

この論文は、古典的なベンチマークインスタンスの構造を突くことで極めて短時間で最適解が得られることを示し、これらのインスタンスが現在では TSPTW-M 問題の評価基準として適切でなくなったと結論付けています。

要約

この論文は、物流や配送ルート計画の分野で使われる「古典的なテスト問題」が、実は**「あまりにも簡単すぎて、最新の技術の真の実力を測るのに不向き」**だと指摘する、非常に重要な警告メッセージです。

まるで**「小学生向けの算数ドリルで、東大の数学教授の能力を測ろうとしている」**ような状況に似ています。

以下に、この論文の核心をわかりやすい比喩を使って解説します。

---

🚚 物語：配送ドライバーと「魔法の地図」

想像してください。ある配送会社が、100 軒の顧客を回る最速のルートを探そうとしています。
それぞれの顧客には「到着していい時間（タイムウィンドウ）」が決まっています。例えば、「午前 10 時から 11 時の間に届けてね」といった具合です。

この問題を解くための「古典的なテスト問題（ベンチマーク）」は、過去 40 年以上にわたって使われてきました。多くの研究者や AI（機械学習）が、このテストで良い成績を収めれば「すごいアルゴリズムだ！」と評価されてきました。

しかし、この論文の著者（フランシスコ・ソリニャック氏）は、**「待ってください！そのテスト問題には『罠』があります」**と言います。

1. 罠とは何か？「狭すぎる道」

古典的なテスト問題の多くは、顧客への到着時間が**「非常に狭い範囲」**に設定されています。

• 例： 「10 時 00 分〜10 時 05 分の間に到着しなさい」

これは、ドライバーにとって**「道が非常に狭く、迷う余地がない」**状態です。

• 狭い道（古典的テスト）： 道が細すぎて、曲がりようがありません。だから、どんなに単純なドライバー（単純なアルゴリズム）でも、迷わずに最短ルートを発見できてしまいます。
• 広い道（現実や新しいテスト）： 道が広く、選択肢がたくさんあります。「10 時〜12 時の間ならどこでも OK」など。ここでは、どの道を選ぶかで難易度が劇的に変わります。

2. 著者の発見：「単純な魔法」が通用してしまった

著者は、**「逆方向から考える」という、とても単純な方法（アルゴリズム）**を開発しました。

• 通常の考え方： 出発点から順に「次にどこへ行こう？」と考える。
• 著者の方法： 目的地（倉庫）から逆算して「いつ出発すれば間に合う？」と考える。

この単純な方法を、50 軒以上の顧客がいる古典的なテスト問題にかけると、なんと**「10 秒未満」で全てを解いてしまいました！
さらに驚くべきことに、この単純な方法を「前処理（下準備）」として使うだけで、他の複雑なアルゴリズムも、古典的なテスト問題では「驚異的な成績」**を収めてしまうのです。

これはつまり、「狭い道」なら、どんなに単純な車でも F1 レースカーと同じ速さで走れてしまうということです。

3. 何が問題なのか？「本物の実力が測れない」

ここで大きな問題が起きます。

• 現状： 「このアルゴリズムは、古典的なテストで 10 秒で解けた！すごい！」と評価される。
• 現実： でも、そのアルゴリズムは**「道が広い（時間制限が緩い）」**現実の配送問題では、全く役に立たないかもしれない。

著者の単純なアルゴリズムは、**「時間制限が緩い（道が広い）」問題になると、逆に「全く解けなくなる」ことがわかりました。
つまり、古典的なテストは「AI やアルゴリズムが本当に賢いのか、それともただの『狭い道』に慣れただけなのか」を見分けることができない、「甘すぎるテスト」**だったのです。

4. 機械学習への警告

最近、配送ルートを最適化するのに**「機械学習（AI）」**が使われています。
多くの AI は、この「古典的なテスト問題」を使って訓練されています。

• 危険性： AI が「狭い道」の解き方だけを覚えてしまい、「広い道（現実世界）」では全く動けなくなる可能性があります。
• 比喩： 狭い廊下だけを練習して「迷路マスター」になった子供に、広い森の迷路を解かせたら、途方に暮れてしまうようなものです。

📝 まとめ：この論文が言いたいこと

1. 古典的なテストは「古すぎる」： 50 軒以上の顧客がいる古典的なテスト問題は、もはや最新のアルゴリズムの性能を測る基準としては使えません。それらは「簡単すぎる」からです。
2. 単純な方法でも勝てる： 複雑な最新技術を使わなくても、単純な方法で簡単に解けてしまうため、「すごい成果！」と勘違いしやすいです。
3. 新しい基準が必要： 研究者や AI 開発者は、**「時間制限が緩い（道が広い）」**ような、もっと難しいテスト問題を使う必要があります。
4. 現実への適用： 現実の配送では、時間制限が厳しすぎたり緩すぎたりと様々です。AI を作るなら、**「様々な難易度の道」**で訓練させなければ、本物の現場では使えません。

一言で言えば：
「これまでのテストは『子供向けのパズル』でした。本物のプロ（AI やアルゴリズム）を評価するには、もっと『大人向けで複雑なパズル』を用意しないと、本当の実力がわからないよ！」という警鐘です。

技術概要

論文要約：時間制約付き巡回セールスマン問題（TSPTW）の古典的ベンチマークインスタンスへの警告

Francisco J. Soulignac 氏によるこの論文は、時間制約付き巡回セールスマン問題（TSPTW）の分野において、長年使用されてきた「古典的ベンチマークインスタンス」が、特に大規模な顧客数（50 以上）を持つ場合、アルゴリズムの性能評価においてもはや適切ではない可能性を指摘しています。

以下に、問題定義、手法、主要な貢献、実験結果、およびその意義について詳細にまとめます。

1. 問題定義 (Problem Statement)

本研究は、以下の 3 つの TSPTW 変種を対象としています。

1. TSPTW-M (Makespan objective): 車両がデポを出発し、全顧客を訪問して戻ってくるまでの完了時間の最小化。
2. TSPTW-D (Duration objective): 出発から帰着までの総所要時間（待ち時間を除く移動時間を含むが、顧客での待ち時間は含まない定義による）の最小化。
3. TSPTW-TT (Total Travel Time): 移動に費やされた時間のみを考慮し、待ち時間を無視した総移動時間の最小化。

背景:
TSPTW の研究は 40 年以上の歴史があり、多くの厳密解法やヒューリスティック手法が開発されてきました。しかし、これらのアルゴリズムの性能評価は、López-Ibáñez と Blum (2023) によって編纂された「古典的ベンチマークインスタンス」のサブセットに依存している傾向があります。近年、機械学習ベースのソルバーも同様の生成プロセスを用いて「難しい」訓練データセットを作成していますが、これらのデータセットの構造が実際の難易度を反映していない可能性が指摘され始めています。

2. 提案手法 (Methodology)

著者は、TSPTW-M および TSPTW-D を解くための単純かつ厳密な手法を提案しました。

2.1 TSPTW-M 用ソルバー (Algorithm 2)

• 基本アルゴリズム: 後方方向（デポから顧客へではなく、最終顧客からデポへ）への**最良優先探索（Best-First Search）**に基づいています。
• 探索戦略:
  • 部分経路を逆順に構築し、デポへの到着時刻が早期になるように優先度付けを行います。
  • 支配関係（Dominance）の剪定: 部分経路 $R$ が、同じ頂点集合を訪問する別の経路 $Q$ によって「$ub$-支配」されている場合（$Q$ の方が遅く出発しても早く到着できる、または同じ到着時間でより遅く出発できる場合）、$R$ の拡張を破棄します。
  • 到達不能関数 (Unreachable Function): 事前計算により、特定の時刻に特定の頂点に到達した場合に、その後に訪問不可能な頂点の集合を特定し、探索木を剪定します。
• 特徴: 非常に単純な構造ですが、古典的ベンチマークの大規模インスタンスに対して驚異的な速度を発揮します。

2.2 TSPTW-D 用ソルバー (Algorithm 3)

• アプローチ: TSPTW-D は、TSPTW-M を出発時刻 $t$ ごとに繰り返し解くことで解決できます（整数時間の場合）。
• スライディングウィンドウ: 全時刻範囲を網羅的に解くのではなく、既存の最良解（スライドウィンドウ）に基づいて探索範囲を絞り込み、局所探索（スワップ、2-opt、シフト）を併用して効率化を図っています。

3. 主要な貢献と発見 (Key Contributions & Findings)

3.1 古典的ベンチマークの限界

• 驚異的な解読速度: 提案した単純なアルゴリズムは、顧客数が 50 以上の古典的ベンチマークインスタンス（Asc, DaS, Gen, Ohl, Lan, Dum, Pes, Pot など）のすべてを 10 秒未満で解くことができました。
• TSPTW-D への適用: 同様に、TSPTW-D についても、最大 30 分以内で（多くの場合数秒）、Lera-Romero et al. (2022) などが未解決だった 14 件を含む、50 人以上の顧客を持つ全インスタンスを解くことができました。
• 構造の偏り: これらのインスタンスは、時間窓（Time Windows）が「狭い（tight）」ように設計されており、探索空間が構造的に制限されているため、単純な探索手法でも容易に最適解に到達してしまいます。

3.2 逆転する性能評価

• 狭い時間窓 vs 広い時間窓: 提案アルゴリズムは狭い時間窓を持つインスタンスでは最強ですが、時間窓が広い（loose）インスタンス（例：Fontaine (2024) や Rifki et al. (2020) によるベンチマーク）では、他の最先端手法（Ler22, Rud23 など）に比べて最も性能が劣ることが示されました。
• 機械学習データへの警告: 多くの機械学習ベースの TSPTW ソルバーは、Lan, Dum, Gen, Ohl, DaS と同様の生成プロセス（狭い時間窓）を用いて訓練データを生成しています。これにより、モデルは「狭い時間窓の構造」に過剰適合（Overfitting）しており、実際の複雑な問題や時間窓が広い問題に対しては汎化性能が低い可能性があります。

4. 実験結果 (Computational Results)

• 環境: AMD Ryzen 7 3700U CPU、シングルスレッド、5GB RAM。
• TSPTW-M 結果:
  • 古典的ベンチマーク（50 顧客以上）: 全件 10 秒未満で解決。
  • 小規模インスタンス（50 顧客未満）: 7 件で失敗（メモリ不足）。
  • 広い時間窓（Rifki ベンチマーク）: 時間窓が緩い（$\beta=0, 25$）場合、他の手法に比べて著しく遅く、メモリ限界に達する。
• TSPTW-D 結果:
  • 古典的ベンチマーク（50 顧客以上）: 全件 30 分以内で解決（多くは数秒）。
  • これまでの研究で未解決だったインスタンスもすべて解決。

5. 意義と結論 (Significance & Conclusion)

5.1 ベンチマークの再評価

現在の古典的ベンチマーク（特に 50 顧客以上のもの）は、TSPTW-M および TSPTW-D の評価ツールとして単独では使用すべきではないと結論付けています。これらのインスタンスは、単純な探索手法でも容易に解けてしまうため、アルゴリズムの真の能力（特に時間窓が広い現実的なシナリオでの能力）を測る指標として不適切です。

5.2 今後の研究方向

• 新しいベンチマークの必要性: 時間窓の厳しさ（tightness）をパラメータ $\beta$ で制御し、難易度を変化させたインスタンス（Fontaine, 2024; Rifki & Solnon, 2025 のアプローチ）を組み合わせる必要があります。
• 機械学習への示唆: 機械学習アルゴリズムの訓練データセットを設計する際、単純な時間窓生成プロセスに依存せず、多様な難易度（特に広い時間窓）を含めるべきです。さもなければ、過剰適合した「見かけ上の高性能」なソルバーが生まれる危険性があります。
• 実世界との乖離: 古典的ベンチマークが現実世界の複雑な問題（特に時間制約が緩い場合や、動的な環境）を本当に代表しているかどうかは疑問です。

総括:
この論文は、TSPTW 研究コミュニティに対して、既存のベンチマークが「解きやすい」構造を持っていることを警告し、より厳格で多様な評価基準の導入を促す重要な提言となっています。単純なアルゴリズムですら古典的ベンチマークを瞬時に解いてしまう事実は、現在の評価基準の見直しを迫るものです。