運籌學專家葉蔭宇：優化演算法如何改變決策方式？

機器之心整理

參與：杜夏德

運籌學的歷史比 AI 和機器學習更悠久，但 AI 與機器學習又為它提供了一種機會，很多頂層的東西都是要靠優化，不管是學習還是剛才講到的決策問題，都要有 OR (運籌學)的結合。

作為優化演算法的基礎，運籌學在第二次世界大戰期間因英美兩國配置資源的需求而發展起來。近些年，隨著數據量大幅度攀升等科技環境的變化，運籌學得以快速發展，並廣泛應用於零售、金融、物流等行業。正如運籌學頂級專家葉蔭宇所說，運籌學的歷史比 AI 和機器學習更悠久，但 AI 與機器學習又為它提供了一種機會，很多頂層的東西都是要靠優化，不管是學習還是剛才講到的決策問題，都要有 OR (運籌學)的結合。

從葉蔭宇以《優化演算法的思想及應用》為題的一次演講中，我們可以了解到運籌學如何應用於物流選址及路徑優化、庫存管理、投資組合優化。以下是經過編輯整理而成的演講內容：

葉蔭宇，是斯坦福大學李國鼎工程講座教授（K. T. Li Chair Professor），優化領域基石演算法之一——內點演算法的奠基人之一，他曾獲得美國運籌與管理學會馮·諾依曼理論獎，也是迄今為止唯一獲得此獎的華人學者。目前，葉蔭宇擔任優化軟體公司 MOSEK 科技顧問委員會主席、杉數科技的首席科學顧問。

1982 年，我剛到美國讀書，AI 非常熱，但那時候就要搞所謂的專家系統 AI 空間，學的語言是 Lisp，數據也不多，很多東西沒法總結，AI 就慢慢冷下去了。我比較喜歡數學，就開始了運籌學的研究。

運籌學是一種研究優化的學問，就是研究如何在實際生活中，把事情做到極值，找到最優解，而不是簡單找一個可行的方案。

數學家歐拉說過，Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear（筆者譯：宇宙中，沒有最大值或最小值的事物是不存在的）。這種理論是基於自然形成的，也是在所謂的一個平衡，也是能量函數到了極值。

那時候還沒有計算機，數學不接地氣，無法落到實地，無法真正應用到人們生活中，產生一些影響。於是數學家們就開始尋求落地的方案。也有一些其他的緊迫因素促使運籌學的誕生，二戰時，兩軍交戰，需要研究盟軍配置，其中包括一些博弈問題。

1947 年，美國數學家 George Dantzig 提出線性優化的單純形法，是優化中最經典的演算法，具有里程碑意義。之後運用到經濟學中後，運籌學得到快速發展，特別是計算機的高速發展，以前遇到結構問題，可能要 1 小時，現在可能不到1秒就可以解出來，這裡面有硬體的控制，也有演算法的提高。運籌學的歷史比 AI 和機器學習要老，但是 AI 和機器學習又提供了一種機會，很多頂層的東西都是要靠優化，不管是學習還是剛才講到的決策問題，都要有 OR (運籌學)的結合。

整體來說，所謂優化，是滿足一定的約束條件下，使某一個函數最大。怎麼把一個問題變成這個優化問題，就需要建模。一般是從建模到求解，再到決策，這就需要一套演算法來求解。

在這個裡面，把實際問題變成數學問題，變成優化問題，然後來求解。什麼叫大數據，有很多不同的解釋。而數據大到一定程度後，就可以量化了，量化以後，我們可以用數學的方程、公式來描述它，然後變成一個量化的決策問題。

1982 年我去美國時 AI 很火，後來沉寂了，現在又紅起來。但是優化一直都在那裡，各行各業都需要它，在這點上，它像統計、數學。

在大數據時代的商務決策中，要用到計算機、信息學，包括機器學習，數據搜集，然後我們要通過機器學習做一些規律性分析，然後就是建模、決策。這裡面需要有一些量化、需求管理、規律性分析，我覺得機器學習確實做的好。但是在決策中有一些很傳統的優化模型和運籌學的模型。

舉幾個簡單的例子，為什麼有些決策模型並不需要深刻的理解就可以得出來。

一、物流選址及路徑優化

比如說選址問題，尋求一個區域內最優的倉庫，成本最少，每個庫建在什麼地方，這裡面要權衡很多問題，一次建設費多少，服務區域有多大，如果區域大了，運輸成本就高了，這裡就是數學規劃的問題。

