運籌優化算法工程師現狀「運籌優化就業前景」

科普推廣運籌學一直以來是【運籌OR帷幄】平台的初衷。本次我們邀請到了平台優化板塊的責編團隊的成員，結合各自獨特的業界工作體會，分享他們眼中在業界發光發熱的運籌學。

一、元器件行業中的運籌學

本人在一家做元器件服務的公司實習，軍用元器件使用的時候有兩個典型場景：替代和統型。

替代是設計師針對進口元器件找到可替代的國產型號；統型是在一個產品的BOM內確定某幾個不同元器件是否可以統一使用一種，以此減少元器件品種數。

目前行業內開始從依賴專家經驗（比如知道某個國產元器件就是對標某個進口元器件做的），轉向從元器件性能參數的相似度出發進行判斷，所以涉及到相似度和聚類方法的應用。

相比方法本身，解決問題的更大阻礙是元器件性能參數數據的複雜性和不規範性。例如不同類別的元器件性能參數不同，即使在同一類別下，不同生廠商給出的性能參數形式也不同，對此進行規範需要有元器件專業知識，所以實際中，數據清洗往往耗費最多人力，也是影響方法使用效果的一大因素。

二、電力行業中的運籌學

本人領域是電力系統最優化，可能大家沒有察覺，但是現在中國的電力網絡毫無爭議的走在了世界的最前沿。強如美國，最近也又一次出現了大規模停電問題。（上次是1977年加州大停電）這次美國的停電持續了25個小時，約至少4萬人受到了影響，經濟損失至少3000萬美金以上。但是中國自從普及用電後，從沒發生過如此大規模的停電問題。除了電力人的辛勤奮鬥外，這也離不開運籌學在電力系統中的應用。

眾所周知，我們現在的電力網是交流輸電網絡。交流輸電網絡中的參數遠比直流輸電網絡要複雜得多。最明顯的不同，在交流網絡中我們需要處理線路的有功功率無功功率。除此之外，線路的損耗、輸電節點的電壓和相角也是我們需要考慮的因素。為了保證整個電力系統的損耗最小，我們需要建立相關的數學模型進行分析計算，然後再由調度中心進行調控。但是實際問題的複雜程度遠遠超乎想像，單一個最優潮流問題就是一個大規模非凸非線性的問題。為了求解這類問題，相關學者提出了諸多算法和理論。諸如：半正定規劃、現代內點法、凸鬆弛技術，模型近似技術等。這些理論已經發展了數十年，但即便如此，也沒有一套成熟的理論被應用到實際中。

在電力網中，我們不單要考慮線路損耗的降低，更重要的是要保證供電的可靠性。我們常常需要提前一天或數天對電力系統進行調度安排，這類問題往往是一個多層優化問題，對於這類問題，我們常見的求解辦法是Benders分解和列生成。除此之外，我們需要不定期對線路檢修，發電廠的維護，而線路的通斷、發電廠的啟停在數學模型中又成了一個整數規劃問題。整體的求解難度又上升了一個層次。另外，在國家大規模倡導新能源接入的今天，風電和光伏電站不斷被接入電力網絡中，而新能源不能得到普及的一個重要因素是我們不能準確預知新能源電廠在下一時刻能夠發出多少電能供我們使用。為了分析這類問題，我們的模型在混合整數非線性規划上又需要考慮不確定因素帶來的影響。對這類問題的求解，我們又提出了隨機規劃、魯棒優化、分佈魯棒等。還有一點，我們的輸電線路可能會由於雷擊、樹枝接觸等導致出現輸送功率出現擾動。系統中的這些小擾動可能會對用戶供電的電壓和頻率產生波動，對於普通家庭來說可能影響不大，但是對於一些高精技術的產業，一次電壓或頻率的波動就可能導致整個生產線的崩潰。如何建立相關的數學優化模型來預防這一問題也是當前的研究熱點之一。

最後，大家也十分熟知我們國家有一個西電東送的工程，這也是我認為最困難的一個點，我們國家的電力網絡是連在一起的，是一個十分龐大且複雜的系統，而我們電力網絡是時時波動的，我們需要在秒級做出優化，並給出方案。目前針對這種超大規模的含不確定性的多層混合整數非線性規劃問題，我們沒有辦法在有限的時間內得到一個最優解。

