OR-Tools について

OR-Tools は組み合わせ最適化向けのオープンソース ソフトウェアです。これは、非常に広範な可能性のあるソリューションの中から問題に対する最適なソリューションを見つけるものです。OR-Tools で解決できる問題の例を次に示します。

  • 車両のルーティング: 特定の制約（「このトラックは 20,000 ポンド以下にする必要があります」または「すべての配達は 2 時間の時間枠内で行う必要があります」。
  • スケジューリング: 複雑なタスクセットに対する最適なスケジュールを見つけます。固定されたマシンセット、またはその他のリソースよりも先に実行しなければならないタスクもあります。
  • ビンパッキング: 最大容量の固定数のビンに、さまざまなサイズのオブジェクトをできるだけ多くパッキングします。

多くの場合、このような問題には可能性のある解決策が膨大な数にのぼります。パソコンにとってその解決策は多すぎます。これに対処するために、OR-Tools は最先端のアルゴリズムを使用して検索セットを絞り込み、最適な（または最適な）ソリューションを見つけます。

OR-Tools には、

制約計画
制約として表される問題に適した解決策を見つけるための一連の手法（たとえば、1 つの部屋を 2 つのイベントに同時に使用することはできません。また、農作物までの距離を、ホースの長さ未満、または一度に録画できるテレビ番組 5 本以下にする必要があります）。
線形整数と混合整数計画法
Glop 線形オプティマイザーは、一連の不等式を制約として指定できます（例: 人に仕事を割り当てる、コストを最小限に抑えながら最適なリソースのセットを割り出す）。Glop と混合整数プログラミング ソフトウェアの SCIP は、Google Apps Script 最適化サービスを通しても利用できます。
車両ルート
制約がある最適な車両ルートを識別する専用ライブラリ。
グラフ アルゴリズム
グラフ、最小費用のフロー、最大フロー、線形和の割り当てで最短パスを見つけるためのコード。

次のセクションでは、OR-Tools をすぐに使い始めることができます。