排班最佳化：用Python求解數學規劃，協助商業決策
keywords: #Python #最佳化問題 #數學規劃 #商業決策
疫情之下，你是否曾想過：物流公司是如何安排配送成千上萬的貨物？辛苦的醫護人員是如何排班以照應醫院需求與個人休息？曾經繁忙的航線會如何重新被規劃以適應驟降的旅客人數？事實上，以上問題都屬於「最佳化問題」的範疇，也是影響商業決策重要的一環，而透過數學規劃與程式語言協助求解，我們便可以精準的回答以上問題。
今天我們請課程長品儒介紹何謂最佳化，並以排班問題示範數學規劃如何協助商業決策。
本篇文章 Takeaways
- 最佳化在商業上的應用包含最小化成本與最大化利益等，相關問題從路線規劃到人員排班，包羅萬象地影響著眾多商業決策
- 我們可用數學規劃式設定符合商業情境的要求以解決最佳化問題
- Gurobi是一個支援多種程式語言的數學規劃優化引擎，可以協助我們求解數學規劃（線性規劃、整數規劃…）
- 以Python實作解決排班問題
適合哪些人閱讀
對於數學規劃在商管領域上的影響有所認知、想更進一步了解如何實作的你。
目錄
1. 何謂最佳化？最佳化在商管領域的應用
2. 以排班問題為例：數學規劃如何協助商業決策
3. 總結何謂最佳化？
最佳化在數學上的換句話說，就是最大化或最小化某一函數或變數。
然而，最佳化在商管領域上的意義，卻是遠遠超出最大化與最小化的求解，其背後更代表著例如公司如何以最小成本聘雇、在最短時間完成生產、觸及最多顧客等關乎千萬上億的商業決策。
常見的最佳化問題如物流配送，其中需考量路線規劃與物流中心選址，更進一步也須考量物流中心內各項商品的擺放位置與分類方式，目標希望在最小化運送成本與物流中心設置成本之下，同時也降低倉儲成本、加快配送速度、優化配送路線等。
又如航空公司的航線與人員規劃，要如何安排航線、如何安排眾多機組人員要飛行的航班、如何調配每天航班的起降時間等等，都也是最佳化問題的一部份。
關於最佳化問題，其重要性來自於當基礎的背包問題*擴展至動輒十萬商品、百萬客戶、千萬距離的規模，公司該如何以求解數學規劃協助商業決策，做出最佳資源分配。本篇接下來就將以人員排班最佳化為例，說明從決策目標出發，如何以數學規劃與python，協助計算出輔助商業決策的結果。
*背包問題(Knapsack problem)：在背包限制總重下，該如何在考量不同物品的重量與價值下，選定放入背包中的物品，使得攜帶物品的總價值最高。
最佳化問題：以實際社團幹部排班為例
以下將以DAC幹部排班問題為例，示範最佳化在決策上的應用。
台大資料分析與決策社(DAC)第三屆有14位幹部、本學期有20堂社課。（註：為避免太多細節，本文計算僅取前十堂社課作排班示範）
如果想為社團找到一個排班表，使得在考量每位幹部各自有無法出席的社課之下，每堂社課仍舊安排有一定數量的幹部出席（依不同社課性質，會有不同需求幹部人數），並且每位幹部的出席堂數盡量不要差太多，以平衡每個人的負擔，則我們可以用一個整數規劃(integer program)列式滿足以上條件，並藉由Gurobi（一個數學規劃優化引擎，下面會更詳細示範）協助計算出最佳解，得到以下結果：
數學規劃
要得到平衡幹部負擔與社課需求的排班表，我們首先需要一個符合條件設定的數學規劃式。完整的列式流程，可從(1) 確定變數與參數 開始，接著 (2) 設立要最佳化的目標式並加入需被滿足的限制式：
(1) 確定所需變數：
所需參數：
(2) 列出目標式與限制式：
目標式為最小化每位幹部出席社課數量之間的差距，限制式則是要求出席幹部數需至少達到該堂社課要求之幹部數，同時考量幹部的可出席時段：
以python求解
在有了目標式與限制式後，接著就可以用gurobi協助我們求解以上的整數規劃了！gurobi是一個求解數學規劃的優化引擎，它支援多種程式語言，而以下將使用python示範：
(1) 在python環境中匯入gurobi套件：
(2) 依據不同社課的性質，每堂會有不同的最少幹部需求人數，例如Excel_1代表Excel的第一堂課，因為比較初階、需要相對較少幹部支援，因此安排四位幹部出席即可。其他社課之需求幹部人數依此類推，此段程式碼提供了R_c此參數的資訊。
(3) 因為最後需要安排每位幹部應出席的社課，因此事先調查過大家可出席的時段，呈現如以下excel檔（此為模擬的調查結果）：
將檔案匯入為availability，作為每位幹部可被安排出席的依據，以避免將幹部安排到他無法出席的社課：
(4) 接著就可以使用gurobi model了！以下模型的設定都是根據前面列的數學規劃，再依照gurobi規定的語法輸入，包含加入變數(addVar)、加入限制式(addConstr)、加入目標式(setObjective)等，最後再以optimize進行計算：
首先，以addVar設定變數：
接著根據列式，用addConstr設定限制式：
最後，用setObjective設定目標式：
在以上進行optimize（最佳化）後，gurobi會協助計算這個整數規劃的最佳解，並回傳此整數規劃是否有解與運算時間等資訊。我們便可再透過pandas 或matplotlib等套件，將結果視覺化成為易解讀的版面：（以下程式碼略，僅顯示最後結果）
大功告成！
總結
用DAC幹部社課排班作為示範，說明了最佳化在商管領域上協助決策的實用性：以上做法只要套入實際的幹部可出席時段調查結果、並將社課規模從示範的10堂改為實際的20堂，就可以得出實際可遵循的排班表。而相似的概念也可運用在文章開頭所提及的物流出貨安排、醫護人員排班、航線規劃等問題上，若能借助數學規劃最佳化求解這些問題，相信都將能有效輔助商業決策。
Reference
(1) Gurobi Workforce Scheduling: https://www.gurobi.com/workforce-scheduling/