但即便困難重重，在一線的電力工作者仍在盡自己最大的努力來保證電力網絡的安全可靠運行，為中國電力點贊。

三、製造業中的運籌學

本人目前是某廠的算法工程師，參與過企業的排班，調度，決策優化等場景的項目，主要想結合自己的經歷和大家分享一下運籌優化在企業中的一些應用，主要包括任務規劃/排班和實時調度兩個方面，圍繞場景定義，方法論和實際中的困難三個點進行闡述。

任務規劃/排班

場景定義

首先說一下什麼是任務規劃，什麼是排班。任務規劃是基於設定好的任務輸入，進行任務的排期規劃，以達到資源的有效利用和工作效率的提升。任務規劃主要用於傳統製造業/工廠排程，建築工程規劃排程，物流運輸線路任務打包等場景。任務規劃後輸出給虛擬人或者其它虛擬資源創建的帶有時間窗的任務包，排班則基於這些任務包，把它對應到實際的人或者其它真實車輛，機械等資源中，規划出某些資源在什麼時候做什麼任務的結果，以及該任務需要消耗多少其它資源。

方法論

主要的規劃方法也是傳統運籌優化使用的方法。首先了解真實的業務場景，抽象業務規則和約束，搭建數學模型，運用規劃求解器（Cplex，Gurobi等）或者啟發式算法（Local Search，Iterative Forward Search等以及各種變種）進行求解。啟發式算法可以在現有的solver上進行基於不同場景的二次開發，也可以自行開發。業界一般採用第一種方式。

實際運用困難點

在實際場景中，給不同資源的排班會有很多實際因素要考慮。給人排班要考慮人的工作班次時長，人歷史的上班習慣（如習慣上晚班，晚班後不能接早班），人所擁有的技能，個人的偏好（偏好某個工種或者上班時間段），法律規定以及不同工廠因為地域有不同的差異，如香港是8小時工作制，而大陸班次時長可以是10小時等。當我們處理實際問題的時候，先要梳理實際場景，總結管理規律，構建多種配置參數，進行建模。相比於排班來說，任務規劃因為是針對虛擬資源而構建，所以可以不用考慮過多的資源屬性（如人習慣）等因素。

實時調度

場景定義

基於實時數據輸入，進行任務的整合和任務的分配。主要的場景有：O2O外賣即時配送，打車軟件車輛實時調度，倉儲叉車/AGV，分揀中心分揀機械人實時調度等場景。實時調度的場景主要集中於新業務，而非傳統的製造業和實體企業。傳統的製造業和實體企業驕傲於他們的規劃，而前面場景定義所提到的一些新業務場景，無法採用有效地長期規劃手段，更多地是依賴短期的預測和實時的規劃調度。

方法論

上述提到的短期預測：如外賣下單到餐品完成的時間估計，車輛調度Supply和Demand的平衡，倉儲/分揀中心的任務需求預測等，一般基於不同場景搭建機器學習模型，或者各種深度學習模型的Ensemble進行訓練和預測。

實時的規劃調度包括：如外賣下單後分給哪個外賣小哥，車輛訂單來了分給哪輛車，任務需求來了分給哪輛叉車，AGV或者機械人。主要的方法有：

● 短時間壓單後進行任務分配，以犧牲一定的最優性而換來快速高效地計算，採用傳統並行的多個Tabu Search，Simulated Annealing等進行TSP或者VRP的計算。

● 強化學習/動態規劃方法。用收集的數據和規則搭建仿真環境，用強化學習構建任務需求（訂單或者生產入庫需求等）與資源（車輛，外賣效果，叉車等）的匹配價值（Value），然後分配計算。

實際運用困難點

● 大規模訂單/任務需求的計算，需要一定的計算資源支持，以及犧牲算法的優化性來實現快速計算。

● 實時數據的採集。有些數據無法直接有效地採集，比如真實商家做餐時間。

● 如果要搭建仿真環境，也需要了解和抽象實際的業務規則。

關於運籌學在業界應用的思考

