技術的概要：LLM 支援型柔軟 MCTS による大規模 CVRP ソルバー設計の自動化

問題定義

容量制約付き車両経路問題（CVRP）はサプライチェーン最適化の要であるが、数百から数千のノードを含む大規模 CVRP（LSCVRP）インスタンスの解決は依然として重大な課題である。問題の NP 困難性により、探索空間はインスタンスサイズとともに指数関数的に拡大し、最先端のソルバーさえも大規模データにおける性能面で苦戦を強いられている。

「分割統治」戦略、すなわちグローバルな問題を管理可能な部分問題に分解するアプローチは有効なパラダイムであるが、その実用的な応用は以下の 2 つの主要な障壁によって阻害されている：

1. 専門知識への依存性: 効果的な分解ロジックの設計とサブソルバーパラメータの較正には多大な労力を要し、ドメイン専門知識に強く依存する。
2. 現在の LLM 支援型アルゴリズム設計（LLMaAD）の限界: 既存の LLM 駆動アプローチは、通常、単一の「思考からコードへ」という単一モジュールなパラダイムに依存している。これらの手法は、限られたコンテキストウィンドウ内で LSCVRP に必要な高度で多コンポーネントなアーキテクチャを生成することに苦戦する。さらに、大規模インスタンスにおける候補ソルバーの評価に伴う莫大な計算コストがボトルネックとなり、アルゴリズム仮説空間内での探索を制限している。

手法：LaF-MCTS

これらの課題に対処するため、著者は高パフォーマンスな LSCVRP ソルバーの設計を自動化するフレームワークであるLaF-MCTS（LLM 支援型柔軟モンテカルロ木探索）を提案する。本手法は、最適なソルバー構成の探索を行う開発段階と、発見された最良のソルバーを適用する展開段階の 2 つの段階で運用される。

1. 3 段階の意思決定階層

LLM に単一のプロンプトからソルバー全体を生成させるのではなく、LaF-MCTS は分解型ハイブリッド遺伝的探索（HGS）に触発された階層的アプローチを採用する。この階層は探索空間を 3 つのレベルに構造化する：

• レベル 1（全体フレームワーク設計）: LLM はグローバルなアルゴリズムアーキテクチャを合成し、メタヒューリスティックの骨格、分解粒度（部分問題のサイズ/数量）、および実行フロー（例：進化サイクル、再統合メカニズム）を定義する。
• レベル 2（分解戦略設計）: フレームワークを条件として、LLM は大規模グラフを部分問題に分割するコードを生成する。LLM の専門ドメイン知識の欠如を克服するため、このレベルでは 11 の確立された CVRP 分解コードからなる専門ライブラリを用いた数ショットプロンプティング戦略を採用し、生成された戦略が厳格なドメイン制約（例：部分問題の均質性）を満たすことを保証する。
• レベル 3（サブソルバー構成）: 最下位レベルは局所適応に焦点を当てる。LLM はハイパーヒューリスティックチューナーとして機能し、各分割の特定のトポロジーと規模に合わせて、HGS ベースのサブソルバー用のパラメータセットを生成する。

2. 柔軟モンテカルロ木探索（MCTS）

本フレームワークは、ソルバーコンポーネントの組み合わせ空間をナビゲートするためにトポロジーに柔軟な MCTS を利用する。探索プロセスは以下の通りである：

• 選択: 探索と利用のバランスを取るために、木への適用上限信頼区間（UCT）を使用する。
• 拡張: LLM は次のレベルに対して $K$ 個の候補コードコンポーネントを生成する。
• 評価: ロールアウト戦略により、選択されたパスから完全なソルバーを構成し、固定されたトレーニングインスタンスのセット上で評価する。報酬は、既知の最良解（BKS）に対する平均ギャップとして定義される。
• バックプロパゲーション: 報酬を木の上流に伝播させ、訪問回数と価値推定値を更新する。

3. 意味的プルーニングと分岐再生

LaF-MCTS の重要な革新は、コードの冗長性を処理し多様性を維持するメカニズムであり、LLM が構文は異なるが意味的に同等なコード（またはその逆）を生成するという問題に対処する。

• 意味的プルーニング: 冗長な評価を回避するため、システムは**単語および文構造ムーバー距離（WSMD）**を採用する。この指標は以下の 2 つを組み合わせる：
  • 意味的埋め込み整合: トークン埋め込みに対する単語ムーバー距離（WMD）の使用。
  • 構造的トポロジー一致: 制御およびデータフロー依存関係を捉えるために、自己注意行列（SAM）に対するグロモフ・ワッサーシュタイン距離の使用。
    2 つのコード分岐間の複合距離が閾値を下回る場合、劣るバリアントはプルーニングされる。
