経路計画における DRL と OR アルゴリズム: 比較と展望

1. 運用最適化とは何ですか?

オペレーションズ・リサーチは、数学、コンピューターサイエンス、経営学の学際的な分野であり、第一次世界大戦の防空戦闘システムに端を発しています。中国には銭学森氏によって導入され、当初は航空・軍事産業やその他の分野の最適化に使用されました。現在では、企業の生産、運営、物流の分野で広く利用されており、アルゴリズムを通じて人間の管理者の意思決定を導き、支援しています。このブログでは、オペレーションズリサーチの最適化を、制約を満たしながら何かを完了するためのコストを最小限に抑える最適化問題を解決することとして要約します。最適化問題は、多くの場合、数学的プログラミング問題として説明されます。決定変数が連続か離散かに応じて、連続最適化問題と組み合わせ最適化の 2 つのカテゴリに分類できます。

連続最適化問題の標準形式は次のとおりです。

ここで、x は決定変数、f(x) は目的関数、g(x) は不等式制約、h(x) は等式制約、m=p=0 です。 m=p=0 の場合、問題は制約のない最適化問題に変換されます。関数 f、g、h は線形または非線形です。従来の解法アルゴリズムには、ニュートン法、勾配降下法、共役法などがあります。

決定変数が整数（または部分的に整数）である場合、それは離散最適化問題であり、組み合わせ最適化とも呼ばれ、オペレーションズリサーチの重要な分野です。その標準形式は次のとおりです。

これは一般に混合整数計画法 (MIP) として説明され、すべてのパラメーター (cj、dk、aij、gik、bi) は任意の実数であり、線形式のみが考慮されます。 $$m$$ は制約の数、 $$n$$ は連続変数の数、 $$p$$ は整数変数の数です。 n=0の場合、上記のMIPは純粋な整数計画問題に変換されます。 $$p=0$$の場合、上記のMIPは線形計画問題に変換されます。特に、yk∈{0, 1}、全称量指定子kの場合、2進計画問題に変換されます。組み合わせ最適化問題（リソーススケジューリング、生産スケジューリング、パス最適化、操作スケジューリングなど）は、企業の経営判断で直面する最も一般的なタイプの最適化問題です。ビジネス上の意思決定の最適化のプロセスのほとんどをカバーしているため、オペレーションズリサーチの主な研究対象の 1 つです。フライトや工場のスケジュール、金融資産の割り当て、倉庫での商品の保管から輸送ルートの設計まで、多くのことが組み合わせ最適化問題としてモデル化できます。この論文の対象は組合せ最適化問題である。

2. 一般的な組み合わせ最適化問題とその解決法

組み合わせ最適化問題の離散的な性質により、問題のサイズに応じて解決空間が指数関数的に増加し、その多くが NP 完全となるため、問題解決に特別な課題が生じます。言い換えれば、現在、多項式時間計算量を持つアルゴリズムは存在しないということです。古典的な満足度 (SAT) 問題、最小頂点カバー (MVC) 問題、最大カット (MC) 問題など、NP 完全問題は数多くあります。これらは多項式複雑度の範囲内で互いに縮減できます。つまり、そのうちの 1 つに多項式複雑度ソリューションがあることが証明された場合、それらすべてに多項式複雑度ソリューションがあることになります。

2.1 一般的な組み合わせ最適化問題

最も古典的な NP 完全問題の 1 つは巡回セールスマン問題 (TSP) であり、これは配車ルート問題 (VRP) の特殊なケースです。その魅力は、説明が簡単そうで日常生活でよく使われるかもしれないという事実にあるかもしれませんが、普遍的で効率的な解決策を見つけるのは非常に困難です。実行可能な解は、すべての点の完全な順列です。点の数が増えると、組み合わせ爆発が発生し、ブルートフォースソリューションの複雑さは O(n!) になります。この問題は、n 個の都市から成り、任意の 2 つの都市間のコストが整数である完全グラフとして記述されます。すべての都市を訪問し、各都市を 1 回だけ訪問して、最後に出発点 (つまり、ハミルトン回路) に戻る必要がある巡回セールスマンがいます。すべての都市を訪問するパスの順序を見つけ、パスのコストの合計が最小になるようにします。

多くの場合、中規模から大規模の TSP では、最適なソリューションを見つけるための効果的なアルゴリズムはありません。見つけられる最善のソリューションと真の最適なソリューションの間の距離は、最適性ギャップと呼ばれます。これは、多くの TSP アルゴリズムを評価するための重要な指標でもあり、そのソリューションが最適ソリューションにどれだけ近いかを示すために使用されます。この問題は、提案されてから数十年にわたって、組み合わせ最適化の分野で繰り返し研究され、正確なアルゴリズム、近似アルゴリズム、ヒューリスティックアルゴリズムに基づくいくつかの成熟した方法が登場しました。 TSP 問題は、輸送、回路基板の設計、物流と流通、その他のシナリオで幅広く応用されています。

組み合わせ最適化におけるもう 1 つの典型的な問題は、車両経路問題 (VRP) です。これは、一定数の顧客がいて、それぞれ必要な商品の数量が異なり、商品が倉庫から顧客に提供され、車両群によって配送されるという問題を表します。顧客のニーズを満たし、一定の制約（時間枠、積載率）下で最短距離、最低コスト、最短時間などの目標を達成することを目的として、適切な配車計画と運転ルートを編成する必要があります。以下に、16 人の顧客 (番号 1 ～ 16) と 1 つの倉庫 (番号 0) がある簡単な図を示します。配達を完了するには合計 4 台の車両が必要です (異なる色でマークされています)。各車両は 4 人の顧客にサービスを提供します。すべての車両は倉庫から出発し、すべての顧客にサービスを提供した後、倉庫に戻ります。