我在某公司實習了三個月，主要做的是生產計劃。生產計劃也是屬於供應鏈的一個環節，與調度相比生產計劃的制定要更加宏觀一些。生產計劃就是決策什麼時間，在哪家廠/哪條生產線上，加工多少工件。生產計劃的問題廣泛的存在於製造業中，舉個例子就是是手機的製造，一部手機有上千個零件構成，每個零件都在指定的供應商處生產，例如手機屏幕，手機攝像頭，手機電池，手機充電器每個零件都由不同的生產廠來生產，然後將這些零件運送到最終的組裝廠拼裝成一台成品的手機。如何合理的安排每個廠在什麼時候該生產多少零件是一個需要決策的重要問題。這個問題的核心在於要考慮盡量滿足訂單的需求要降低庫存水位（或者是庫存的周轉率），同時要考慮到物料的約束，產能的約束，運輸的約束等等因素。

在小規模的排產問題中人工調度員還能應對，一旦生產規模變大，生產工藝複雜之後，人工調度的弊病會逐漸凸顯出來。目前國內有意識去做供應鏈的決策模型與算法的並不多，據我所知其中比較有代表性的是杉數科技。

杉數科技智能計劃排程系統致力於為製造業及其上下游產業提供全鏈條技術服務，利用運籌學與機器學習將實際問題轉化為數學模型求解，實現最優化的排程。個人認為，杉數科技在運籌學應用於製造業領域做了很好的探索，在很大程度上解決了如何用更少的人，更短的時間，生產更多的產品問題。

上面提到的生產計劃問題本質上是一個混合整數規劃問題，零件的個數就是一個整數變量，而生產這些零件的物料可能是整數的也可能是連續變量，因此該問題構成了一個混合整數規劃問題。解決方案無非以下兩種：

● 採用經典的混合整數規劃的方法，先對原混合整數規划進行分解和重新建模，例如拉格朗日鬆弛，Benders 分解或者列生成等等方法，子問題的求解可以採用Gurobi或Cplex這些商用求解器。

● 針對問題特性設計元啟發式算法，啟發式算法。

實際運用困難點

我想談談混合整數規劃在業界應用的gap到底在哪裡，當然說大一點的話也是探討運籌學在業應用的gap。

1 實際應用問題往往是大規模的

實際的生產問題往往是大規模的，例如我實習時所面臨的實際問題其決策變量維數都達到上億級別，業務部門要求是2小時之內給出結果，這對算法的效率實際上提出了非常大的挑戰。即使是求解上億規模的線性規劃問題耗時都比較巨大，更不用說是整數規劃問題了。我們經常說線性規劃簡單，哈哈，但是從實際應用的角度來看目前求解線性規劃的速度在一些場景上還是不能滿足我們實際應用的需求的。

目前在學術界大家很多情況下都是在小規模問題上自娛自樂玩一下，所以真正在公司的話，大規模的問題非常非常普遍。舉個例子就是讀運籌學的PhD的時候是學會在游泳池裡游泳，真正在公司裡邊面對的問題可能就是得在大海裡邊游。這其實還是比較好的狀況，更差的情況是一些童鞋可能在學校里只是學會了在浴缸里游泳而已。

2 實際數據往往都是病態的

實際問題的數據往往都是病態的，例如我在公司遇到的問題就是病態問題，具體來說就是優化問題約束或者目標函數的係數數量級的差別過大，導致求解過程的病態，實際問題的數據往往是千差萬別和稀奇古怪的，數量級的差異經常超過10E20以上。這一點在學術界研究的相對較少一點，因為學術界研究的問題都比較理想化，即使有從實際中抽象一些原型出來，但是已經把病態啊這些問題都基本過濾掉了，但是在實際中你就發現病態問題太多了。

3 業務人員沒有優化的意識，運籌優化的人缺乏業務知識，溝通成本非常高

業務人員沒有優化的意識，很多時候他們不清楚運籌優化能做什麼，甚至當運籌優化的算法工程師問題業務人員你們有什麼要求沒（約束條件），你們有什麼量化的指標要越大越好或者越小越好（目標函數），業務人員很多時候也不能很清晰量化的描述出來這些東西，還有很多時候業務人員嘴巴上告訴你的目標函數和心裏想的不一致。就相當於你是一個大廚，什麼線性規劃，拉格朗日鬆弛，列生成，半定規劃，魯棒優化這些菜你都會做，結果來一個顧客說他不知道吃點啥。

