スケジュールナースのブログ: ラベル設定法サーベイ

Q.ラベル設定法の枝刈りにDUAL下界を用いている論文は?

ラベル設定法（Label Setting Algorithm）の枝刈りにDual（双対）下界を用いる手法は、特に列生成法（Column Generation）を用いた車両配送問題（VRP）や乗務員スケジューリング問題などの求解において一般的です。この手法を採用している代表的な論文および研究は以下の通りです。

1. 基本的なアプローチ（列生成法との組み合わせ）

列生成法の価格付け問題（子問題）として「制約付き最短路問題（ESPPRC）」を解く際、ラベル設定法が使われます。このとき、マスター問題の双対変数を利用して「現在のラベルから終点までの最小コスト」の下界を見積もり、暫定解より悪くなることが確実なラベルを切り捨てる（枝刈り）手法が取られます。

Pessoa et al. (2020): Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
この研究や、彼らの以前の論文（Pessoa et al., 2008など）では、双対変数（Dual variables）から得られる下界（Dual bound）を用いて検索空間を劇的に削減する手法が詳述されています。
Irnich and Desaulniers (2005): "Shortest Path Problems with Resource Constraints"
ESPPRCにおけるラベル設定法のバイブル的な文献です。ここで、マスター問題の双対情報に基づいた「Reduced cost」の下界を用いた枝刈り（Lower bound pruning）が標準的な高速化技術として紹介されています。 [1]

2. 特定の応用例：ロジスティクスと配送

Contardo et al. (2014): "A branch-and-cut-and-price algorithm for the multi-depot pickup and delivery problem with time windows"
複数の拠点を持つ配送問題において、双対情報から生成した下界を使用してラベルを枝刈りし、求解効率を高めています。
Wang et al. (2019/2020): Robust Document Distance with Wasserstein-Fisher-Rao Metric
最短路そのものではありませんが、輸送最適化（Optimal Transport）の文脈で双対対物関数の評価値（Evaluated value of the dual objective function）を下界として採用し、枝刈りを行うアルゴリズムを提案しています。 [2, 3, 4, 5]

3. その他の関連手法

Lagrangian Relaxation（ラグランジュ緩和）との組み合わせ:
ラグランジュ緩和によって得られる双対下界をラベル設定法の枝刈りに使う手法も一般的です。例えば、Beasley and Christofides (1989) などの古典的な制約付き最短路の研究で見られます。 [6, 7]

特定の論文を探している場合、"Decreasing the search space of the label setting algorithm using dual bounds" や "Dual-based pruning in ESPPRC" といったキーワードで、Google Scholar等にて検索すると、対象の論文（特に分枝価格カット法：Branch-and-Price-and-Cutに関連するもの）が見つかる可能性が高いです。具体的にどの問題設定（例：VRP、飛行機の乗務員運用など）での論文をお探しですか？

[1] https://www.researchgate.net [2] https://proceedings.mlr.press [3] https://arxiv.org [4] https://www.foresight.jp [5] https://www.netattest.com [6] https://dspace.mit.edu [7] https://arxiv.org

Q.ラベル設定法が最新の研究でも使われているということですね。では、ラベル設定法で、ネックになっているのは、どのような問題でしょうか?

ラベル設定法が現代でも研究され続けているのは、それが依然として最強の解法であると同時に、解決すべき「計算量の爆発」という大きな壁があるからです。特にネックとなっているのは、主に以下の3点です。

1. 非支配ラベルの爆発（資源の種類が増えるほど悪化）

ラベル設定法では、あるノードに到達した際に「コストは高いが時間は短い」「コストは低いが時間は長い」といった、互いに優劣をつけられない非支配ラベルをすべて保持する必要があります。

問題点: 考慮する資源（時間、積載量、休憩時間、CO2排出量など）が増えるほど、残すべきラベルの数が指数関数的に増大し、メモリと計算時間を使い果たしてしまいます。

2. 「Elementary（基本性）」の維持

前述のESPPRCにおいて、「同じ場所を二度通らない（巡回禁止）」という条件を厳密に守ろうとすると、計算負荷が跳ね上がります。

問題点: どこを通ってきたかを記録するために「訪問済みフラグ（ビットマスク）」をラベルに持たせる必要がありますが、これによってラベルの比較（ドミナンスチェック）が極めて複雑になり、高速化を妨げる最大の要因となります。