那麼怎麼選才好？以前，我把它寫成一個整數規劃，然後去算，有些演算法，幾個月都算不出解來，但是客戶有很多需求都是有時限的。現在把它看成是一張網路，就要把這個點放在上面，進行隨時的調配，重新選址，這個時候我的演算法就非常的快，然後就會有很多的近似演算法。這裡面的演算法，選址的問題，我們在與客戶合作的過程中有很多這樣的問題。

另一個問題更複雜一點，選一個倉庫提供一個區域服務，叫 hub 的選址。有些物品不是從倉庫發到某一個顧客上，而是要經過中轉站，再到顧客上。那麼這個中轉站怎麼選才好。通常我們把選址的問題，叫作戰略性的決策，一旦選了以後，幾年都不會變。決策也分為戰略決策，戰術決策、operation 決策，而我這裡談的是 operation 決策，我現在要送貨，送到這麼多的點上，如何把貨都送出去，然後回到出發的地點，最終要使整個距離最小，這叫「旅行商問題」，也是很經典的確定性問題。

在實際中，也叫車輛調度問題。當然現實問題比這更複雜，因為可能有一輛車不能跑了，幾千上萬輛車，每輛車跑哪些地點，哪些區域，又怎麼選址，還要考慮取貨和同時送貨，取貨必須要保證某一個時間點或者時間窗口。這是運籌學比較擅長的問題，要實時低解決這些問題。

比如我現在有 5 輛車，要服務這個區域。首先建立一個服務區的概念，怎麼把這個大的區域分成 50 分點，每一個區域選擇一個分點，這叫「區域選擇」。在分這個區域的時候，我要知道每個區域的工作量都是多少，盡量分的均勻，要不然一個區域很大，跑兩天跑不完，一個小區域半天就跑完了。

我的一個學生在和杉數在一起研究，怎麼把區域所有的工作量都分得一樣，每個給的這個點就是車的出發點，可以很快的劃分出來，在作一些路線規劃。

這張圖裡面有 50 輛車，需要找路徑，這是一個實際問題。每一條街道都要跑，我在劃分這個區域的時候，每個區域里街道的總長度是基本上相似的。在跑這個區域的時候，怎麼跑到最大，把所有的街道都跑一趟，這就是路徑問題，這是地圖公司需要考慮的。

大家肯定用過 GPS ，其中有兩個核心技術，一個是衛星定位，經度緯度定位以後。剩下所有的地理信息位置，都是搜集過來的，但是街道的地理數據不斷在變，所以每次都要把街道的信息更新都要重新搜集進來，派一輛車把每個街道跑一遍。這個時候要把城市的街道都跑一遍的話，不可能跑一輛車，可能需要 50 輛車。那麼怎麼劃分這個車輛的區域，以前是用郵政編碼來分，由於城市區域的改變，有些郵政編碼覆蓋的區域大好幾倍，這樣分就不合理，所以要根據瞬時情況進行分析。如何判斷有效，比如原來要用 75 輛車現在 60 輛就夠了，原來用 2 天時間現在一天半就夠了，這個技術，諾基亞在全世界 26 個國家使用。

我原來認為我刨出來最後的路程最短，後來又提出一個要求，在排路徑的時候，盡量向右轉。因為左轉所要花的時間，比向右轉高出 5 到 10 倍，最後我們用運籌學的辦法把這個解決了。

再舉一個路徑優化的問題，大家都在搞所謂的無人倉，有一些小車搬運載有貨物的托盤到空閑工作台，然後小車搬運托盤從工作台回到倉庫空儲位，這叫回庫，然後小車搬運空托盤從工作台到托盤迴收處，叫回收，這裡面都是一些貨櫃，怎麼拖起來怎麼用，就需要路徑規劃和協調。

在國內，研究機器人，研究的比較多的是提高每個機器人自身的能力，做的非常好。但是在很多問題上，缺少通盤調配和安排。單個機器人能力很強，但是在一個團隊中時就不一定了。我們比較缺乏統籌的軟體決策系統。我們很注重個人能力的提高，但是期缺乏一種集體的統籌的決策開發。每個機器人都在瞎跑，這樣肯定不行，無人車也是。

很多公司都在考慮無人車的技術多強，但是其實最主要的問題是什麼，反而是無人車之間的協調、調配和統一指揮。

比如說這是工作台，某一個區域的貨來了以後，要進行分擔，這裡面有很多問題，比如路徑問題。從設計上來說，是設計成單行線還是雙程線，如果設置單行線，跑的距離要長，碰撞的可能性就少一些，這裡面都可以通過優化來解決。比如杉數與京東 618 活動的物流倉統籌調配合作，其中的演算法也都是算出來的。