問題の特性に応じて、さまざまな制約を追加して、次の図に示すように、さまざまな VRP 問題のバリエーションを取得できます。 TSP は VRP の特殊なケースであり、車両の制約を考慮せず、1 台の車両を使用してすべての顧客にサービスを提供します。車両に定員（積載制限）がある場合はCVRPとなり、時間枠（Time Window）を考慮するとVRPTWとなり、集荷と配達が同時に行われる場合（Pickup and Delivery）はVRPPDとなります。一般的な都市の配送問題は CVRP として記述でき、一般的な予約インストール問題は VRPTW として抽象化でき、食品配達やタクシー配車などの O2O 関連の問題は VRPPD で記述できます。そのため、VRP は物流と流通において幅広い応用シナリオを持ち、過去 50 年間にわたり研究のホットスポットとなってきました。従来の最適化手法（ヒューリスティック、正確なアルゴリズムなど）は、さまざまな問題のバリエーションを研究することに重点を置いており、不確実性、堅牢性、確率的、2階層などのシナリオにまで拡張されています。一方、深層強化学習手法は、主にTSPやCVRPなどの単純な状況を解決することに重点を置いており、最適化手法によって得られたソリューションを比較対象として使用することがよくあります。これについては以下で詳しく説明します。

2.2 組合せ最適化問題の一般的な解法

2.2.1 近似アルゴリズム

このタイプのアルゴリズムは、最適なソリューションではなく、次善のソリューション、または最適に近いソリューションを探します。その利点は、ある程度の最適性が保証されることです。具体的には、最悪の場合に与えられた解が、近似比と呼ばれる特定の倍数だけ最適解より劣っていないことを保証できます。 NP 完全問題の場合、最適解を見つけるための多項式複雑度のアルゴリズムはありませんが、最適解に近いものを見つけるための多項式複雑度のアルゴリズムは多数あります。このタイプの方法には、貪欲アルゴリズム、主双対法、動的計画法などが含まれます。

最小化組合せ最適化問題の場合、全体最適解の目的関数が 100 であると仮定すると、近似比 2 の近似アルゴリズムによって得られる解は [100, 200] の範囲内にある必要があり、最悪のケースは 200 になります。 TSP問題の場合、三角不等式が満たされると、クリストフィードアルゴリズムは最小全域木と最小重み完全マッチングを計算することでこれを解決します。その時間計算量はO(n3)で、近似率は1.5です。

2.2.2 ヒューリスティックアルゴリズム

ヒューリスティックアルゴリズムとは、経験と実験分析からの帰納的推論、つまり何らかの直感的な判断や試行方法を利用して問題を解決する方法を指します。本質的には、これも近似解を見つけることですが、上記の近似アルゴリズムと比較すると、ヒューリスティックアルゴリズムには最適性の理論的な保証がなく、つまり、解の品質を保証できないという違いがあります。しかし、一般的には、上記の近似アルゴリズムよりも優れたソリューションを見つけることができます。それは次の2つのカテゴリーに分けられます。

1 つは、最近傍法や最小全域木など、問題に関連するヒューリスティックに基づいてソリューションを構築するタイプです。もう 1 つは、ヒューリスティックに基づいて中間ソリューションをローカルに変更し、ソリューション空間内で反復的に検索するローカル検索です。このタイプのアルゴリズムは通常、問題指向、つまり問題固有です。一般的なフレームワークはなく、通常、問題ごとに異なるヒューリスティックアルゴリズムが設計され、ローカル最適性を迅速に探すことに重点を置いています。

もう一つのカテゴリーは、メタヒューリスティック検索フレームワークの応用です。よく知られているものとしては、タブー検索アルゴリズム、シミュレーテッドアニーリングアルゴリズム、遺伝的アルゴリズム、アリコロニー最適化アルゴリズム、粒子群最適化アルゴリズム、人工魚群アルゴリズム、人工蜂コロニーアルゴリズムなどがあります。これらは生物の行動や物質の運動形態に基づいており、社会性昆虫の集団行動の研究、社会性生物が協力して示すマクロインテリジェントな行動特性に基づいており、群知能最適化アルゴリズムとも呼ばれています。メタヒューリスティックアルゴリズムは、一般的な問題、つまり問題独立型の問題をターゲットにすることができ、幅広い適用性を持つブラックボックス操作として使用できます。ただし、アルゴリズムのさまざまなパラメータは、問題の特性に応じて調整する必要があります。ランダム最適化メカニズムを備えており、グローバル最適値を求めるのに適しています。

TSP 問題の場合、このタイプの方法における SOTA アルゴリズムは Lin-Kernighan-Helsgaun (LKH) であり、最大数万の問題を解決できます。 VRP 問題の場合、解決プロセスに応じて、構築ヒューリスティックと改善ヒューリスティックの 2 つのカテゴリに分類できます。構築ヒューリスティックは、初期の実行可能なソリューションを構築するために使用されます。一般的に使用される方法には、ソロモン I1 と保存ヒューリスティックがあります。後者の概略図を以下に示します。基本的な考え方は、各顧客ポイントをデポに接続して、1 つの配送ポイントのみを含む複数のルートを形成し、次に貪欲ルールを使用して、ポイント i とポイント j を 1 つのルートで接続することによって節約される距離を計算し、この手順を繰り返してルートをマージすることです。