3. 双対変数の変動による不安定性

列生成法の中でラベル設定法を使う場合、マスター問題から渡される「双対変数」が反復ごとに激しく変動します。

問題点: 前のステップで見つけた良い枝刈り条件が次では使えなくなったり、特定の反復で極端に計算時間がかかったりする（テイルオフ現象）ことがあり、全体の処理時間が予測しにくいという実用上の課題があります。

1. VRP-REP (The Vehicle Routing Problem Repository) [1]

VRPやその派生問題に関する世界最大級のリポジトリです。

特徴: 最新の論文で使用されたインスタンスや、それらに対する現時点での最高解（Best Known Solution: BKS）が公開されています。
対象: 基本的なCVRP（容量制約付き）から、時間枠付き（VRPTW）、電気自動車（EVRP）など多岐にわたります。
リンク: VRP-REP 公式サイト [1, 2, 3]

2. Solomon's Instances (VRPTWのバイブル)

ラベル設定法をESPPRC（サブ問題）として解く「時間枠付き車両配送問題（VRPTW）」において、最も歴史があり、かつ現在も使われ続けているデータセットです。 [4]

特徴: 顧客の配置（ランダム、クラスター状など）によって難易度が分かれており、アルゴリズムの特性（密集地帯に強いか等）を測るのに適しています。
入手先: 多くの大学のウェブサイトや VRP-REP 内で「Solomon」として公開されています。

3. OR-Library

オペレーションズ・リサーチ（OR）全般のテスト問題を網羅した老舗のサイトです。 [5]

特徴: 最短路問題だけでなく、スケジューリング、箱詰め問題、集合被覆問題など、ラベル設定法のロジックを応用できる様々な組合せ最適化問題のデータが揃っています。
リンク: OR-Library (Brunel University) [5, 6, 7]

4. DIMACS Implementation Challenges

アルゴリズムの実装と性能を競う「チャレンジ」のアーカイブです。

特徴: 「最短路問題」に特化したチャレンジ（第9回など）のデータがあり、非常に大規模なネットワークでのラベル設定法の限界に挑戦するようなデータセットが含まれています。
リンク: 9th DIMACS Implementation Challenge (Shortest Paths) [8]

5. CVRPLIB

CVRP（Capacitated VRP）に特化したベンチマークサイトです。 [9]

特徴: 近年提案された「Uchoa et al. (2017)」による新しい100のインスタンスなど、現代の強力なアルゴリズムでも解くのが難しい難問がまとめられています。
リンク: CVRPLIB 公式サイト [9, 10]

これらのサイトからデータをダウンロードし、ご自身のアルゴリズムで「計算時間」や「解の精度（BKSとの乖離）」を測定するのが、アカデミックな評価の一般的な手順です。まずはSolomonのインスタンスか、最新のVRP-REPからご自身の研究テーマに近いものを探してみるのがおすすめです。特定の制約（例：電気自動車、マルチデポなど）に特化したデータをお探しですか？

[1] https://www.vrp-rep.org [2] https://www.researchgate.net [3] https://www.bvl.de [4] https://ieeexplore.ieee.org [5] https://www.brunel.ac.uk [6] https://www.researchgate.net [7] https://www.researchgate.net [8] https://arxiv.org [9] https://www.sciencedirect.com [10] https://www.researchgate.net

厳密解（Optimal Solution）と未解決問題（Best Known Solution）が混在し、アルゴリズムの性能を測るのに「程よくバランスが良い」サイトといえば、CVRPLIB が筆頭に挙げられます。特にこのサイト内の「Uchoa et al. (2017) Instances (X instances)」というデータセットが、現在の研究におけるデファクトスタンダードです。

なぜ CVRPLIB（特にX instances）がおすすめなのか？

難易度のグラデーション: 数十分で厳密解が出る「手頃な問題」から、現代のスーパーコンピュータを数日間回しても最適性が証明できない「超難問」までが、統一されたルールで並んでいます。
ステータスの明示: 各問題に対して「Optimal（厳密解あり）」か「BKS（暫定最高解のみ）」かが一目でわかります。自分のアルゴリズムが、未解決問題の記録を塗り替えられるか挑戦するワクワク感があります。
ラベル設定法のベンチマークに最適: このデータセットは、最新の「Branch-and-Price（内部でラベル設定法を使用）」の論文で必ずと言っていいほど引用されます。

