OR-Tools 是組合最佳化的開放原始碼軟體,可在一組非常可能的解決方案中,針對問題找出最佳解決方案。以下列舉 OR-Tools 能夠解決的問題:
- 車輛路線規劃:根據車輛限制 (例如「這款卡車不能超過 20,000 磅」或「所有送貨人員必須在 2 小時內完成」
- 排程:為一組複雜的工作找出最佳排程,其中部分工作需要在一組固定的機器或其他資源上執行。
- 特徵分塊包裝:盡可能將多種不同大小的物件封裝成具有最大容量的固定二進位數。
在這類情況下,這類問題通常有許多可能的解決方案,例如讓電腦一次搜尋所有解決方案。 為了克服上述問題,OR-Tools 使用最先進的演算法縮小搜尋集,以找出最佳 (或接近最佳) 解決方案。
OR-Tools 提供下列工具的解題工具:
- 限製程式設計
- 運用一組技巧找出可解決的解決方案,以解決限制 (例如一個房間無法同時用於兩個事件,或兩地的裁剪距離不得短於軟管長度,或一次不能錄製超過 5 個電視節目)。
- 線性和混合整數程式設計
- Glop 線性最佳化器會根據一組線性不等式的限制,找出線性目標函式的最佳值 (例如,指派工作給指定人員,或找出一組資源的最佳分配,同時將成本降到最低)。Glop 和混合整數程式設計軟體 SCIP 也可透過 Google Apps Script Optimization Service 取得。
- 汽車路線
- 專門用來找出特定限制條件的最佳車輛路徑專用程式庫。
- 圖形演算法
- 用於在圖形中尋找最短路徑的程式碼、最低流程、最大流量和線性總和。
下一節將協助您快速開始使用 OR-Tools。