改善ヒューリスティックは、初期ソリューションを改善するために使用されます。一般的に使用される方法を下の図に示します。基本的な考え方は、メタヒューリスティックアルゴリズムで近傍解を構築するための中間演算子としてよく使用されるポイントとエッジの位置または順序を交換し、ネストされた反復を使用して解の効果を継続的に最適化することです。

2.2.3 正確なアルゴリズム

正確なアルゴリズムとは、問題に対する最適な解決策を見つけることができるアルゴリズムです。難しい組み合わせ最適化問題の場合、問題の規模が小さい場合、正確なアルゴリズムは許容できる時間内に最適なソリューションを見つけることができます。問題の規模が大きい場合、正確なアルゴリズムは、一方では問題の実行可能なソリューションを提供し、他方では、より良いソリューションを検索できるようにヒューリスティックな方法の初期ソリューションを提供することができます。正確なアルゴリズムには、主に分岐限定法、切断面法、列生成アルゴリズム、動的計画法などが含まれます。

名前が示すように、正確なアルゴリズムはソリューション空間全体を検索し、最適なソリューションを見つけることが保証されます。もちろん、探索空間が大きすぎるため、実際には、探索空間を縮小するためにプルーニングなどの方法が使用されます。一般的なアプローチは、整数計画法 (IP) または混合整数計画法 (MIP) の問題としてモデル化し、双対理論を使用して問題の下限と上限を見つけ (最小化問題の場合、これは実行可能なソリューションです)、近似を続けることです。

古典的な VRPTW の数学的プログラミングモデルは次のとおりです。

このモデルは典型的な MIP モデルです。決定変数 x{ijk} は 0 または 1 の値を持つバイナリ変数です。s{ik} は車両 k が顧客 i に到着する時間を表す連続変数です。元の問題の下限は、線形緩和を解くことで簡単に得られますが、非常に弱い場合が多いため、切断面を追加することで改善されることがよくあります。ソースとシンクが与えられている場合、リソース制約を満たす最短パスが多数存在するため、列生成法を使用して、最初にいくつかの実行可能なパスを介してメイン問題を構築し、次に価格設定サブ問題を解決し、徐々に目的を改善できる新しい変数（列）を追加します。実行可能なソリューションを確実にするために、分数変数も分岐する必要があります。

具体的には、Branch and Bound は基本的に検索空間をツリーに構築し、ノードを継続的に選択して分割し、剪定を調整することで、最適な整数ソリューションを効果的に見つけます。ノードをどのように選択し、それらに値をどのように割り当てるかは、解を見つける速度に大きな影響を与えます。これは巨大なテーマであるため、多くのヒューリスティックな戦略が導き出されています。切断面法は、緩和された問題に対する非整数最適解から開始し、新しい線形不等式（対応する線形方程式によって表される超平面を切断面と呼びます）を順次追加して、新しい緩和された問題を解決します。列生成アルゴリズムは、分解の考え方と単体法の特性を利用します。すべての候補ソリューションを同時に処理するのではなく、主問題を制限して、現在生成された列のサブセットに基づいて主問題を最適化して解決します。残りの候補ソリューション（変数）は、制限された主問題の現在の最適ソリューションを改善できる場合にのみ、サブセットに入ります。

MIP の実際の解決では、これらの方法を組み合わせて、ブランチアンドカット、ブランチアンドプライス、ブランチアンドカットアンドプライス (BCP) 法などを形成することが多く、BCP 法は TSP と VRP を解決するための最も効果的で正確なアルゴリズムです。

3. 数理計画ソルバー

ソルバーは、実行可能な領域で最適なソリューションを見つけるために使用されるツールです。本質的には、複雑な数学アルゴリズムを実装するために使用される専門的な数学/コンピューティングソフトウェアです。現在、市場には主に商用ソルバーとオープンソースソルバーの 2 種類のソルバーが存在します。主な商用ソルバーには IBM CPLEX、GUROBI、FICO XPRESS などがあり、主なオープンソースソルバーには SCIP、COIN-OR、Google OR-Tools などがあります。商用ソルバーは一般にオープンソースソルバーよりも 5 ～ 7 倍効率的です。 VRPTW ベンチマーク C101 を例にとると、上記のモデルは Gurobi を通じて 3 秒以内に最適解を得ることができます。最適化ソルバーの存在により、上記の整数計画モデルの係数行列を最適化ソルバーに入力するだけで、最適解または実行可能解を素早く見つけることができます（分岐限定法に加えて、さまざまなヒューリスティックスと切断面アルゴリズムも統合されています）。

前述のように、混合整数計画法は、産業、経済、国防、医療などさまざまな業界で広く使用されています。現在、独自の整数計画ソルバーを持っている先進国は、米国の GUROBI、CPLEX、SAS、MATLAB、CBC、SYMPHONY、ドイツの SCIP、ロシアの MIPCL と GLPK、英国の XPRESS (後に米国の FICO が買収)、フィンランドの LPSOLVE など、ごくわずかです。商用ソルバーの主要3社であるCPLEX、GUROBI、XPRESSは、豊富な商用開発経験と優れたパフォーマンスにより、国際市場で90%以上のシェアを誇っています。現在の SOTA 数理計画法ソルバーは、2008 年に Zonghao Gu、Ed Rothberg、Robert Bixby によって設立された Gurobi Optimization です。2009 年の最初のリリース以来、Gurobi はソルバーのパフォーマンス (年間平均 60% の速度向上を実現) と適用性 (40 を超えるさまざまな業界の 2,400 社を超える企業にアプリケーションを拡張) において新しい基準を設定し続けています。