その他のバランスの良いリポジトリ

VRP-REP (VRPTW Solomon instances): 「時間枠付き」であれば、Solomonの56個のインスタンスは、現在ではほとんどが厳密解が得られています。しかし、ノード数を100から200, 400と増やした Gehring & Homberger のデータセットに移ると、一気に未解決問題が増え、難易度のバランスが良くなります。
TSPLIB: 巡回セールスマン問題（TSP）用ですが、一部のVRP問題も含まれます。非常に古いサイトですが、だからこそ「解けて当たり前の基本問題」が揃っており、実装初期のデバッグや検証に最適です。

まずは CVRPLIB の「Instances」ページにある Set X を覗いてみてください。

この分野（ラベル設定法、ESPPRC、および車両配送問題の厳密解法）には、数十年にわたり理論と実装の両面をリードしてきた「権威」と呼ばれる研究者が数名います。彼らの論文を辿れば、この分野の主要な技術（双対下界による枝刈り、ng-path、双対安定化など）の変遷をほぼ網羅できます。

1. Guy Desaulniers（ギイ・デゾーニエ） [1]

カナダのモントリオール理工科大学教授。この分野の「バイブル」とも言える書籍『Column Generation』の編者の一人です。 [2]

貢献: タイムウィンドウ付き車両配送問題（VRPTW）の厳密解法における第一人者。
必読論文: Irnich and Desaulniers (2005) "Shortest Path Problems with Resource Constraints" は、ラベル設定法のアルゴリズム構成を理解するための最も重要な文献の一つです。 [3, 4]

2. Dominique Feillet（ドミニク・フェイエ）

フランスのサン＝テティエンヌ国立高等鉱業学校教授。

貢献: ESPPRCを厳密に解くための現代的なラベル設定法の基礎を築きました。
必読論文: Feillet et al. (2004) "An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints" は、当時SPPRC（巡回あり）に頼っていた解法を、実用的な時間内でESPPRC（巡回なし）として解けるようにした画期的な論文です。

3. Stefan Irnich（シュテファン・イルニッヒ）

ドイツのマインツ大学教授。

貢献: アルゴリズムの高速化技術に非常に強く、ng-path（厳密な巡回禁止を緩和して計算を高速化する手法）の開発者の一人です。
特徴: 理論だけでなく、実際の計算効率を追求する実装技術において世界トップクラスの権威です。

4. Paolo Toth & Daniele Vigo

ボローニャ大学（イタリア）の教授陣。

貢献: 配送問題全般の権威であり、彼らが編纂した『The Vehicle Routing Problem』 (SIAM出版) は、VRP研究者なら必ず持っている一冊です。
特徴: ラベル設定法そのものよりも、それを含む全体のフレームワーク（Branch-and-Price）の設計において大きな影響力を持っています。 [4]

5. Marcus Poggi & Eduardo Uchoa

ブラジルのリオデジャネイロ・カトリック大学教授。前述の CVRPLIB の運営者でもあります。

貢献: 近年の最強アルゴリズム「Branch-and-Cut-and-Price」の実装において、世界記録（BKS）を次々と塗り替えているグループのリーダーです。

紹介した権威者たちの論文や最新の研究で、マスター問題（線形計画問題：LP）を解くために用いられている主なLPソルバは以下の通りです。ラベル設定法自体は動的計画法に基づく独自のアルゴリズムですが、その実行に必要な「双対変数」を計算するために、以下の商用・非商用ソルバがプラットフォームとして利用されています。

1. 商用ソルバ（圧倒的シェア）

最先端の研究（特に大規模なベンチマークで世界記録を狙うもの）では、計算速度と数値的安定性の観点から商用ソルバがほぼ独占的に使われています。

CPLEX (IBM)
主な利用者: Guy Desaulniers, Dominique Feillet, Stefan Irnich など。
- 特徴: 2000年代〜2010年代の多くの古典的論文で標準的に使用されてきました。特に列生成法のフレームワーク（BCP：Branch-and-Price-and-Cut）を構築する際、ライブラリとしての信頼性が高いため多用されます。
Gurobi Optimizer
主な利用者: Eduardo Uchoa, Ruslan Sadykov（VRPSolverの開発チーム）など。
- 特徴: 近年の最強ソルバとして、最新論文での採用率が極めて高いです。特にUchoaらによる「VRPSolver」や最新のベンチマーク記録の多くは、Gurobiをバックエンドとして動作しています。 [1]