• 分岐再生: プルーニングにより探索空間が狭くなりすぎるのを防ぐため、システムは分岐再生をトリガーする。ノードがプルーニングされた際、LLM には負の制約を付与して、保持されたノードと論理的かつ構造的に区別される新しい候補を生成させることで、探索の多様性を維持する。

主要な貢献

1. 新規フレームワーク: 3 段階の階層を通じて人間の専門家による構築を模倣し、分解強化型ソルバーの設計を自動化する LaF-MCTS の導入。
2. 階層的探索空間: フレームワーク、分解、サブソルバーというプラグアンドプレイ型のアルゴリズムテンプレートの提案。これにより、LLM は制約されつつも表現力豊かな構造内で専門コンポーネントを生成でき、単一モジュールなコード生成の限界を克服する。
3. 効率的な探索メカニズム: 意味的プルーニング（WSMD 経由）と分岐再生メカニズムの開発。これらの技術は、冗長な評価に伴う計算ボトルネックを効果的に削減しつつ、探索が局所最適解に停滞しないことを保証する。
4. 最先端のパフォーマンス: LaF-MCTS が既存のメタヒューリスティック、ニューラル組合せ最適化（NCO）手法、および他の LLMaAD アプローチを上回るソルバーを自律的に構成できることの証明。

実験結果

著者は、ノード数が $N=100$ から $N=1000$ の範囲にわたる 100 インスタンスを網羅するCVRPLibベンチマーク上で LaF-MCTS を評価した。

• 性能: LaF-MCTS は、OR-Tools、HGS、HGS+BS、各種 NCO モデル（例：RF-POMO、CaDA）、および他の LLMaAD 手法（例：FunSearch、ReEvo、EoH）を含むベースラインと比較して、すべての問題スケールにおいて最低の平均目的関数値と最適性ギャップを達成した。
• HGS+BS との比較: 分解ベースのメタヒューリスティックである HGS+BS は標準的な HGS を上回ったが、LaF-MCTS は人間の介入なしに HGS+BS を凌駕する分解ベースのソルバーを生成し、$[100, 200)$ ノードスケールで平均最適性ギャップ0.05%、$[800, 1000]$ スケールで**1.39%**を達成した。
• アブレーション研究:
  • 階層性: 完全に統合された 3 段階バリアントは、部分的なバリアント（例：フレームワークのみ、または分解のみ）を一貫して上回り、完全な階層の必要性を検証した。
  • 共同最適化: 分解戦略とパラメータを共同で最適化することは、いずれかを固定するよりも良い結果をもたらした。パラメータ調整は分解戦略に決定的に依存していることが示された。
  • プルーニング/再生: 意味的プルーニングまたは分岐再生のいずれかを除去すると性能が低下し、効率と多様性のバランスにおけるそれらの役割が確認された。
  • WSMD コンポーネント: プルーニング指標の意味的（埋め込み）および構造的（トポロジー）の両方のコンポーネントが、効果的な冗長性検出に必要であることが判明した。

意義と主張

本論文は、LaF-MCTS が複雑な組合せ最適化問題における自動化アルゴリズム設計において重要な前進を表すと主張している。LLM の推論能力と古典的アルゴリズムの実行速度の間のギャップを埋めることで、このフレームワークは、大規模ルーティング問題における LLMaAD を過去に制限してきた構造的複雑性と評価コストの障壁を成功裡に克服した。

著者は、自らのアプローチが単純な構築ヒューリスティックを超えて、複雑で多コンポーネントなアーキテクチャを発見するものだと強調している。その結果得られたソルバーは、最先端の人間設計メタヒューリスティック（HGS+BS など）およびニューラルアプローチの性能に匹敵するだけでなく、それを上回る。この研究は、手動最適化がますます困難になっている分野において、高度なソルバーの設計を自動化するための viable な経路として、階層的かつプルーニング強化型の探索が有効であることを示唆している。

注：著者は、アーキテクチャの多様性を制限する専門家定義の HGS ワークフローへの依存という現在の限界を認識しており、完全自律的なワークフローの進化の実現と、一般化の向上のための分解ポートフォリオの生成を今後の課題として特定している。