這裡面是三配，機器人怎麼配到貨櫃，怎麼收檢這個站。目前的方法是用機器人用托盤拖這個貨櫃，把整個的貨櫃拖到旁邊的這個台上，然後又把這個拿下來，再把托盤送回去。首先是機器人，把整個的貨櫃拖起來，可能那個貨櫃員就檢一個東西下來。那麼為什麼貨櫃不動，讓貨櫃員坐在機器身上然後去檢貨呢？因為這樣貨櫃可以裝的更高了，空間利用率更高了。而且人坐在這個機器上，不僅可以前後移動，還可以升降貨櫃，放的更高，運行過程中形成三位的倉庫而不是平面的倉庫，這樣我們就可以計算出來，貨的密度增加多少，倉庫的利用率可以增加多少。在中國，人力相對比較便宜，但是房子非常貴，這樣就能更加節省成本，但是整個也是靠產品運輸來優化問題進行求解。

工業界總是覺得我們需要深度學習、機器學習，需要把預測的精度再提高 1%，卻忽略了測不準的這個定理，精度到一定程度就不可能再提高了。所以在測不準的情況下，在決策上是不是可以做點工作，在知道測不準，可能有不同狀況出現的情況下，決策是不是可以調整一下。比如說，可以保證我在期望值省時一些，但是我保證永遠不會破產，防備那些惡性大事件發生。所以這些模型在 OR 應用到很多的。比如說今天給到這個送貨員的送貨任務有 10 單，我們做了一個輔助工具 PonyPlus ，可以幫助送貨員如果選擇送貨路徑。

二、庫存管理

這裡面最典型的是庫存問題，就是典型的知道你測不準，我怎麼能夠把局測做到最好，把庫存做到最好。以前早的時候還沒有深度學習，比如你是小零售商，你進貨進多少，進一個星期的貨，但是不知道這個星期有多少，多的有多的損失，少的有少的損失。所以這個時候運籌學就有一套方法來處理這個問題。

比如你是小零售商，一個星期要進多少貨，進多了，有多的損失，進少了，有少的損失。

這個時候運籌學就有一套方法來處理這個問題。最近，美聯航因為機票賣多了，有人上了飛機後被拖下去。這是典型的不確定環境下的決策問題，飛機上座位是固定的 300 個，你事先只賣 300 張票，不會賣多，來的人都可以登記，問題是總有 5 %到 10 %的人，因為各種各樣的原因是不會來的。所以航空公司一般都會多賣一點。最好的情況是不來的人數正好是我多賣的人數。但是這個人數永遠是測不準的，也就出現了美聯航的這個問題。

這類問題也出現在很多電商中。通常周轉率在 29 天的，那麼現在降 16.5%，庫存的金額大家也都知道零售商最怕的就是庫存周轉率太低，買了人家的東西自己又賣不出去，庫存金額降 19.2%，現貨率提升了，GMV 上升 1.9%，而周轉天數下降到 24.4 天。就是說我們主要是降低了這部分人力，在不損失這兩個標準的情況下。

還有一個辦法根據某一個電商的特點，叫閃購，出一份貨賣一個星期就不賣了，此時電商把那個星期的預測，需要備多少貨就決定下來。我們採取兩階段的策略，首先我有一個總的估量，但是我發貨的時候是發三天的貨，通過第一天的銷量我再決定追不追貨，本來一周的需求量是 100 件，我實際送到前沿倉庫的是 60 件，我是否需要把這 40 件補上去就看第一天的銷量，第一天的銷量對後續的預測度更高。

杉數的一個產品經理設計了一個叫 StockGo 的智能庫存決策系統。我們覺得應該給每一個中小電商，至少提供一個可能的工具，觀察庫存的這個周轉，幫助他決策，這裡面有很多的功能，比如說對目前庫存狀態的量化評估，對高精度的銷量預測，高精度的補貨策略，供應鏈管理的智能化轉型，這裡面包括很多機器學習和深度學習的工具，對你的庫存狀態進行評估，精確到每一個 SKU，還有補貨策略，以及個性化的全雲端的解決方案，也可以直接把數據傳送到杉數，然後幫你進行診脈。

總的目的是把這些 OR 的東西應用到經濟中。很多 ERP（企業資源應用系統）的公司用了這個系統後，通常周轉率會提高到 50%，資金及人力成本降低，電商自動化庫存能力也都提高，這樣一個小工具，能夠為廣大的小電商服務。你也可以自己調整，但是至少給了你一個可能性。

三、投資組合優化

我最近還研究一些投資組合，也就是防範風險。