ソルバーは産業の発展において重要な役割を果たします。たとえば、我が国の戦略的レイアウトが直面している困難な問題である EDA (電子設計自動化) では、迅速な検証のために SAT ソルバーの使用が必要ですが、製造、物流、サプライチェーンの最適化には整数計画法ソルバー (特に線形計画法ソルバー) が必要です。数年前までは、ソルバーを必要とする企業は、CPLEX、GUROBI、XPRESS を米国から直接購入していました。幸いなことに、近年では国内の新興企業や、優れた技術力を持つインターネット大手企業も、独自の最適化ソルバーの開発や関連研究を開始しています。最初の「国産」ソルバーは2018年にリリースされました。まだ初期段階ではありますが、0から1へのブレークスルーを達成しました。

3.1 国内の数理計画ソルバー

3.1.1 CAS CMIP 混合整数計画ソルバー

2015年から、中国科学院数学・システム科学学院の戴宇紅研究員がCMIPチームを率いて30ヶ月をかけて中国初の国際レベルの整数計画ソルバーCMIPを独自に開発し、2018年3月にそのバージョンをCMIP 1.0として発表しました。 CMIP コードの総量は 50,000 行を超え、国際的に既存のソルバーの前処理、ヒューリスティック、切断面、分岐、ノード選択、ドメイン伝播などのさまざまな機能モジュールをカバーしており、大規模な整数計画を解く優れた能力を備えています。

3.1.2 LEAVES最適化ソルバーとCOPT

LEAVES 最適化ソルバーは、上海財経大学と Sunshu Technology が共同で構築したオペレーションズリサーチと人工知能の基本アルゴリズムプラットフォームです。これは、中国初の大規模なオペレーションズリサーチ最適化アルゴリズムソルバーでもあります。 LEAVES ソルバーは、線形計画法、半正定値計画法、幾何計画法、線形制約付き凸計画法などの一般的な大規模最適化問題を解決でき、現在はコミュニティでオープンソース化されています。

Sunshu Technology が開発した商用ソルバーである COPT は、大規模な混合整数計画法、線形計画法 (単体法と内点法)、2 次円錐計画法、半正定値計画法、および凸二次計画法と凸二次制約計画法の問題を解くことができる総合的な数理計画法ソルバーです。バージョン 1.0 は 2019 年 5 月にリリースされ、現在はバージョン 6.5 にアップデートされています。 2022年6月19日のミッテルマンテストリスト（http://plato.asu.edu/bench.html、アリゾナ州立大学のハンス・ミッテルマン教授が管理する数理計画ソルバーテストプラットフォーム。現在、世界で最も有名で権威があり、代表的な独立したサードパーティテストプラットフォームとして認められています）によると、COPTは線形計画法の単体法、内点法、凸二次計画法、半正定値計画法で1位にランクされました。

3.1.3 DAMOアカデミーマインドオプト

