關於 OR-Tools

OR-Tools 是組合最佳化的開放原始碼軟體,可在一組非常可能的解決方案中,針對問題找出最佳解決方案。以下列舉 OR-Tools 能夠解決的問題:

  • 車輛路線規劃:根據車輛限制 (例如「這款卡車不能超過 20,000 磅」或「所有送貨人員必須在 2 小時內完成」
  • 排程:為一組複雜的工作找出最佳排程,其中部分工作需要在一組固定的機器或其他資源上執行。
  • 特徵分塊包裝:盡可能將多種不同大小的物件封裝成具有最大容量的固定二進位數。

在這類情況下,這類問題通常有許多可能的解決方案,例如讓電腦一次搜尋所有解決方案。 為了克服上述問題,OR-Tools 使用最先進的演算法縮小搜尋集,以找出最佳 (或接近最佳) 解決方案。

OR-Tools 提供下列工具的解題工具:

限製程式設計
運用一組技巧找出可解決的解決方案,以解決限制 (例如一個房間無法同時用於兩個事件,或兩地的裁剪距離不得短於軟管長度,或一次不能錄製超過 5 個電視節目)。
線性和混合整數程式設計
Glop 線性最佳化器會根據一組線性不等式的限制,找出線性目標函式的最佳值 (例如,指派工作給指定人員,或找出一組資源的最佳分配,同時將成本降到最低)。Glop 和混合整數程式設計軟體 SCIP 也可透過 Google Apps Script Optimization Service 取得。
汽車路線
專門用來找出特定限制條件的最佳車輛路徑專用程式庫。
圖形演算法
用於在圖形中尋找最短路徑的程式碼、最低流程、最大流量和線性總和。

下一節將協助您快速開始使用 OR-Tools。