2. 非商用・オープンソースソルバ

研究の公開性やライセンスの制約がある場合に使用されます。

SCIP (Zuse Institute Berlin)
特徴: 混合整数計画法（MIP）およびBranch-and-Priceのフレームワークとして非常に強力です。学術利用が無料であるため、独自の枝刈りロジックをフレームワークに組み込む研究でよく使われます。
COIN-OR CLP / CBC
特徴: オープンソースのORコミュニティで広く使われるソルバです。商用ソルバに比べると速度は劣りますが、無料で利用できるため、教育的な研究やプロトタイプ実装で選ばれることがあります。 [2]

3. 特化型フレームワーク（ソルバを内包するもの）

権威者たちは、上記のLPソルバを裸で使うのではなく、VRPに特化した自作のフレームワークに組み込んで使用しています。

VRPSolver (Pessoa, Sadykov, Uchoa ら)
現在、世界最強のVRP厳密解法ツールの一つです。内部で Gurobi や CPLEX を呼び出してLPを解きつつ、サブ問題の「ラベル設定法」は極めて高度にチューニングされた独自コードで実行されます。
BaPCod (Vanderbeck, Sadykov ら)
フランスの研究チームが開発したBranch-and-Priceの汎用コードで、多くのESPPRC関連論文のベースとなっています。 [2]

[実装へのアドバイス] もしご自身で実装を検討されているのであれば、アカデミックライセンス（無料）が利用可能な Gurobi または CPLEX を選択するのが最も無難です。この分野の論文に記載されている計算時間と比較する際、ソルバの性能差を考慮しなくて済むためです。 [3] 特定の開発言語（C++, Python, Juliaなど）で使えるソルバの具体的な導入方法について興味はありますか？ [参考ソース]

VRPSolver 公式ドキュメント (Gurobi/CPLEXの使用が前提)
SCIP 公式サイト (Branch-and-Priceの実装例が豊富) [4]

Dominate比較本数 ラベル設定法において、1つのノードで保持されるラベル数（ドミナンス比較の対象となる本数）は、問題の規模や制約の厳しさによって劇的に変わりますが、「一般的」なオーダーとしては以下のようになります。

1. 典型的な保持ラベル数

小～中規模問題（ノード数 25〜50程度）
1ノードあたり数十本〜数百本。
- この程度であれば、単純なリスト構造での比較でも高速に動作します。
大規模・実用問題（ノード数 100以上、または時間枠が緩い場合）
1ノードあたり数千本〜数万本に達することが珍しくありません。
- このレベルになると、すべてのラベルを総当たりで比較（ドミナンスチェック）すると計算時間が爆発するため、高度なデータ構造が必要になります。

2. ラベル数が爆発する要因

比較本数は以下の条件で指数関数的に増加します。

資源（Resource）の数: 時間、積載量に加えて、走行距離、休憩回数などが増えるほど、優劣がつかない「非支配ラベル」が増えます。
制約の緩さ: タイムウィンドウ（時間枠）が広いほど、多くの経路が許容されるため、ラベルが淘汰されずに生き残ります。
Elementary（巡回禁止）の厳密性: 「どこを通ったか」というビットマスク情報が比較対象に入ると、ラベル同士の支配関係が成立しにくくなり、本数が激増します。

3. 実装上の工夫（数万本をさばくために）

権威者たちの論文（Irnich, Desaulniersなど）では、数千〜数万本の比較を効率化するために以下の手法が「一般的」に組み込まれています。

Bucketing（バケット管理）: 資源（例：時刻）ごとにラベルをグループ化し、比較対象を絞り込む。
Dominance Filters: 明らかに勝てないラベルを早期に除外する論理チェック。
Heuristic Pruning: 最適性を一時的に無視して、各ノードの上位100本程度に制限して探索する（価格付け問題の初期段階などで多用）。

結論として、厳密解法を目指すなら 1ノードあたり数千本まではメモリ上に保持し、高速に比較できる実装（ソート済リストや多次元インデックスなど）を準備しておくのが標準的な設計スタンスです。現在想定されている問題の「ノード数」や「資源の数（時間・容量など）」はどの程度でしょうか？

