：用開源求解器搞定排班、路徑與裝箱難題)
先跟你聊個項目煩惱排班表排到崩潰、配送路線越跑越遠、倉庫裝箱總覺得空了一半。這些事擱以前我第一反應是寫一堆規(guī)則加一堆 if else結(jié)果規(guī)則越來越多真到要用的那天還是得靠老師傅拍腦袋。直到我在實際項目里把組合優(yōu)化工具正經(jīng)用起來才發(fā)現(xiàn)這些問題的解法其實是同一個套路。今天要聊的這套 Google OR-Tools就是那個讓我少走兩年彎路的神級開源套件。它不是一個只會解某種數(shù)學題的單一求解器而是一整套組合優(yōu)化工具箱員工排班、車輛路徑規(guī)劃、裝箱、背包、排課、資源分配基本你能想到的離散優(yōu)化問題它都能建模求解。而且對 Python 開發(fā)者極其友好從安裝到跑通第一個模型五分鐘足夠。如果你是做業(yè)務系統(tǒng)的工程師、供應鏈物流方向的同學或者剛接觸運籌優(yōu)化的學生這篇內(nèi)容應該能幫你把工具的全貌和落地方案一次性看明白。1. OR-Tools 是什么一個組合優(yōu)化工具箱而不是單一求解器1.1 四種核心求解器各管一攤我最早誤以為 OR-Tools 就一個求解函數(shù)進去之后才發(fā)現(xiàn)它是整套體系。核心組件分四大塊每一塊處理的數(shù)學問題類型完全不同。第一塊是約束規(guī)劃求解器也就是 CP-SAT。它最適合處理一堆約束 有限離散變量的問題比如排班、排課、任務調(diào)度。它的核心思路不是傳統(tǒng)線性規(guī)劃那種單純形法而是基于約束傳播與沖突驅(qū)動的子句學習在搜索過程中不斷剪枝。說人話就是它會把張三不能連續(xù)上夜班每個班次至少兩個人這類規(guī)則塞進約束系統(tǒng)里再用啟發(fā)式搜索高效地翻找可行區(qū)域。后續(xù)版本的 CP-SAT 還內(nèi)置了線性松弛能力使得它處理帶目標函數(shù)的優(yōu)化問題也很強不只是找可行解。第二塊是路由求解器專精車輛路徑問題。這個模塊底層其實集成了帶本地搜索的元啟發(fā)式方法比如大規(guī)模鄰域搜索。它跟你自己在圖上寫 Dijkstra 完全不是一回事。路由求解器不是單純找一條最短路而是統(tǒng)籌多臺車輛、多個點、多時間窗、多容量限制的整體路線方案。第三塊是線性優(yōu)化求解器處理整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、線性規(guī)劃。OR-Tools 里通過 pywraplp 接口調(diào)用的底層求解器是開源的 CLP、CBC、SCIP 等。這一塊適合變量規(guī)模大、約束關系平移但約束類型比較規(guī)整的問題比如生產(chǎn)排程里常見的混合整數(shù)模型。第四塊是圖算法套件提供最短路徑、最大流、最小費用流這些經(jīng)典圖論算法。小場景里你自己寫 BFS 沒問題但上了規(guī)模直接調(diào)用它內(nèi)部高度優(yōu)化的 C 實現(xiàn)效率天差地別。1.2 為什么說它對開發(fā)者友好說一下體感OR-Tools 對開發(fā)者最大的友好是抽象層次。它把運籌建模里最繁瑣的構(gòu)造標準型矩陣稀疏化求解器參數(shù)調(diào)優(yōu)全部包掉了。你只需要定義有哪些決策變量這些變量滿足什么約束你想最大化或最小化什么然后交給求解器。這個思維方式和寫普通業(yè)務代碼不同但一旦轉(zhuǎn)換過來建模速度非常快。而且 Python 接口能做到與 C 底層幾乎一致的性能不需要為了性能提前切換到 C這對快速驗證方案簡直不要太舒服。另外一個很關鍵的點OR-Tools 是純開源商用友好的 license。你在商業(yè)項目里集成它不需要擔心授權成本這就讓它成為很多創(chuàng)業(yè)團隊和中小型項目的第一選擇。相比動輒幾十萬授權的商業(yè)求解器這是一上來就能直接開工的方案。2. 安裝與第一個模型十分鐘跑通 0/1 背包2.1 安裝只有一條命令環(huán)境要求很簡單Python 3.8 以上的環(huán)境就夠了。安裝直接用包管理工具pip install ortools這里有個小坑如果你是在公司內(nèi)網(wǎng)環(huán)境裝建議先確認 Python 版本和網(wǎng)絡源。我遇到過裝完導入時報ortools模塊不存在十有八九是環(huán)境中同時存在多個 Python 解釋器把包裝到了另一個環(huán)境下。用虛擬環(huán)境能規(guī)避掉這種低級問題。2.2 用 CP-SAT 解背包問題代碼就這么簡單先給你一個最小的可運行例子用 CP-SAT 解經(jīng)典 0/1 背包問題from ortools.sat.python import cp_model weights [2, 3, 4, 5, 9] values [3, 4, 5, 8, 10] capacity 10 n len(weights) model cp_model.CpModel() # 決策變量每個物品選還是不選 x [model.NewBoolVar(fx_{i}) for i in range(n)] # 重量約束總重量不超過容量 model.Add(sum(weights[i] * x[i] for i in range(n)) capacity) # 目標函數(shù)最大化總價值 model.Maximize(sum(values[i] * x[i] for i in range(n))) solver cp_model.CpSolver() status solver.Solve(model) if status in (cp_model.OPTIMAL, cp_model.FEASIBLE): selected [i for i in range(n) if solver.Value(x[i]) 1] print(總價值:, solver.ObjectiveValue()) print(選擇的物品:, selected) else: print(無解)這段代碼很短但已經(jīng)完整走完了 OR-Tools 建模的標準流程創(chuàng)建模型對象、聲明變量、添加約束、定義目標、調(diào)用求解器、讀取結(jié)果。跑完你就能看到在容量 10 的情況下最優(yōu)總價值是 18選擇的物品是索引 0、2、3 這三件。2.3 理解建模三個要素變量、約束、目標很多新手上來就卡在我的業(yè)務怎么轉(zhuǎn)換成變量、約束、目標這步。其實有個套路可循先問自己哪些東西是需要系統(tǒng)替我決定的。選的物品、排班的人、路徑上的點這些都是決策變量。再說約束現(xiàn)實里硬性不能違反的規(guī)則就是約束比如總量不能超載每人每天最多一個班次必須按時交付。最后是目標通常一個量化指標比如最省錢、耗時最短、資源利用最均衡。這個順序全部想清楚再動手寫代碼建模成功率會提高非常多。另外注意 CP-SAT 里的變量是整數(shù)域。背包問題天然用 0/1 變量這個例子剛好體現(xiàn)布爾變量NewBoolVar的用法。實際情況中更多是NewIntVar(low, high, name)來定義整數(shù)區(qū)間的變量。3. 三個高頻實戰(zhàn)場景這樣建模基本不會跑偏3.1 員工排班最難的不是約束是把人的規(guī)則翻譯成數(shù)字模型排班問題我前后做過好幾個版本給某連鎖門店做排班系統(tǒng)時最大的痛苦不是寫求解器而是跟店長梳理規(guī)則。你會發(fā)現(xiàn)現(xiàn)實規(guī)則特別多且碎不能連上兩個夜班、周末盡量少排新人、每個班次必須有一個老員工、休假天數(shù)要動態(tài)變化。翻譯成數(shù)學約束之后代碼反而沒有那么多。下面是我經(jīng)常用來演示的排班模型稍微精簡但保留了核心約束from ortools.sat.python import cp_model num_workers 4 num_days 7 num_shifts 3 # 班次0、1、2 model cp_model.CpModel() shifts {} # w員工, d天, s班次 for w in range(num_workers): for d in range(num_days): for s in range(num_shifts): shifts[(w, d, s)] model.NewBoolVar(fw{w}_dgv5xshg9wyt_s{s}) # 每人每天最多一個班次 for w in range(num_workers): for d in range(num_days): model.Add(sum(shifts[(w, d, s)] for s in range(num_shifts)) 1) # 每天每個班次至少安排一個人 for d in range(num_days): for s in range(num_shifts): model.Add(sum(shifts[(w, d, s)] for w in range(num_workers)) 1) # 每人每周班次數(shù)盡量控制在 2~4 之間 for w in range(num_workers): model.Add(sum(shifts[(w, d, s)] for d in range(num_days) for s in range(num_shifts)) 2) model.Add(sum(shifts[(w, d, s)] for d in range(num_days) for s in range(num_shifts)) 4) solver cp_model.CpSolver() status solver.Solve(model) if status in (cp_model.OPTIMAL, cp_model.FEASIBLE): for d in range(num_days): line f第{d1}天: for s in range(num_shifts): for w in range(num_workers): if solver.Value(shifts[(w, d, s)]) 1: line f班次{s1}員工{w1} print(line) else: print(無解)這個模型沒有目標函數(shù)只求可行解就已經(jīng)能滿足不少小規(guī)模排班需求。如果你想進一步做到公平把每個員工總班次數(shù)盡量均衡定義成 minimize 目標即可。還有更細的約束組合OR-Tools 提供了AddAllowedAssignments、AddAllDifferent、AddExactlyOne這些封裝能很優(yōu)雅地表達復雜規(guī)則。實戰(zhàn)心得是排班問題的建模順序一定是從硬約束開始先讓模型有解再加軟約束和目標函數(shù)。一上來把所有規(guī)則全部塞進去求解器可能直接給你返回一個不可行狀態(tài)到時候你根本分不清是哪條規(guī)則寫錯了。3.2 車輛路徑繞城配送的路線一行回調(diào)函數(shù)就能搞定路徑優(yōu)化是另一個常見的硬骨頭。某物流調(diào)度項目里我有一張真實的城市配送距離表二十多個配送點三臺車每輛車容量還不同。手動排路線基本就是憑借老師傅經(jīng)驗但分完路線之后經(jīng)常出現(xiàn)一輛車超載、另一輛空跑的情況。用 Routing 求解器之后方案質(zhì)量提升非常明顯。最小的 TSP單輛車的旅行商問題代碼如下from ortools.constraint_solver import routing_enums_pb2, pywrapcp distance_matrix [ [0, 2, 9, 10], [1, 0, 6, 4], [15, 7, 0, 8], [6, 3, 12, 0], ] manager pywrapcp.RoutingIndexManager(len(distance_matrix), 1, 0) routing pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) search_parameters pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) solution routing.SolveWithParameters(search_parameters) if solution: index routing.Start(0) route [] while not routing.IsEnd(index): route.append(manager.IndexToNode(index)) index solution.Value(routing.NextVar(index)) route.append(manager.IndexToNode(index)) print(TSP 路線:, route)核心是那個distance_callbackOR-Tools 會反復調(diào)用它來詢問任意兩點之間的代價這個代價不一定是距離也可以是時間、油耗、費用。Routing 模塊把這類指標統(tǒng)稱為代價回調(diào)注冊到模型里就自動參與優(yōu)化計算。多車輛、容量限制、時間窗基本都是在這個結(jié)構(gòu)上疊加維度實現(xiàn)的比如用routing.AddDimension來創(chuàng)建容量或時間維度。這類問題我最想提醒的一點距離矩陣一定要保證正確性。我之前用地圖 API 批量計算時因為部分點之間沒有道路通行直接給了一個極大值當距離結(jié)果求解器把路線硬繞到極遠的地方我還以為模型寫錯了排查半天才發(fā)現(xiàn)是數(shù)據(jù)源問題。先把數(shù)據(jù)清洗干凈再談模型優(yōu)化。3.3 裝箱與資源分配空間和資源其實可以抽象成維度裝箱問題聽起來難但實際上在 OR-Tools 里建模并不復雜。它可以抽象成有一批物品每個有長寬高或重量有若干個箱子每個箱子有容量上限目標是用最少箱子裝完所有物品或者把一個箱子填得更滿。這類問題通常會深度使用 CP-SAT 的區(qū)間變量和可選區(qū)間機制來處理物品與箱子之間的等價關系。不過這里我不想貼太長代碼給你一個建模思路把每個物品放進哪個箱子作為整數(shù)變量范圍為 0 到箱子總數(shù)減一再對每個箱子的總重量、總體積分別建立約束最后把箱子是否使用這個布爾變量設為目標函數(shù)去最小化。在資源分配場景中OR-Tools 還有一個非常實用的抽象叫維度。路由求解器里的容量維度、時間維度本質(zhì)上是給每輛車維護一個沿路線累積的量比如裝了多少貨、走了多久。這個抽象幾乎能覆蓋所有帶累積約束的問題比如外賣配送的保溫箱容量、生產(chǎn)線上的上下料時間。理解了維度你再看它的文檔會豁然開朗。4. 建模時最容易翻車的細節(jié)我替你試過4.1 浮點數(shù)會坑你CP-SAT 只吃整數(shù)這是新手入坑會遇到的第一大坑。CP-SAT 的所有變量和約束都是整數(shù)域它本身不處理浮點數(shù)。如果你在業(yè)務里遇到價格、重量、時間這些帶小數(shù)點的數(shù)據(jù)直接傳給模型會報錯或者結(jié)果被隱式截斷。標準做法是縮放成整數(shù)。比如金額保留兩位小數(shù)就乘以 100 轉(zhuǎn)成分重量精確到克就乘以 1000。縮放比例需要全局一致否則約束關系會失調(diào)。這個轉(zhuǎn)換過程看似簡單但我在項目里吃過虧曾經(jīng)把時間粒度從分調(diào)整成秒時忘了改所有約束里的對應系數(shù)結(jié)果模型算出一堆不可行的路線。所以建議在一開始就把數(shù)據(jù)粒度定義寫清楚建模代碼里統(tǒng)一使用同一個常量系數(shù)。4.2 軟約束和獎勵要怎么揉進目標函數(shù)業(yè)務系統(tǒng)里很多規(guī)則不是絕對的比如盡量讓老員工優(yōu)先休假盡量少用一個箱子。這樣的軟約束不能直接放進硬約束列表里否則模型可能直接被搞到無解。常規(guī)做法是引入懲罰變量或者獎勵變量把違反程度乘上一個懲罰系數(shù)加進目標函數(shù)。目標函數(shù)是一個被最小化或最大化的量所以盡量少用一個箱子就可以寫成minimize(箱子使用數(shù)量 * 成本系數(shù))。這個過程的難點在于系數(shù)怎么定。系數(shù)太小求解器會無視這個懲罰系數(shù)太大又會過度犧牲其他目標。實際調(diào)參時我會先固定一個目標觀察另一個指標的變化幅度然后二分調(diào)整系數(shù)基本幾次就會收斂到可接受的范圍。4.3 求解時間失控怎么限制和判斷組合優(yōu)化在規(guī)模大的時候非常容易求解時間失控。OR-Tools 默認會一直算下去直到證明最優(yōu)這在生產(chǎn)環(huán)境是不能接受的。幾乎所有實戰(zhàn)項目里都要顯式加上時間限制。CP-SAT 的用法是solver.parameters.max_time_in_seconds 10Routing 求解器則是search_parameters.time_limit.seconds 10加了時間限制之后求解器可能在超時前返回一個可行但不保證最優(yōu)的結(jié)果。這時候就要學會看兩個指標ObjectiveValue是當前找到的最好目標值BestObjectiveBound是理論上能夠達到的邊界。兩者越接近說明距離最優(yōu)解越近。如果時間到了但 gap 還很大就說明模型還沒收斂要么加時間要么簡化模型。5. 常見問題與排查思路速查5.1 模型一直解出 0 或空解如果是排班模型這種用布爾變量的場景解出來全是空大概率是約束條件互相沖突。我遇到過有人把每人每天至少一個班次和每人每天最多一個班次同時設成嚴格相等還把班次數(shù)和人數(shù)傳給搞錯了結(jié)果是必然無解。排查辦法也簡單把所有約束先注釋掉只保留一組硬約束跑一次如果還產(chǎn)生結(jié)果再把約束逐個加回來很快能定位到?jīng)_突的那一條。5.2 解有了但不是最優(yōu)而且差得遠出現(xiàn)這個現(xiàn)象的常見原因是目標函數(shù)沒寫對或者沒寫全。比如排班問題里你只寫了可行性約束那求解器給出任何一個可行解就停了你根本不知道它是不是優(yōu)化過。另外還有一個隱蔽坑距離或成本矩陣的單位不一致。某個項目里我有一段距離是公里另一段距離是米模型計算結(jié)果里路線亂繞最終對比實際里程才發(fā)現(xiàn)是單位沒統(tǒng)一。先檢查數(shù)據(jù)的一致性再檢查目標函數(shù)。5.3 規(guī)模一大就跑不動怎么辦如果問題規(guī)模確實很大第一件事是審視模型的對稱性。比如兩個員工能力一致、位置互換解相同這種情況下解空間存在大量對稱解搜索效率極低。解決思路是加對稱破壞約束比如強制員工 A 的班次數(shù)不大于員工 B。第二個手段是給求解器開多線程CP-SAT 支持設置搜索并行度solver.parameters.num_search_workers 8第三招是對問題做降維分解。比如把大片區(qū)拆成若干小片區(qū)分別求解再合并結(jié)果或者先用啟發(fā)式算法產(chǎn)生一個不錯的初始解再交給 OR-Tools 做改進。OR-Tools 里可以通過設置初始解候選來加速收斂。5.4 排查順序和幾個實用技巧把最常見問題的排查順序整理成一張速查表方便你直接對照現(xiàn)象優(yōu)先排查推薦的修復動作無解約束沖突逐條注釋約束定位沖突檢查變量域是否為空結(jié)果全為 0變量未被約束綁定檢查決策變量定義范圍確認布爾變量是否有遺漏約束結(jié)果差得遠目標函數(shù)或數(shù)據(jù)單位錯誤驗證目標表達式統(tǒng)一數(shù)據(jù)縮放系數(shù)求解超時模型規(guī)?；騾?shù)設置不合理加時間限制、開并行、降維或拆分問題結(jié)果不穩(wěn)定初值/隨機種子影響固定隨機種子或增加求解時間還有一個實用技巧CP-SAT 求解后的狀態(tài)碼要會看。OPTIMAL代表已經(jīng)證明最優(yōu)FEASIBLE代表找到了可行解但未證明最優(yōu)INFEASIBLE代表無解。很多人在狀態(tài)碼處理上只看OPTIMAL導致明明有合法排班結(jié)果卻因為狀態(tài)碼不對直接忽略非?？上А?. 它的邊界在哪里什么時候該換更專業(yè)的求解器6.1 哪些問題它搞不定OR-Tools 在離散優(yōu)化領域很強悍但不代表所有優(yōu)化問題都能包打天下。連續(xù)變量為主的問題比如投資組合優(yōu)化、連續(xù)參數(shù)調(diào)優(yōu)它的表現(xiàn)就不夠好。這類問題更適合專業(yè)的線性規(guī)劃或非線性規(guī)劃求解器甚至可以直接用數(shù)值優(yōu)化庫。另外如果問題包含復雜的非線性約束比如乘積形式的約束CP-SAT 的整數(shù)模型很難直接表達需要通過分段線性化等手段重新建模這工作量往往不小。還有個容易被忽視的限制OR-Tools 不擅長處理不確定性優(yōu)化。比如需求不確定的庫存優(yōu)化、概率約束問題它不是為這類隨機優(yōu)化設計的。當你發(fā)現(xiàn)核心業(yè)務邏輯需要大量處理和概率相關的變量就該考慮其他方案了。6.2 和啟發(fā)式算法的配合我不建議把所有問題都丟給一個求解器。實際工程里效果最好的方式往往是 OR-Tools 和啟發(fā)式算法配合。比如先用貪心或遺傳算法得到一個初始解再把初始解作為起點喂給 OR-Tools 去進行局部大鄰域搜索讓它在這個基礎上優(yōu)化。反過來也行先讓 OR-Tools 快速求一個可行解再用專門的鄰域搜索來微調(diào)。OR-Tools 路由模塊本身就內(nèi)置了多種搜索策略你完全可以用自定義啟發(fā)式方法來擾動初始解空間這會讓最終方案質(zhì)量明顯提升。6.3 換個更專業(yè)的求解器說句實話如果你的問題明確是大型混合整數(shù)規(guī)劃比如幾十萬級變量、幾百萬條約束OR-Tools 的開源求解器確實比不過商業(yè)求解器比如高性能商用 MIP 求解器帶來的性能差距是數(shù)量級的。在這個場景下我建議把 OR-Tools 當作原型驗證工具用它快速驗證模型方向是否可行然后切換到商業(yè)求解器做生產(chǎn)級計算。不過絕大部分業(yè)務場景其實沒有到那個量級我做過不少項目變量規(guī)模在幾千到幾萬個之間OR-Tools 的 CP-SAT 表現(xiàn)相當夠用而且免費這個優(yōu)勢讓它成為中小企業(yè)落地的最佳起點。先跑通再優(yōu)化比一開始就上重武器要現(xiàn)實得多。最后分享一點我在多個真實項目里的體感這類工具一定要用一個真實場景完整跑一遍你才會理解建模比求解更重要。變量定義是否清晰、約束里是否悄悄混進了軟規(guī)則、目標函數(shù)是否真正貼合業(yè)務指標這些決定了結(jié)果的可用性。工具再強也替你做不了業(yè)務建模的思考。建議你找一個手頭最常見的排班或路徑問題從最小模型開始一步步加約束很快你就會迷上這種把規(guī)則變成數(shù)學再讓機器替你找答案的感覺。遇到具體的坑歡迎在評論區(qū)和大家交流。 Google OR-Tools實戰(zhàn)：用開源求解器搞定排班、路徑與裝箱難題
先跟你聊個項目煩惱排班表排到崩潰、配送路線越跑越遠、倉庫裝箱總覺得空了一半。這些事擱以前我第一反應是寫一堆規(guī)則加一堆 if else結(jié)果規(guī)則越來越多真到要用的那天還是得靠老師傅拍腦袋。直到我在實際項目里把組合優(yōu)化工具正經(jīng)用起來才發(fā)現(xiàn)這些問題的解法其實是同一個套路。今天要聊的這套 Google OR-Tools就是那個讓我少走兩年彎路的神級開源套件。它不是一個只會解某種數(shù)學題的單一求解器而是一整套組合優(yōu)化工具箱員工排班、車輛路徑規(guī)劃、裝箱、背包、排課、資源分配基本你能想到的離散優(yōu)化問題它都能建模求解。而且對 Python 開發(fā)者極其友好從安裝到跑通第一個模型五分鐘足夠。如果你是做業(yè)務系統(tǒng)的工程師、供應鏈物流方向的同學或者剛接觸運籌優(yōu)化的學生這篇內(nèi)容應該能幫你把工具的全貌和落地方案一次性看明白。1. OR-Tools 是什么一個組合優(yōu)化工具箱而不是單一求解器1.1 四種核心求解器各管一攤我最早誤以為 OR-Tools 就一個求解函數(shù)進去之后才發(fā)現(xiàn)它是整套體系。核心組件分四大塊每一塊處理的數(shù)學問題類型完全不同。第一塊是約束規(guī)劃求解器也就是 CP-SAT。它最適合處理一堆約束 有限離散變量的問題比如排班、排課、任務調(diào)度。它的核心思路不是傳統(tǒng)線性規(guī)劃那種單純形法而是基于約束傳播與沖突驅(qū)動的子句學習在搜索過程中不斷剪枝。說人話就是它會把張三不能連續(xù)上夜班每個班次至少兩個人這類規(guī)則塞進約束系統(tǒng)里再用啟發(fā)式搜索高效地翻找可行區(qū)域。后續(xù)版本的 CP-SAT 還內(nèi)置了線性松弛能力使得它處理帶目標函數(shù)的優(yōu)化問題也很強不只是找可行解。第二塊是路由求解器專精車輛路徑問題。這個模塊底層其實集成了帶本地搜索的元啟發(fā)式方法比如大規(guī)模鄰域搜索。它跟你自己在圖上寫 Dijkstra 完全不是一回事。路由求解器不是單純找一條最短路而是統(tǒng)籌多臺車輛、多個點、多時間窗、多容量限制的整體路線方案。第三塊是線性優(yōu)化求解器處理整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、線性規(guī)劃。OR-Tools 里通過 pywraplp 接口調(diào)用的底層求解器是開源的 CLP、CBC、SCIP 等。這一塊適合變量規(guī)模大、約束關系平移但約束類型比較規(guī)整的問題比如生產(chǎn)排程里常見的混合整數(shù)模型。第四塊是圖算法套件提供最短路徑、最大流、最小費用流這些經(jīng)典圖論算法。小場景里你自己寫 BFS 沒問題但上了規(guī)模直接調(diào)用它內(nèi)部高度優(yōu)化的 C 實現(xiàn)效率天差地別。1.2 為什么說它對開發(fā)者友好說一下體感OR-Tools 對開發(fā)者最大的友好是抽象層次。它把運籌建模里最繁瑣的構(gòu)造標準型矩陣稀疏化求解器參數(shù)調(diào)優(yōu)全部包掉了。你只需要定義有哪些決策變量這些變量滿足什么約束你想最大化或最小化什么然后交給求解器。這個思維方式和寫普通業(yè)務代碼不同但一旦轉(zhuǎn)換過來建模速度非常快。而且 Python 接口能做到與 C 底層幾乎一致的性能不需要為了性能提前切換到 C這對快速驗證方案簡直不要太舒服。另外一個很關鍵的點OR-Tools 是純開源商用友好的 license。你在商業(yè)項目里集成它不需要擔心授權成本這就讓它成為很多創(chuàng)業(yè)團隊和中小型項目的第一選擇。相比動輒幾十萬授權的商業(yè)求解器這是一上來就能直接開工的方案。2. 安裝與第一個模型十分鐘跑通 0/1 背包2.1 安裝只有一條命令環(huán)境要求很簡單Python 3.8 以上的環(huán)境就夠了。安裝直接用包管理工具pip install ortools這里有個小坑如果你是在公司內(nèi)網(wǎng)環(huán)境裝建議先確認 Python 版本和網(wǎng)絡源。我遇到過裝完導入時報ortools模塊不存在十有八九是環(huán)境中同時存在多個 Python 解釋器把包裝到了另一個環(huán)境下。用虛擬環(huán)境能規(guī)避掉這種低級問題。2.2 用 CP-SAT 解背包問題代碼就這么簡單先給你一個最小的可運行例子用 CP-SAT 解經(jīng)典 0/1 背包問題from ortools.sat.python import cp_model weights [2, 3, 4, 5, 9] values [3, 4, 5, 8, 10] capacity 10 n len(weights) model cp_model.CpModel() # 決策變量每個物品選還是不選 x [model.NewBoolVar(fx_{i}) for i in range(n)] # 重量約束總重量不超過容量 model.Add(sum(weights[i] * x[i] for i in range(n)) capacity) # 目標函數(shù)最大化總價值 model.Maximize(sum(values[i] * x[i] for i in range(n))) solver cp_model.CpSolver() status solver.Solve(model) if status in (cp_model.OPTIMAL, cp_model.FEASIBLE): selected [i for i in range(n) if solver.Value(x[i]) 1] print(總價值:, solver.ObjectiveValue()) print(選擇的物品:, selected) else: print(無解)這段代碼很短但已經(jīng)完整走完了 OR-Tools 建模的標準流程創(chuàng)建模型對象、聲明變量、添加約束、定義目標、調(diào)用求解器、讀取結(jié)果。跑完你就能看到在容量 10 的情況下最優(yōu)總價值是 18選擇的物品是索引 0、2、3 這三件。2.3 理解建模三個要素變量、約束、目標很多新手上來就卡在我的業(yè)務怎么轉(zhuǎn)換成變量、約束、目標這步。其實有個套路可循先問自己哪些東西是需要系統(tǒng)替我決定的。選的物品、排班的人、路徑上的點這些都是決策變量。再說約束現(xiàn)實里硬性不能違反的規(guī)則就是約束比如總量不能超載每人每天最多一個班次必須按時交付。最后是目標通常一個量化指標比如最省錢、耗時最短、資源利用最均衡。這個順序全部想清楚再動手寫代碼建模成功率會提高非常多。另外注意 CP-SAT 里的變量是整數(shù)域。背包問題天然用 0/1 變量這個例子剛好體現(xiàn)布爾變量NewBoolVar的用法。實際情況中更多是NewIntVar(low, high, name)來定義整數(shù)區(qū)間的變量。3. 三個高頻實戰(zhàn)場景這樣建模基本不會跑偏3.1 員工排班最難的不是約束是把人的規(guī)則翻譯成數(shù)字模型排班問題我前后做過好幾個版本給某連鎖門店做排班系統(tǒng)時最大的痛苦不是寫求解器而是跟店長梳理規(guī)則。你會發(fā)現(xiàn)現(xiàn)實規(guī)則特別多且碎不能連上兩個夜班、周末盡量少排新人、每個班次必須有一個老員工、休假天數(shù)要動態(tài)變化。翻譯成數(shù)學約束之后代碼反而沒有那么多。下面是我經(jīng)常用來演示的排班模型稍微精簡但保留了核心約束from ortools.sat.python import cp_model num_workers 4 num_days 7 num_shifts 3 # 班次0、1、2 model cp_model.CpModel() shifts {} # w員工, d天, s班次 for w in range(num_workers): for d in range(num_days): for s in range(num_shifts): shifts[(w, d, s)] model.NewBoolVar(fw{w}_dgv5xshg9wyt_s{s}) # 每人每天最多一個班次 for w in range(num_workers): for d in range(num_days): model.Add(sum(shifts[(w, d, s)] for s in range(num_shifts)) 1) # 每天每個班次至少安排一個人 for d in range(num_days): for s in range(num_shifts): model.Add(sum(shifts[(w, d, s)] for w in range(num_workers)) 1) # 每人每周班次數(shù)盡量控制在 2~4 之間 for w in range(num_workers): model.Add(sum(shifts[(w, d, s)] for d in range(num_days) for s in range(num_shifts)) 2) model.Add(sum(shifts[(w, d, s)] for d in range(num_days) for s in range(num_shifts)) 4) solver cp_model.CpSolver() status solver.Solve(model) if status in (cp_model.OPTIMAL, cp_model.FEASIBLE): for d in range(num_days): line f第{d1}天: for s in range(num_shifts): for w in range(num_workers): if solver.Value(shifts[(w, d, s)]) 1: line f班次{s1}員工{w1} print(line) else: print(無解)這個模型沒有目標函數(shù)只求可行解就已經(jīng)能滿足不少小規(guī)模排班需求。如果你想進一步做到公平把每個員工總班次數(shù)盡量均衡定義成 minimize 目標即可。還有更細的約束組合OR-Tools 提供了AddAllowedAssignments、AddAllDifferent、AddExactlyOne這些封裝能很優(yōu)雅地表達復雜規(guī)則。實戰(zhàn)心得是排班問題的建模順序一定是從硬約束開始先讓模型有解再加軟約束和目標函數(shù)。一上來把所有規(guī)則全部塞進去求解器可能直接給你返回一個不可行狀態(tài)到時候你根本分不清是哪條規(guī)則寫錯了。3.2 車輛路徑繞城配送的路線一行回調(diào)函數(shù)就能搞定路徑優(yōu)化是另一個常見的硬骨頭。某物流調(diào)度項目里我有一張真實的城市配送距離表二十多個配送點三臺車每輛車容量還不同。手動排路線基本就是憑借老師傅經(jīng)驗但分完路線之后經(jīng)常出現(xiàn)一輛車超載、另一輛空跑的情況。用 Routing 求解器之后方案質(zhì)量提升非常明顯。最小的 TSP單輛車的旅行商問題代碼如下from ortools.constraint_solver import routing_enums_pb2, pywrapcp distance_matrix [ [0, 2, 9, 10], [1, 0, 6, 4], [15, 7, 0, 8], [6, 3, 12, 0], ] manager pywrapcp.RoutingIndexManager(len(distance_matrix), 1, 0) routing pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): from_node manager.IndexToNode(from_index) to_node manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] transit_callback_index routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) search_parameters pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) solution routing.SolveWithParameters(search_parameters) if solution: index routing.Start(0) route [] while not routing.IsEnd(index): route.append(manager.IndexToNode(index)) index solution.Value(routing.NextVar(index)) route.append(manager.IndexToNode(index)) print(TSP 路線:, route)核心是那個distance_callbackOR-Tools 會反復調(diào)用它來詢問任意兩點之間的代價這個代價不一定是距離也可以是時間、油耗、費用。Routing 模塊把這類指標統(tǒng)稱為代價回調(diào)注冊到模型里就自動參與優(yōu)化計算。多車輛、容量限制、時間窗基本都是在這個結(jié)構(gòu)上疊加維度實現(xiàn)的比如用routing.AddDimension來創(chuàng)建容量或時間維度。這類問題我最想提醒的一點距離矩陣一定要保證正確性。我之前用地圖 API 批量計算時因為部分點之間沒有道路通行直接給了一個極大值當距離結(jié)果求解器把路線硬繞到極遠的地方我還以為模型寫錯了排查半天才發(fā)現(xiàn)是數(shù)據(jù)源問題。先把數(shù)據(jù)清洗干凈再談模型優(yōu)化。3.3 裝箱與資源分配空間和資源其實可以抽象成維度裝箱問題聽起來難但實際上在 OR-Tools 里建模并不復雜。它可以抽象成有一批物品每個有長寬高或重量有若干個箱子每個箱子有容量上限目標是用最少箱子裝完所有物品或者把一個箱子填得更滿。這類問題通常會深度使用 CP-SAT 的區(qū)間變量和可選區(qū)間機制來處理物品與箱子之間的等價關系。不過這里我不想貼太長代碼給你一個建模思路把每個物品放進哪個箱子作為整數(shù)變量范圍為 0 到箱子總數(shù)減一再對每個箱子的總重量、總體積分別建立約束最后把箱子是否使用這個布爾變量設為目標函數(shù)去最小化。在資源分配場景中OR-Tools 還有一個非常實用的抽象叫維度。路由求解器里的容量維度、時間維度本質(zhì)上是給每輛車維護一個沿路線累積的量比如裝了多少貨、走了多久。這個抽象幾乎能覆蓋所有帶累積約束的問題比如外賣配送的保溫箱容量、生產(chǎn)線上的上下料時間。理解了維度你再看它的文檔會豁然開朗。4. 建模時最容易翻車的細節(jié)我替你試過4.1 浮點數(shù)會坑你CP-SAT 只吃整數(shù)這是新手入坑會遇到的第一大坑。CP-SAT 的所有變量和約束都是整數(shù)域它本身不處理浮點數(shù)。如果你在業(yè)務里遇到價格、重量、時間這些帶小數(shù)點的數(shù)據(jù)直接傳給模型會報錯或者結(jié)果被隱式截斷。標準做法是縮放成整數(shù)。比如金額保留兩位小數(shù)就乘以 100 轉(zhuǎn)成分重量精確到克就乘以 1000。縮放比例需要全局一致否則約束關系會失調(diào)。這個轉(zhuǎn)換過程看似簡單但我在項目里吃過虧曾經(jīng)把時間粒度從分調(diào)整成秒時忘了改所有約束里的對應系數(shù)結(jié)果模型算出一堆不可行的路線。所以建議在一開始就把數(shù)據(jù)粒度定義寫清楚建模代碼里統(tǒng)一使用同一個常量系數(shù)。4.2 軟約束和獎勵要怎么揉進目標函數(shù)業(yè)務系統(tǒng)里很多規(guī)則不是絕對的比如盡量讓老員工優(yōu)先休假盡量少用一個箱子。這樣的軟約束不能直接放進硬約束列表里否則模型可能直接被搞到無解。常規(guī)做法是引入懲罰變量或者獎勵變量把違反程度乘上一個懲罰系數(shù)加進目標函數(shù)。目標函數(shù)是一個被最小化或最大化的量所以盡量少用一個箱子就可以寫成minimize(箱子使用數(shù)量 * 成本系數(shù))。這個過程的難點在于系數(shù)怎么定。系數(shù)太小求解器會無視這個懲罰系數(shù)太大又會過度犧牲其他目標。實際調(diào)參時我會先固定一個目標觀察另一個指標的變化幅度然后二分調(diào)整系數(shù)基本幾次就會收斂到可接受的范圍。4.3 求解時間失控怎么限制和判斷組合優(yōu)化在規(guī)模大的時候非常容易求解時間失控。OR-Tools 默認會一直算下去直到證明最優(yōu)這在生產(chǎn)環(huán)境是不能接受的。幾乎所有實戰(zhàn)項目里都要顯式加上時間限制。CP-SAT 的用法是solver.parameters.max_time_in_seconds 10Routing 求解器則是search_parameters.time_limit.seconds 10加了時間限制之后求解器可能在超時前返回一個可行但不保證最優(yōu)的結(jié)果。這時候就要學會看兩個指標ObjectiveValue是當前找到的最好目標值BestObjectiveBound是理論上能夠達到的邊界。兩者越接近說明距離最優(yōu)解越近。如果時間到了但 gap 還很大就說明模型還沒收斂要么加時間要么簡化模型。5. 常見問題與排查思路速查5.1 模型一直解出 0 或空解如果是排班模型這種用布爾變量的場景解出來全是空大概率是約束條件互相沖突。我遇到過有人把每人每天至少一個班次和每人每天最多一個班次同時設成嚴格相等還把班次數(shù)和人數(shù)傳給搞錯了結(jié)果是必然無解。排查辦法也簡單把所有約束先注釋掉只保留一組硬約束跑一次如果還產(chǎn)生結(jié)果再把約束逐個加回來很快能定位到?jīng)_突的那一條。5.2 解有了但不是最優(yōu)而且差得遠出現(xiàn)這個現(xiàn)象的常見原因是目標函數(shù)沒寫對或者沒寫全。比如排班問題里你只寫了可行性約束那求解器給出任何一個可行解就停了你根本不知道它是不是優(yōu)化過。另外還有一個隱蔽坑距離或成本矩陣的單位不一致。某個項目里我有一段距離是公里另一段距離是米模型計算結(jié)果里路線亂繞最終對比實際里程才發(fā)現(xiàn)是單位沒統(tǒng)一。先檢查數(shù)據(jù)的一致性再檢查目標函數(shù)。5.3 規(guī)模一大就跑不動怎么辦如果問題規(guī)模確實很大第一件事是審視模型的對稱性。比如兩個員工能力一致、位置互換解相同這種情況下解空間存在大量對稱解搜索效率極低。解決思路是加對稱破壞約束比如強制員工 A 的班次數(shù)不大于員工 B。第二個手段是給求解器開多線程CP-SAT 支持設置搜索并行度solver.parameters.num_search_workers 8第三招是對問題做降維分解。比如把大片區(qū)拆成若干小片區(qū)分別求解再合并結(jié)果或者先用啟發(fā)式算法產(chǎn)生一個不錯的初始解再交給 OR-Tools 做改進。OR-Tools 里可以通過設置初始解候選來加速收斂。5.4 排查順序和幾個實用技巧把最常見問題的排查順序整理成一張速查表方便你直接對照現(xiàn)象優(yōu)先排查推薦的修復動作無解約束沖突逐條注釋約束定位沖突檢查變量域是否為空結(jié)果全為 0變量未被約束綁定檢查決策變量定義范圍確認布爾變量是否有遺漏約束結(jié)果差得遠目標函數(shù)或數(shù)據(jù)單位錯誤驗證目標表達式統(tǒng)一數(shù)據(jù)縮放系數(shù)求解超時模型規(guī)?；騾?shù)設置不合理加時間限制、開并行、降維或拆分問題結(jié)果不穩(wěn)定初值/隨機種子影響固定隨機種子或增加求解時間還有一個實用技巧CP-SAT 求解后的狀態(tài)碼要會看。OPTIMAL代表已經(jīng)證明最優(yōu)FEASIBLE代表找到了可行解但未證明最優(yōu)INFEASIBLE代表無解。很多人在狀態(tài)碼處理上只看OPTIMAL導致明明有合法排班結(jié)果卻因為狀態(tài)碼不對直接忽略非?？上А?. 它的邊界在哪里什么時候該換更專業(yè)的求解器6.1 哪些問題它搞不定OR-Tools 在離散優(yōu)化領域很強悍但不代表所有優(yōu)化問題都能包打天下。連續(xù)變量為主的問題比如投資組合優(yōu)化、連續(xù)參數(shù)調(diào)優(yōu)它的表現(xiàn)就不夠好。這類問題更適合專業(yè)的線性規(guī)劃或非線性規(guī)劃求解器甚至可以直接用數(shù)值優(yōu)化庫。另外如果問題包含復雜的非線性約束比如乘積形式的約束CP-SAT 的整數(shù)模型很難直接表達需要通過分段線性化等手段重新建模這工作量往往不小。還有個容易被忽視的限制OR-Tools 不擅長處理不確定性優(yōu)化。比如需求不確定的庫存優(yōu)化、概率約束問題它不是為這類隨機優(yōu)化設計的。當你發(fā)現(xiàn)核心業(yè)務邏輯需要大量處理和概率相關的變量就該考慮其他方案了。6.2 和啟發(fā)式算法的配合我不建議把所有問題都丟給一個求解器。實際工程里效果最好的方式往往是 OR-Tools 和啟發(fā)式算法配合。比如先用貪心或遺傳算法得到一個初始解再把初始解作為起點喂給 OR-Tools 去進行局部大鄰域搜索讓它在這個基礎上優(yōu)化。反過來也行先讓 OR-Tools 快速求一個可行解再用專門的鄰域搜索來微調(diào)。OR-Tools 路由模塊本身就內(nèi)置了多種搜索策略你完全可以用自定義啟發(fā)式方法來擾動初始解空間這會讓最終方案質(zhì)量明顯提升。6.3 換個更專業(yè)的求解器說句實話如果你的問題明確是大型混合整數(shù)規(guī)劃比如幾十萬級變量、幾百萬條約束OR-Tools 的開源求解器確實比不過商業(yè)求解器比如高性能商用 MIP 求解器帶來的性能差距是數(shù)量級的。在這個場景下我建議把 OR-Tools 當作原型驗證工具用它快速驗證模型方向是否可行然后切換到商業(yè)求解器做生產(chǎn)級計算。不過絕大部分業(yè)務場景其實沒有到那個量級我做過不少項目變量規(guī)模在幾千到幾萬個之間OR-Tools 的 CP-SAT 表現(xiàn)相當夠用而且免費這個優(yōu)勢讓它成為中小企業(yè)落地的最佳起點。先跑通再優(yōu)化比一開始就上重武器要現(xiàn)實得多。最后分享一點我在多個真實項目里的體感這類工具一定要用一個真實場景完整跑一遍你才會理解建模比求解更重要。變量定義是否清晰、約束里是否悄悄混進了軟規(guī)則、目標函數(shù)是否真正貼合業(yè)務指標這些決定了結(jié)果的可用性。工具再強也替你做不了業(yè)務建模的思考。建議你找一個手頭最常見的排班或路徑問題從最小模型開始一步步加約束很快你就會迷上這種把規(guī)則變成數(shù)學再讓機器替你找答案的感覺。遇到具體的坑歡迎在評論區(qū)和大家交流。