運籌學的理論的應用必然還是要有一個實際的背景問題，而不同的問題所處的行業不一樣，每個行業都有自己的習慣自己的一套語言和模式，例如航空業就有很多專業術語，如果做航空優化的話，那麼就要求運籌優化的算法工程師要具備一定的業務基礎，否則你是無法和業務人員交流的，人家說話你都聽不懂，1次2次不懂你可以問，十次八次不懂的話，人家就不愛和你說話了。而且運籌優化算法工程師一般都是作為乙方出現的，很多時候還必須是我們得放低姿態的去主動的接觸業務學習業務才行啊，否則項目就很難進行下去。

4 測試困難，如何驗證優化算法求解結果的正確性

好不容易，經過了重重阻礙，克服千難萬險，我們的優化算法出爐了，我們可以得到一個結果。如何驗證這個結果是正確的呢？其實非常抱歉的告訴你，基本沒啥靠譜的方法去驗證。現在在公司普遍的作法是兩種，1是人為的構造一些類似benchmark的東西，這些東西的最優解比較顯而易見，通過這些benchmark來檢測算法的正確性；2是參考以前人工的經驗來看，算法給出的解是不是合理，例如要是做一個調度算法呢，就找幾個有經驗的調度員來看這個算法是不是接近以前人工調度的結果，如果接近那就認為OK了。很顯然這兩種方法有很多的不足，第一種方法只能適用問題特別簡單的時候，問題稍微複雜一點，規模大點benchmark就很難構造了，第二種方法雖然適用面更寬一些，但是問題也很明顯，那就是以前人工調度的結果很難說是比較好的結果，那這個結果去和算法做對比本來參考系就有問題。

四、電商行業中的運籌學

本人目前在某電商供應鏈計劃部門實習，該電商平台有八個事業部，每個事業部每天都有一定量級的產品上新、下架。目前平台上八大事業部的總商品數量量級是十萬，對接不到2000家供應商。我所在職位的主要工作內容是，根據歷史銷量進行各個產品的需求量預測，由於產品發貨渠道有商家自發貨和平台發貨兩種渠道，選擇平台發貨的廠商需要結合產品的生產周期，並且按照與平台約定的補貨周期將貨物運到平台的自有倉庫。

因此對於平台供應鏈計劃部門來說，需要根據貨物現有庫存，結合日均銷量預測（分大促日銷和平常日銷兩種）實現補貨量和補貨時間點預測自動化，倉庫效益最大化。將預測信息反饋到計劃員和事業部同事進行產品調整。存在的難題有很多，比如對於新品的日銷需求預測？長期在架產品的需求預測及庫存管理實現效益最大化？當某產品的補貨周期是一個月時，涵蓋了大促時期和平銷時期，如何庫存管理和日銷量預測，以實現倉庫效益最大化，平台收益最大，且儘可能縮短斷貨時長？而這些都是運籌學和優化問題。

五、機器學習行業中的運籌學

本人最近在BAT（之一）的北美研究院實習，研究院本身的運作模式算是和本地業務團隊稍有不同，成員多為國內外名校畢業的計算機、統計、數學、運籌學等專業的博士。除了寫paper之外，團隊也需要做能「落地」的業務支持項目（通常和國內的業務部門合作）：如在線視頻網站的推薦算法、二手商品平台的定價算法、新零售門店的多渠道庫存控制算法等。

這些問題首先的一個共性是：海量的數據規模。這些問題對應的業務部門都有專門的數據團隊，每天在公司內部的數據倉庫會定時更新當日的數據（每日的數據量級都是上百TB）。因此，要在此基礎之上，設計實用的優化算法，實際上對經典的運籌學模型和優化算法來說，也是巨大的挑戰。

因此，在目前我注意到的這些業界的實際「優化」業務中，機器學習方法和運籌學模型基本上是要一起使用的。更具體的來說，業界更需要的是「數據驅動」的決策模型。比如，現有的機器學習、深度學習方法帶給我們良好的預測模型，而所謂的決策模型/優化模型便往往可以基於這些預測模型之上。當然，最理想的狀態是能夠將預測和決策這兩個看似分離的步驟結合起來，即，動態地基於預測調整決策，再通過現階段的決策調整之後的預測。關於這點，目前學術界有了很多不錯的理論，但距離工業界的實際「落地」還是有距離的。這或許便是業界當中機器學習和運籌學的未來吧。