Mind-Opt は、Alibaba DAMO Academy の Decision Intelligence Laboratory が開発した、最適化問題を解決するためのプロフェッショナルコンピューティングソフトウェアです。クラウドコンピューティング、小売、金融、製造、運輸、エネルギーなどの分野で幅広く活用でき、弾力性のあるコンピューティングリソースのスケジューリングと最適化のシナリオにおいて、Alibaba Cloud は毎年数億ドルのコストを節約できると言われています。過去2年間、Sunshu、Alibaba、Gurobiは、線形計画法の権威あるリストであるMittlemannテストで激しい競争を繰り広げてきました。 2023 年 3 月 24 日のデータによると、MindOpt と COPT は両方とも、Mittelmann テストセットの LPopt リスト (http://plato.asu.edu/ftp/lpopt.html) でトップになりました。

3.1.4 ファーウェイ天翔

Huawei Cloud OptVerse AI ソルバーは、オペレーションズ・リサーチと AI を組み合わせ、業界の運用最適化の限界を打ち破り、混合整数線形計画問題と線形計画問題の解決をサポートし、最適なソリューションを求めます。その機能には、AI を活用した解決、履歴データと問題の特性に基づく最適なパラメータの適応選択、トポロジを考慮した分散並列アクセラレーションのサポート、Huawei Cloud の分散並列機能のフル活用などが含まれます。 2023年3月24日のデータによると、Tianchou AIソルバーは、ミッテルマンテストセットの大規模ネットワーク線形計画リストでTOP1にランクされました（http://plato.asu.edu/ftp/network.html）

4. 深層強化学習と組み合わせに関するクロス研究

現在、ディープラーニングは自然言語処理、視覚、音声、推奨などの分野で広く使用されています。ディープラーニングのタスクでは、モデルの損失関数を定義します。これは最適化問題の目的関数と呼ばれます。損失関数は予測値と実際の値のギャップを表し、特定の最適化アルゴリズム（SGDなど）を通じてこのギャップを減らします。ほとんどの場合、損失関数は非常に複雑で、明確で一意の解析解を得るのは困難です。代わりに、通常は最適化反復法によって数値解を近似します。機械学習アルゴリズムと従来のオペレーションズ・リサーチの最適化アルゴリズムの比較は次のとおりです。

	アドバンテージ	不十分
運用最適化アルゴリズム	堅牢で安定: 時間計算量と最悪ケース近似の理論的保証	新しい問題の場合、問題固有のヒューリスティックを設計するためにドメイン専門家の知識が必要である。
機械学習アルゴリズム	適応型でデータ駆動型: 特定のビジネスデータ分布に基づいてアルゴリズムのパフォーマンスを向上させる能力があり、大規模な問題への適用の可能性を提供します。	最適比率の保証がない

両者の利点を組み合わせることで、これら 2 種類のアルゴリズムの相互統合が徐々に研究のホットスポットになってきました。これらを組み合わせる主な方法は 2 つあります。(ここでは、Yoshua Bengio の論文の図を参照します。それぞれ図 7 と図 9 を参照してください)

機械学習をエンドツーエンドで使用して、与えられた問題に対する解決策を直接出力します（適切な後処理付き）
機械学習を従来のアルゴリズムと組み合わせる（例えば、機械学習を使用してパラメータやヒューリスティック戦略を選択するなど）

以下では、経路計画問題（TSP、VRP）を例に、これら2つの側面からの近年のいくつかの横断的な研究を紹介します。機械学習に基づく組み合わせ最適化を主軸として、RNN、アテンションメカニズム、Transformer、GNNなどが導入され、現在では多くの分野に発展しています。この方向性は、機械学習の急速な発展とともに急速に進化しています。より多くのアイデアが吸収され、組み合わせ最適化に統合されるにつれて、組み合わせ最適化は従来のアルゴリズムを強力に補完するものになるでしょう。

4.1 エンドツーエンド方式

4.1.1 初期の研究

組み合わせ最適化問題を解決するために機械学習を使用することは、初期の頃に試みられ、芽生えました。 1985 年、ホップフィールドとタンクの論文「最適化問題における決定のニューラル計算」では、ホップフィールドネットワークを使用して小規模な TSP インスタンスを解決しようとしました。欠点は、ハイパーパラメータとパラメータの初期化に敏感だったことです。1995 年、チャンとディートリッヒは論文「ジョブショップスケジューリングへの強化学習アプローチ」で、NP 困難なショップスケジューリング問題に強化学習を適用しました。1999 年の論文「組み合わせ最適化のためのニューラルネットワーク: 10 年を超える研究のレビュー」では、組み合わせ最適化問題にニューラルネットワークを使用する初期の研究をレビューしました。当時のデータと計算能力の限界を考慮すると、これらの試みのほとんどは研究と探索に限定されており、従来のアルゴリズムよりも優れた結果は得られませんでした。

4.1.2 ポインタネットワーク開始

シーケンスツーシーケンス（Seq2Seq）モデル、アテンションメカニズム、そして2014年に提案されたTransformerは、翻訳、チャットボット、テキスト生成などのシーケンスデータタスクの処理に広く使用されており、良好な結果を達成しています。しかし、従来のSeq2Seqモデルでは、デコーダーが出力するターゲットの数が固定されているため、出力シーケンスの語彙が入力シーケンスの長さに応じて変化するという問題を解決できません。たとえば、翻訳中の出力ベクトルの長さは辞書のサイズに等しいことが多く、出力は入力からしか選択できないという事前情報は無視されます。この結果、Seq2Seq は凸包問題や TSP などの一部の組み合わせ最適化問題に使用できなくなります。これらの問題の特徴は、出力が入力セットのサブセットであることが多い（出力は入力に大きく依存する）ことと、この長さが変化するということです。たとえば、TSP の出力は入力の完全な順列です。問題インスタンスごとに、入力の数、つまり都市の数は異なります。

2015年、Googleとカリフォルニア大学バークレー校の「ポインターネットワーク」は、ディープニューラルネットワークを組み合わせ最適化の分野に応用しました。Ptr-Netは、可変出力辞書サイズの問題を解決し、Attentionメソッドを修正することができます。Attentionの値に応じて、エンコーダー入力から1つが選択され、デコーダー出力になります。

Ptr-Net の最後の仕上げは、アテンションメカニズムの修正です。注意機構を備えた従来の seq2seq モデルでは、最初にエンコーダー部分を使用して入力シーケンスをエンコードし、次にエンコードされたベクトルに対して注意を実行し、最後にデコーダー部分を使用して注意後のベクトルをデコードして予測結果を取得します。しかし、Ptr-Net では、予測結果を得る方法は確率分布を出力することであり、これは論理的には入力内のノードを指すポインター、いわゆるポインターに似ています。つまり、注意メカニズムを備えた従来の seq2seq モデルは出力語彙の確率分布を出力しますが、Ptr-Net は入力テキストシーケンスの確率分布を出力します。

4.1.2 強化学習の導入

上記の方法は主に教師あり学習法であり、教師あり学習のアルゴリズムの品質はトレーニングセットの品質に大きく依存するため、比較的大きな制限となっています。つまり、このネットワークをトレーニングするには、まずトレーニングセット内の問題に対する高品質のソリューションを見つける必要があります。コンピュータービジョンにおけるオブジェクトの検出と画像の分類は、肉眼で行うことができます。ただし、トレーニングセット内の各サンプルが TSP などの NP 完全問題である場合、その最適解または高品質の実行可能解を見つけることは非常に複雑になります。教師あり学習の限界を克服するために、強化学習が導入されました。強化学習では、明示的にラベル付けされたデータセットは必要なく、環境との継続的な相互作用から得られるフィードバックを通じて学習するからです。

2018 年、リーハイ大学の論文「車両経路問題を解決するための強化学習」では、Ptr-Net を拡張して VRP を解決しました。 TSP と比較すると、VRP の難しさは、問題の入力が動的に変化する点にあります。たとえば、顧客が訪問すると、その需要が解消される（分割配送の場合は削減される）場合があります。 Ptr-Net 構造の問題は、入力シーケンス内の動的要素が変化すると、次のノードを予測するためにエンコーダー全体を更新する必要があり、計算量が増加することです。

この記事では、テキスト翻訳などのシナリオでは、単語間の相対関係など、入力セット内の要素間の順序が重要であるが、TSP や VRP などの組み合わせ最適化問題では、入力は顧客の場所と需要であり、それらの相対的な順序は無意味であると指摘しています。したがって、エンコーダ部分は削除され、デコーダ部分のみが保持されます。具体的には、埋め込み層では、静的要素（座標）が直接 $$D$$ 次元ベクトル空間にマッピングされ、異なる時刻の入力は同じ入力構造を共有します。注意層では、RNNの出力と動的要素（需要）が注意機構に入力され、次に実行可能な決定ポイントの確率分布が形成されます。

モデルのトレーニングでは、古典的なポリシー勾配法を採用しています。さらに、トレーニングを高速化し、実行可能なソリューションを生成するために、実行不可能なソリューションの対数確率を負の無限大に設定するマスキングスキームを使用します。後処理方法には、貪欲法とビーム検索の 2 つがあります。新しい問題インスタンスについては、同じ問題インスタンス分布からのものである限り、再トレーニングは必要ありません。中規模の VRP (顧客数 50、100) では、この方法は、従来のヒューリスティック手法 (Clarke-Wright 節約ヒューリスティック、スイープヒューリスティック) や Google OR ツールに比べて、ソリューションの品質において一定の利点があります。ビームサーチと組み合わせると、ORツールと比較して60％以上の勝率になります。

4.1.3 変圧器の構造

2017年、Googleの「注意が必要です」は、このペーパーではトランスモデルを提案し、（マルチヘッド）注意メカニズムを使用し、並列化が容易になりました。そのネットワーク構造は、パス最適化の問題を解決するためにも使用されます。たとえば、2019年のアムステルダム大学の論文「注意：ルーティングの問題を学ぶ！」では、元の変圧器モデルと比較して、ポジションエンコードはエンコーダーパーツでは使用されていません。（船の接続）およびバッチ正規化レイヤー（バッチ正規化、BN）。マルチヘッドの注意メカニズムにより、ノードは異なる近隣からさまざまなタイプのメッセージを受信でき、フィードフォワードサブレーヤーは512次元の隠れ層とReluアクティベーション関数を使用します。

デコーダーは、古典的な自己回帰モードを採用し、ステップt∈{1、...、n}で順番に実行します。デコードプロセス中、デコードコンテキストを表すために特別なコンテキストノード（c）を使用します。このコンテキストノードとその他の埋め込み情報は、出力ベクトルを取得するために、MHA層に渡されます（エンコーダーのMHAと比較して、SKIP接続、BNおよびFFサブレイヤーはここにありません）。最後に、デコーダー構造には単一の注意ヘッド（つまり、M = 1のMHA）があり、ソフトマックス出力は現在のステップの出力です。

トレーニングはポリシーベースの強化学習方法を採用し、ベースライン関数は、現在の最良のポリシーモデルに基づいて決定論的な貪欲な展開を実行することによって得られます。実験部品は、主にTSPやVRPのさまざまなバリエーションなど、さまざまなパスの問題を考慮しています。実験データは、ユニットスクエア内のランダムで均一なサンプリングによって取得されます。

4.1.4グラフ埋め込みとGNN

組み合わせ最適化の問題のジレンマは、さまざまなデータで同じタイプの問題を何度も解決する必要があることが多いことです。グラフの最適化の問題と問題インスタンスの分布を考えると、ヒューリスティックを見たことのない問題インスタンスを一般化する方法はありますか？機械学習を導入するという期待の1つは、その一般化能力を改善することです。つまり、訓練されたモデルは、目に見えない問題インスタンスに効果的に適用できます。一般化能力を向上させるために、グラフなどの非ユークリッドデータの場合、グラフ埋め込みはデータから効果的な機能を抽出するために使用され、低次元ベクトルを使用してグラフのトポロジー構造などの情報を表します。これは、後続の機械学習アルゴリズムの入力として使用されます。 Graph Neural Network（GNN）は、グラフ関連のタスクの1つを解決するために、深いニューラルネットワークモデルを適用する方法です。

2020年、Cainiao Networkは、「実用的な車両ルーティングの問題を効率的に解決する：新しい共同学習アプローチ」というタイトルのKDDに関する論文を公開しました。このモデルは、古典的なエンコーダデコーダーフレームワークに従います。エンコーダーパーツでは、GCNネットワークを使用して、グラフ内のポイントとエッジの表現を生成します。採用されたGCNエンコーダーは、ポイント入力とエッジ入力の両方を考慮し、実際の道路ネットワークのトラフィックアクセシビリティをエッジの埋め込みとして使用します。

デコーダー段階には、2つのデコーダーがあります。ポイントシーケンス予測デコーダーとエッジ分類デコーダーです。 πの中で、ポイントシーケンス予測デコーダーは、VRPの解決シーケンスを生成するための入力としてポイント機能を取得し、エッジ分類モデルはエッジ機能を入力として取り、エッジが存在するかどうかを表す確率マトリックスを出力します。エッジ分類デコーダには、分類トレーニングをガイドするためのラベルが必要ですが、特に問題サイズが大きい場合（たとえば、100を超える）、正確なアルゴリズムが合理的な時間で正確なソリューションを生成することは困難です。妥協点として、このペーパーは、ポイントシーケンス予測デコーダーによって得られたπを、エッジ確率マトリックスの接地（ラベル）として使用します。トレーニングプロセス中に、強化学習（ポイントシーケンス予測デコーダ）と監視された学習（エッジ分類デコーダー）を組み合わせた共同学習戦略が採用されています。

実験分析段階では、実際の配信データと実際の道路ネットワークマトリックスを選択し、比較実験はエッジの特徴の重要性を証明し、最終的にソリューションの品質を向上させることができました。

4.1.5 RLHF

VRPでは、最適化の目的は、総輸送コスト、移動時間/距離、必要な車両の数、時間窓違反などを最小限に抑えることです。これらの目標には、産業の練習では、明確で定量化可能な計算式があります。多くの場合、視覚的に魅力的に見えるようにします。次の図は、2つのソリューションを示しています。1つは視覚的な魅力（左）と、最小化目標として総コスト（右）をとるものを考慮します。明らかに、視覚的な魅力を考慮すると、ライン間の交差点が少なくなります。これはより美しく見え、アルゴリズムソリューションを実装しやすいです。この場合、各ドライバーはサービスを提供するために小さなエリアに集中しています。これは、ドライバーがこの地域の交通、駐車場、営業時間などに精通しているため、より高い運用効率を意味します。

ただし、ルートが美しく見え、交差点がないという事実は、主観的で定性的な説明であり、明確な計算式を定義することは困難です。確かに、計算ジオメトリ法を使用して、最初に各ルートの最小限の円と囲まれた凸ポリゴンを計算し、次にこれらのポリゴン間の重複領域または交差を最小限に抑えることができますが、これは視覚的魅力と直接等しいものではありません。そのようなソリューションが実装されている場合、それは引き続きディスパッチャーによって挑戦されます（実際の生産では、ディスパッチャは手動で電車を調整し、ルートを手配します）。別のオプションは、統計的方法を使用してディスパッチャーのエクスペリエンスを活用し、ある程度、「ドライバーがこの地域に精通している」ことを学ぶことです。

幸いなことに、TMSに保存されているディスパッチャーの派遣計画と車両駆動軌道を使用して、アルゴリズムの最適化を導くことができます。これは、LLMの進行軌跡に非常に似ています。 LLMは多様なテキストコンテンツを生成できますが、生成された結果の評価は主観的でコンテキスト依存的です。人間の好みと主観的な意見は、次の単語の予測方法と交差エントロピーなどの単純な損失関数をモデル化することによって明示的に導入されません。 RLHFは、強化学習を使用し、生成されたテキストに関する手動フィードバックをメトリックとして使用し、さらにこのフィードバックをモデルを最適化するために損失として使用して、ChatGptのようなモデルを輝かせることにより、人間のフィードバックで言語モデルを直接最適化します。 RLHFは、一般的なテキストデータのコーパスでトレーニングされた言語モデルを有効にして、複雑な人間の価値と一致します。

パス計画の実際のアプリケーションに戻ると、TMSに蓄積された派遣者の車の派遣ソリューション（視覚的な美しいソリューション）に基づいて、監視された学習が使用されます。強化学習のための報酬信号を作成するため。

要するに、RLHFを使用して、人間の専門家の知識と経験をエージェントの学習プロセスに統合することで、人間の経験を通じて、視覚的なソリューションなどの困難なソリューションを実装するための方向性が向上します。

4.2検索と後処理

前述のように、深い学習ベースの方法は、組み合わせ最適化の問題で非常に良い結果を達成しました。一方、これらの方法のほとんどは、いくつかの後処理操作と組み合わせる必要があり、次のカテゴリに分けることができることもわかります。

多くのタスクでは、確率を表すために機械学習モデルの出力のためのいくつかの後処理アルゴリズムを通じて最終的なソリューションが必要です。 1）貪欲：最高の出力確率を持つノードが毎回選択されます。 2）ビーム検索：幅が制限された基本的に幅最初の検索。 3）サンプリング：一定数のソリューションをサンプリングし、最適なソリューションを取得します。

機械学習部分は完全なソリューションを取得し、いくつかのローカル検索方法（2-OPT、3-OPTなどなど）と組み合わせて、このソリューションを変更して改善しようとします。 2019年、モントリオール統合テクノロジーおよび他の機関による「組み合わせの最適化のための機械学習アプローチ：巡回セールスマンの問題へのアプローチを評価する方法」は、いくつかの機械学習ベースの方法で得られたソリューションが2-OPT、3-OPT、LKなどの方法の改良後に大きな影響を与えることができることを示しました。

GCN出力ノードが最適なソリューションに属する可能性に基づいて、Fusion Tree SearchまたはMonte Carlo Tree Search（MCTS）のアイデアを使用して、ツリー検索で溶液を構築するために使用されます。この確率分布はマルチモーダルである可能性があるため、多くの候補ソリューションを生成できます。これは、その後のツリー検索でのより良い調査に役立ちます。 MCTは、トレーニングと推論の両方に追加されます。これにより、調査中の一般化能力が向上し、推論中の安定性が向上します。

4.3従来の方法との組み合わせ

組み合わせの最適化問題を解決するために機械学習を導入すると、上記の方法は主にエンドツーエンドの方法であり、別の重要な方法は、それを従来の方法または方法と組み合わせることです。

前述のように、最適化を組み合わせた従来の方法の最も古典的なソリューションは、整数のプログラミングの問題をモデル化することです。。通常、これらのハイパーパラメーターは、手動エクスペリエンスに基づいてソルバー開発者によって設定され、デフォルト値として一般的な問題に対する最も広い適用可能性を備えた一連のパラメーターを提供します。ただし、セグメント化された業界の特定のシナリオでは、まず、デフォルトのパラメーターをソルバーの最高のパフォーマンスを実現するのが困難です。第二に、ソルバーを使用するためのしきい値は比較的高いため、ユーザーは組み合わせの最適化、数学的計画アルゴリズム、シナリオの問題自体をより深く理解する必要があります。第三に、業界分野の専門家でさえ、ソルバーの大規模なパラメーターの組み合わせで特定のシナリオ問題に最適なパラメーターを選択するプロセスにおいて、手動パラメーター調整の課題を持っています。

ここで言及する必要があるのは、NEURLPSのML4CO（組み合わせ最適化のための機械学習）コンビナトリアル最適化競争です。 2021年のコンテストは、モントリオール大学とモントリオール大学の機械学習研究所が主催しています。ミラは、ヨシュアベンギオ教授によって設立された世界をリードするディープラーニングリサーチセンターです。この課題の焦点は、既存の組み合わせ最適化ソルバー（オープンソースソルバーSCIPとそのPythonパッケージEcole）のヒューリスティックコンポーネントを機械学習方法を通じて交換し、混合整数線形プログラミング問題（MILP）を最適化し、ソルバーパラメーターチューニングでの機械学習の適用とパラメーターの推奨事項を実現する目的を実現することです。オーガナイザーは、MILPの問題の制約境界をより速く締め、SCIPソルバーの最良のパラメーター推奨事項を求める方法に関するデュアルタスクトラックの調査など、完全に異なる実際の問題から生じる3つのMILPデータセットを提供し、業界固有のシナリオの問題で一般的なソルバーのパフォーマンスを改善するのに役立ちます。

具体的には、ソルバーには、ブランチの境界、切断平面、列生成などのアルゴリズムの組み込みソリューションフレームワークがあります。これには、ブランチ変数の選択、ノード選択戦略、ツリー検索中のノードクリッピング戦略、効果的な不平等の選択、非ネガティブなリストの選択など、いくつかの意思決定プロセスが含まれます。機械学習の導入は、意思決定を導くために大量のデータから独立してヒューリスティックルールを学ぶことです。たとえば、ブランチ区切り方式は、ソリューションスペースを再帰的に分割して検索ツリーを形成します。このツリーでは、バウンドが計算され、最適な値が含まれていないサブツリーがカットされます。彼等（2014）は、監視された学習を通じて適応型ノード検索戦略を取得します。さらに、Tang et alは、補強材を適応的に選択しました。これらは、ディープラーニングアルゴリズムを使用して、従来の方法または方法での意思決定ヒューリスティック選択戦略を支援する強力な試みです。

5。結論と提案

深い強化学習を使用して従来の組み合わせの最適化の問題を解決することは、学問的な波の波を引き起こした機械学習の活況とともに急速に進化しましたが、それを促進し、使用するために業界ではまだ長い道のりです。

学術研究の問題はすべて、明確で明確な定義に関する標準的な問題です。多くの場合、問題の定義は曖昧であり、試行錯誤を通じて制約と目的機能を決定する必要があります。パスの最適化を例にとると、ビジネス上の懸念は最短の距離であり、各車両のサービスエリアは、特にPOCシナリオで、車両の負荷、上限の制限、各サービスの上限制限などを可能な限り集中させることができます。機械学習アルゴリズムは、問題の定義（特定の制約の追加/削除など）を変更し、数学的な計画方法を箱から出して使用できます。

一方、学術研究の実験データ（倉庫の場所、顧客ノードの場所、需要量など）は、基本的に1つの間隔内でランダムに均一なサンプリングによって取得されるため、機械学習アルゴリズムは同じ世代ルールに基づいて大量のトレーニングデータを取得できます。実際のシナリオでは、顧客の分布と注文頻度には、明らかな数学的統計的特性がないことがよくあります。これにより、機械学習アルゴリズムは、特定の分布に従って生成されたデータセットでより良いパフォーマンスを発揮しますが、実際の例では不十分です。

たとえば、サプライチェーン企業でAI部門が実施したアルゴリズムの問題や、さまざまなビジネスラインや業界ラインには、多くの意思決定の最適化と深い学習シナリオがあります。上記のルート計画の問題はすべて、トランクおよびブランチルートルート、トランスミッションステーション、都市分布、およびターミナルリクルートメントにあります。決定の最適化のシナリオでは、従来の最適化方法は現在、上流の販売予測とボリューム予測リンクとしてのみ使用され、2つは相互に補完されます。現在、最適化の意思決定シナリオをエンドツーエンドでサポートするために、機械学習アルゴリズムの使用をまだ検討しています。しかし、マシンビジョン（CV）および自然言語処理（NLP）シナリオでは、非常に異なります。 CVとNLPの分野では、ディープラーニングがより成熟し、多くのオープンソースコードとフレームワークが出現し、業界で広く使用されています。

研究の深化とさまざまな業界での大規模なモデルの実装により、深い補強学習と組み合わせの最適化方法の相互統合により、分散型コンピューティングパワーと大規模なデータの利点の助けを借りて、業界でそれを実装し、価値を生み出します。