美國有一位經濟學家 Harry M. Markowitz ，他有一個著名的理論叫現代投資前沿理論。他把投資組合的問題寫成一個二代規劃，其目標函數不是線性函數，而是二次函數，所有的約束也都是線性的，如何最快的解這個問題解？這個時候我們就有很多的問題，那麼這個模型中為什麼出現了二次函數？在統計中，二次的X的平方通常描述的是變化量，通常需要波動不太大，這就是簡單的這個二次函數，實際上要解的也就是二次規劃，常見的軟體Barra、Axioma、ITG、Mosek。

現在，華爾街搞風險控制的都是用二次模型，用的求解器也就使用的 Mosek 。那麼在交易過程當中，你的演算法你的求解器比別人家快一些，我個人認為高頻交易的競賽也就是演算法速度的競賽。我知道國內就有用到過這樣的模型，自己解需要解 10 秒鐘的時間。從 10 秒到 0.04 秒，這裡面有演算法的模型。

FICO（ FICO 信用分是由美國個人消費信用評估公司開發出的一種個人信用評級法）也是二次規劃的問題，很多很多大數據公司，越來越重視優化。美國最早的大數據公司就是產生 FICO 的一家公司，國內是叫徵信打分，最早的是一家公司把個人所有的信息收集起來給這個人的信譽打一個分。到美國租房要擔保，首先就是看這個 FICO 分。

這個公司後來做的很好，大家都用他的 FICO 。包括在網上查一查這個徵信也都要交錢，這是美國很早的大數據公司，收集很多公司對每個人也都有打分。

運通公司是一個純信用卡公司，實際上是一個擔保公司。我總跟人家講運通公司是合法的高利貸公司，利率確實比較高。那麼他的核心技術就是防範風險，希望你消費但又希望你不要還錢而且希望你還錢不要還得太快，但是又不希望你永遠不還。運通公司有一個專門的團隊從事相關工作。

我當時團隊幫運通公司搞了一個怎麼追債軟體，很多是基於演算法的。國內公司做這種 AI 軟體的非常熱。中國的文化也比較適合。

為什麼？因為在中國，數據公開是比較自由的，像美國大公司數據絕對不會給你的，所以我覺得這種公開自由為 AI 開闢了很多前途。

但是中國公司在發展過程中忽略了演算法的力量，他們通常是以問題為根本，找了一些參考資料，在開源軟體中找一個演算法進行試一試。這是要花非常大的這個功夫，確實是要耐得住寂寞，但是要用人家的開源軟體，人家不給源代碼，就永遠會被牽著鼻子走。我知道其實他們很需要線性規劃或者說其他的運營規劃。但是你要買別家公司的，出於安全考慮也不太妥當。

現在有很多公司比如 CPLEX ，Mosek ，還有些大學，不光是做實際應用，也培養自己的演算法開發，這樣就比較有核心技術了。真正的成為技術公司而不是諮詢公司。所以投資要耐得住寂寞，要有核心的技術。

未來，AI、深度學習和機器學習提供了很多的支撐，模型規模也飛速增長，需要超大規模的優化演算法。以前我認為就要搞出個萬能的演算法，解所有的線性規劃都要解得快，但是我後來反觀看 AI 和人的思維並非是通用的，他是非常定製的，我可以什麼方法對某一類方法用的好就用那個方法，不是追求某一個統一的演算法，或者類別法。反而是比較定製化的，用中國化來講比較實用主義一些。不一定追求理論上的完美，有一個統一的演算法，所以這點上，我覺得反過來，AI 對運籌學會有很大的促進，什麼問題需要什麼樣的演算法，本身需要學習的過程。

還有一個問題，我們以前比較重視凸劃，但是大量的問題是非凸規劃。現在需要考慮集群化，軟硬體結合，如何利用 GPU 實現並行運算，包括應用在智慧供應鏈、智能金融、健康管理等領域。比如挂號系統，有很多很多的問題能不能採取更好的方法，這個方法在 OR中叫排序。

總的來說，我一直在研究運籌學和優化。從 1982 年到現在，大半輩子看到學術研究的起伏變化。我原來比較重視理論，很多問題都是寫文章，證明一些東西，也小有成就，但是人到年紀大的時候會覺得最大的利益還是對一般人生活產生一些影響。不光是有一定的學術造詣，把自己的學術成果轉化成技術，對人的基本生活產生影響，這才是 OR 的本質，OR 是一個接地氣的科學，是一個落地的科學，怎麼落地，需要經過我們的試驗，像深度學習、機器學習這些技術也確實對物流業產生一些影響。我希望通過我們的努力，促使中國的企業，能從一個比較粗狂的形式進一步拓展為依賴於大數據、國際技術來進行決策的環境裡面。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！