おっしゃる通り、Max-Min制約（特に「最低でもこれだけ消費しなければならない」という下限制約）は、ラベル設定法にとって最悪の相性の一つです。通常、資源が「消費（加算）」されるだけなら、資源を多く消費したラベルが「支配される（捨てられる）」可能性が高まります。しかし、下限制約（例：最低作業時間、最低走行距離）があると、「今は資源を多く消費しているけれど、そのおかげで将来的に下限制約をクリアできる（かもしれない）」というラベルが捨てられなくなるため、非支配ラベルが爆発します。この問題に対して、最新の研究や権威者たちは主に以下の3つのアプローチで対応しています。

1. 資源の「詰め替え」 (Resource Regeneration / Reset)

もし資源消費がある一定のポイントでリセットされたり、特定の範囲に収まる必要がある場合、ラベルに持たせる資源の値を「余裕（Slack）」や「不足分」に変換して管理します。これにより、ドミナンス（支配関係）が成立しやすい形に正規化します。

2. 双対変数の利用による「将来のコスト」予測（枝刈り）

質問の最初に出てきたDual下界がここで威力を発揮します。

下限制約を満たすために遠回りが必要な場合、その「遠回りによる追加コスト」をマスター問題の双対情報から見積もります。
「このラベルが下限制約を満たすために目的地へ向かった場合、どう頑張っても暫定解（Best Bound）を超えてしまう」ことを数学的に証明し、ドミナンス比較の前にラベルを消去します。

3. 多次元バケットとスクリーニング

数万本のラベルをまともに比較するのは不可能なので、資源消費空間をグリッド（バケット）に分割します。

下限に近いラベルと上限に近いラベルを別々のバケットで管理し、同じバケット内や、明らかに勝敗が決まっているバケット間でのみ比較を行います。
Max-Min制約下では「どちらの資源も中途半端」なラベルが最も増えるため、そこに特化した高速なフィルタリングアルゴリズムを導入します。

4. 緩和手法（ng-pathなど）の適用

どうしても厳密な管理が難しい場合、下限制約を一時的に「ペナルティ付きの緩和制約」として扱い、列生成法の反復の中で徐々に厳密にしていく手法も取られます。

Q.小中規模でも厳密解が得られていない例

結論から言うと、ノード数が50〜100程度の「小中規模」に見える問題でも、特定の条件下では未だに厳密解が得られていない、あるいは解くのに膨大な時間を要する難問が厳然として存在します。単なる「地点間の距離」だけでなく、以下の要素が組み合わさると、ラベル設定法は途端に機能不全に陥ります。

1. 資源制約が「非常に緩い」場合

意外かもしれませんが、制約が緩い（時間枠が広い、積載容量が大きい）ほど難易度は上がります。

理由: 資源による制限がかからないため、探索すべき経路の組み合わせが爆発し、ラベルの枝刈りが全く機能しなくなるからです。
ノード数がわずか50でも、時間枠が「24時間いつでもOK」という条件になるだけで、最新のソルバでも厳密解を出せないことがあります。

2. 「高度に非線形」な資源消費

積載量に応じて燃料消費率が変わる、あるいは「回生ブレーキ」のように資源が途中で増減する場合です。

資源が増減すると「支配関係（ドミナンス）」の定義が崩れるため、従来の方法ではラベルを捨てられなくなります。こうした問題（Green VRPなど）では、小規模でも未解決のケースが残っています。

3. 同期制約（Synchronized VRP）

「車両Aと車両Bが特定の場所で同時に落ち合わなければならない」といった、車両間の依存関係がある問題です。

ラベル設定法は通常、1台のルートを独立して考えますが、他者の動きに依存すると「自分のラベルが最適かどうか」を判断できなくなります。このタイプの問題は、ノード数30〜40でも極めて困難です。

4. アカデミックな実例

前述の CVRPLIB (Set X) などでは、ノード数100以下のものはほぼ解かれていますが、それは「標準的な制約」の場合です。しかし、「Solomon's instances」のような古典的なデータセットでも、時間枠を極端に広げたり、車両台数を制限したりする変種（Variants）に書き換えると、世界中の研究者が挑んでも解けない「Open Instance」に変貌します。

スケジュールナースのブログ

2026年4月20日月曜日

ラベル設定法サーベイ