菜鳥網絡算法專家朱禮君：物流優化問題在大數據時代被賦予新的意義? | CCF-GAIR 2017

2017年7月7日至9日，全球人工智能與機器人峰會CCF-GAIR大會在深圳成功舉辦。本次由CCF中國計算機學會主辦、雷鋒網與香港中文大學（深圳）承辦。來自全球30多位頂級院士、近300家AI明星AI企業，齊聚智能科技產業盛會。

菜鳥網絡高級算法專家朱禮君在CCF-GAIR 2017大會上發表了演講，主題是“大數據時代的物流優化問題”，主要講解菜鳥網絡當中的物流發展情況。朱禮君畢業于美國馬里蘭大學，獲得物理學博士學位，先后就職于Goldman Sachs、亞馬遜、Facebook等公司，于2014年回國加入阿里巴巴，領導菜鳥網絡倉配供應鏈的算法團隊。

以下是朱禮君演講速記全文整理，雷鋒網在不改變原意的基礎上做了精編：

我來自菜鳥網絡，我將分享大數據時代的物流優化問題，我們在做物流優化的時候碰到了很多問題。物流其實是一個非常古老的行業，可以說有上千年的歷史，但是在這個大數據時代，我們發現很多傳統的運籌學優化問題，在大數據時代被賦予了很多新意義，我們在這方面做了很多研究，碰到了很多有意思的問題，在運行的過程中也學到了很多的經驗與大家進行分享。

菜鳥網絡是傳統行業和物流行業的融合

首先介紹一下菜鳥網絡，菜鳥網絡是一個物流平臺，協同物流合作伙伴為消費者和商家提供物流服務，包括快遞、倉配網絡、跨境、末端網絡，還有農村物流網絡。值得一提的是這里面很多節點，像倉庫以及配送，最后一公里等，我們用的還是社會上的物流資源，是我們合作伙伴的資源，但是菜鳥網絡在這里面會起到全局優化的作用。

剛才說到我們的一個特點就是傳統行業和物流行業的融合，因為物流行業是一個非常傳統的行業，但是我們是一家互聯網公司，是一家數據公司，所以數據是核心，技術是核心，很多的傳統物流優化的問題在互聯網時代的確是被賦于了很多新的意義，而且在大數據和算法是這里面的核心。

物流優化問題在大數據時代被賦予的新意義

在大數據時代，我們的物流優化問題被賦于了哪些新的意義呢？經過我們的研究發現，首先我們對很多物流優化問題的計算性能要求遠遠大于以前，之前我們不太在乎優化計算資源的使用的，因為以前的優化是今天算了明天再用，現在是實時的，所以對算法有很大的挑戰。

另外，機器學習和人工智能被提到很高的高度，在物流領域以前用的是傳統運籌優化的理論和算法，在大數據時代，這兩者需要得到更好的有機融合。還有一點也是我們最近在研究的方向，就是怎么用機器學習的思想來求解傳統物流優化問題，這也是在學術界上非常有挑戰的一個新的方向，我們在這個過程中也有一些經驗。

物流算法應用案例

下面分享一下我們在菜鳥網絡做過的一些物流算法應用的案例。

第一個問題是供應鏈倉儲配送網絡的優化問題，這是非常傳統的問題，我們有一些客戶在全國或者全世界有一個區域的分布，我們到底要選哪些倉庫布點，把貨囤到哪些倉庫，從供應商那里運到倉庫，最后再運到用戶哪里，這里的核心是我們選擇哪個倉庫，每個倉庫負責哪個區域的用戶，這是傳統的問題。

為什么我們認為在現在這個大數據時代有它的新的意義呢？在阿里的電商平臺上，商家其實都是負責自己的貨，之前他會用自己的倉儲網絡，我們會對每個商家做優化，比如說優化以后，有些貨可以放到菜鳥倉庫里，幫它配送，它會覆蓋一些范圍。

舉個例子，深圳的一個商家以前可能在深圳有倉庫，北京的用戶他就需要遠程發貨，但是菜鳥在北京有倉庫，我們就可以推薦這個商家用我們的倉庫囤在北京附近貨。這里面需要考慮的一些優化的目標非常多。除了成本以外，還會考慮時效，次日達的體驗對用戶來說非常重要，還有鋪貨成本，就是從供應商運到倉庫大概要多少錢，一般我們會用混合規劃的模型來解決這個問題，所以這里面要求非常快，我們專門設計一些算法來解決這個問題，我們有成千上萬的商家，對每個商家都要單獨求解，這樣用傳統優化的算法會有一定的局限性。

當商家選了我們的倉庫之后，我們要告訴他們怎么分倉，我在北京的倉庫要放多少貨，上海的倉庫要放多少貨，這個問題看似簡單，其實不然，就算我根據歷史的數據，用機器學習的模型預測出北京的銷量是多少，上海的銷量是多少，這還是不夠，因為機器學習的模型是有非常多的不確定性因素，它預測的未來銷量會有很大的波動，我們也知道特別在中國的電商會有很多的促銷，這個波動會變得更大，我們如何把這些波動考慮進去，使得我們在一些不確定的環境下，都能保證我補貨的量比較合適，不會有缺貨的情況出現，也不會有滯銷的情況出現。所以要考慮鋪貨的成本、倉儲的成本，然后要考慮周期性補貨，到底是一個星期一次，還是兩個星期一次，還是一個月一次是最優化。最重要的一點是要考慮銷量的波動性，因為銷量非常不穩定。

然后整個補貨量確定之后，我們建立這樣一個模型，用魯棒優化的算法來計算每個倉庫大概要補多少量，這個算法也是對每一件商品、每一個商家都是個性化計算的，所以這也是一個難點。

在倉儲領域，我們知道在倉庫里面，用戶下了訂單以后，倉庫里面會有倉庫的工作人員，在倉庫的貨架走一圈，把用戶下的訂單都揀過來，再打包發給用戶。這里面非常重要的問題就是任務怎么切分和路徑怎么優化。任務切分就是哪個訂單應該派給哪個人，路徑優化是怎么派給這個人，這兩個問題是相互融合的，它是一個類似于車輛路徑規劃的問題。這里面的難點就是，特別是像電商這樣的平臺，訂單是不斷下發的，我們需要知道到底在什么時候我要做一個決定，哪些訂單把它大爆發給一個工作人員，讓他去貨架上揀，所以這是一個需要實時做決策的問題，它對計算性能的要求也非常高，因為倉庫里的工作基本上是連軸轉，中間不會停，因此需要迅速計算出下一個任務到底要發給誰，然后訂單也是不斷下發，這是一個非常動態的問題，所以用一些傳統的運籌優化算法解這種問題比較難。

箱型推薦問題

在倉儲領域還有一個比較有意思的問題，可能大家會覺得這個問題看上去比較簡單，其實不然，就是箱型推薦問題。比如說用戶在這個網站上買了8件商品，一個用戶買8個東西或者10個東西，這是很正常的，這些東西有它的長寬高、重量，我知道我倉庫里備的箱子的大小和它能承重多少，問題是在訂單下發的那一刻，我要知道這些商品要怎么壘，然后放到哪個箱子里，或者最大的箱子也放不下，我要放到哪幾個箱子里，這個問題為什么這么重要呢？如果能一個箱子裝下，它就是一個包裹，而如果我把它分成了兩個包裹，它就會需要兩個包裹運輸，增加了配送的費用，而且這個箱子的包材也有浪費，所以這個算法可以發揮空間很大。這個問題在學術界是一個傳統的三維裝箱問題，這是一個非常難的問題。它的約束是物品累積在一起的時候，它的長寬高不能高于那個箱子的長寬高，這是大家都能想到的約束條件。一般的傳統的做法是用構造性的算法求解，就是我去嘗試各種不同的擺放形式，或者不同的擺放順序，然后我們在這里面需要做一些語言啟發算法，就是把一些啟發式的算法整合起來，做一些分層的算法設計。假設你有100個商品，一個復雜的算法很可能是算不過來，因為我們需要很短的時間內把這個計算出來，在訂單下發的過程中就計算出來，如果你沒有計算出來，后面就會卡住，所以這個算法的挑戰很大。

我們把這個問題解完了以后，后來自己考慮了一下，這里有一個很重要的約束，就是商品累積在一起，它的長寬高不能高于這個箱子的長寬高，然后我們就自己問自己，這個約束是一定要的嗎？其實不然。因為我們可以根據歷史的一些數據來重新分析一下每個倉庫它到底要怎么樣準備它的箱子，這其實是一個新問題，我們提出了一個新的問題，在歷史上，傳統的學術界沒有做過，因為現在電商積累了這么多的商品數據、訂單數據，我知道每一個倉庫發貨的時候，用戶喜歡把什么東西買在一起，然后訂單里面的那些組成的商品成分是什么，它們的長寬高是什么，有一個分布，那個分布我知道，我的確可以從數據的角度反推出來最優的箱子的形狀是什么，然后我們就做了這個事情，這也是一個非常有意思的問題，剛才說到，假設我給定箱子長寬高以后，我要解這個問題，其實是一個非常難的問題。在這里我們根本不能夠用傳統優化算法里面的求梯度，用梯度下降的方法去做，因為你根本算不出它的梯度是什么，所以我們做了一些無梯度的算法。

因為這個問題比較特殊，它對這個箱子的長寬高沒有太多約束，所以我們就可以做一些無梯度的優化算法，把每個箱子的長寬高的參數空間做一些切分，然后看最后總成本的函數大概是多大，然后會平衡全局的搜索和局部的搜索，找到一個最優解，這樣做對成本也是非常大的節約。這里給我們一個啟示，在物流行業很多時候你把一個算法做好了非常好，但是你要找到這里面你可以打破的約束可能更重要。

我們更進一步研究這個問題，因為傳統的優化問題一般用的方法就是運籌學里的一些方法，比如說整數規劃的問題，或者是一些啟發式的算法。但是現在人工智能、深度學習、機器學習都是非常火的領域，的確有一些新的思想可以用在傳統的問題里面。像在機器翻譯這個領域，以前我們用的都是一些傳統的機器學習方法，后來有人提出來用深度神經網絡的方法，用LSTM的網絡結構做機器翻譯，后來也有一些學術上的言怎么把這種LSTM的網絡結構用在解TSP的問題，我們就嘗試了把這種網絡結構用來解箱型推薦的問題。這里面的目標是說，我們要預測商品放進去的時候那個順序到底怎樣，使得它最后的面積最小，這的確是我們要解決的問題。傳統的優化的方法就是不停地去試順序到底是怎么樣的，然后找到一個順序。用機器學習或者深度學習的方法，我就直接預測出那個順序，當然這里面會牽扯到很多數據，我們會用歷史數據，這里輸入的數據是物品的長寬高，輸出的數據是它的順序的數據，中間有一些模型跟機器翻譯的模型網絡結構非常像，當然我們做的時候也是用它的歷史數據訓練，做下來有5%的提升。雖然這個運籌優化還是比較古老的領域，但是在人工智能這個時代，機器學習和深度學習的算法的確可以用。

車輛的路徑規劃問題

在物流這個行業有一個非常重要的問題是車輛的路徑規劃問題。這個問題的定義其實非常簡單，就是我們在地理上有一些需要去服務的點，要配送的包裹，或者是需要攬收的貨物，它在地理上分布在不同地方，我需要從一個總的中心派幾輛車，分別去攬收，或者分別去派送這些貨物或者是包裹，這個問題體現在兩個層面：

第一，怎么派活，哪些點的服務要派給哪輛車，用什么樣的車。

第二，每輛車要怎么走，它的路徑要怎么優化，這個跟倉庫里面的揀貨優化路徑類似，這一大類問題是車輛路徑規劃問題。它有很多變種，比如說CVRP，就是有的車有限重。還有VRPTW，就是它有一個時間窗的約束。還有VRPPD，你去一個地方拿東西，然后再去另一個地方配送。還有一些其他組合，所以問題其實非常多，但是總的框架還是比較類似，無非是說我要派一些車去一些服務點，然后每輛車怎么走，這個問題在數學上抽象起來還算比較清晰。

傳統的方法大概兩類：

第一，有一些精確的解法，這些算法一般在超過100個服務點的時候很難在優先的時間里面解出來；

第二，傳統的算法里面還有很多近似算法，像ALNS、VNS，這些都是流域搜索的算法，還有基因算法。現在的一些比較前沿的研究是如何把這些優化算法與深度學習的一些技巧聯合起來。

我們自己開發了一個車輛路徑規劃非常強大的引擎。因為剛才提到這是物流行業經常出現的問題，我們從算法的層面來說，這里面最重要的一個點是用了機器學習里的一個思想。每一個我要優化的問題它會有不同的約束，比如在農村，約束車的數量不變，如果外賣，可能會有時間窗，所以每一類問題的約束還是多種多樣的，我要是單獨做一個算法還好，但是我要算法適應各種不同的約束，就非常難。而且我們知道機器學習、強化學習里面會有一些自適應的方法，我們會根據這個問題的特殊的結構識別出來我到底要怎么解決這個問題，這里我們用的是比較傳統的Bandit Learning思想，各種問題會有一些不同的解法，有一些算子，我會試一下，看看兩兩交換、三三交換，能不能把這個解做得更好，把一些解做一個變換，看看能不能做得更好。不同的問題，不同的策略會使它更快的收攬，所以我們會去試，比如說這次好，下次會再試一下其他方式，比如說兩兩交換不好，我可以試一下三三交換，這樣算下來，每個個體會找到特定的算子，到底什么樣的算子、算法最優。

我們的應用案例也很多，像一些生鮮配送的應用、農村淘寶、城市門店配送、倉庫揀選路徑優化。應用的場景很多，同一個算法引擎可以用到很多場景中，原因就是因為它有自適應的學習過程。

大數據智能分單

下面分享我們做的大數據智能分單。傳統物流的情況是說我們需要把包裹收上來以后，按照全國的流向去分，比如說我會按北京、上海、廣州流向去分，以前是人在分的，如下圖，有一個人在看快遞地址，然后把它放到對應的口，全國可能有200多個口，人工分揀起來很難。未來我們肯定希望做到自動化，自動化比較重要的一個點就是數據化，首先我們需要把這個地址數據化，然后把它編碼。以前是人工會寫一個碼，我會看這個地址。現在菜鳥電子面單，在商家發貨的時候，會寫上對應的碼，操作員只需要看這個碼就行了，非常方便，因為識別一個碼比識別一個手寫的地址更簡單。

一個地址應該去哪個站點配送呢？快遞公司有多規則去分，比如說深圳福田區的一個網點它到底要服務哪一個區域，它有一些很復雜的規則，這些規則你很難把它數字化，我們用了一個什么樣的方法呢？我們用的是大規模機器學習方法，我不知道你的規則什么樣，也不需要描述，我把它挖過來，這是機器學習的非常簡單的應用，原來你是怎么學習的我不知道，我只要有歷史數據，我就可以通過機器學習的挖掘把它利用出來。這里面會用到一些分詞、地理圍欄的特征，還有規則的特征，我們用大數據的模型學習，最終把訂單都分到它對應的點。

據雷鋒網了解，中國有很多物流提供商、很多快遞公司，也有很多配送公司都有各自的優劣，每個公司在各自的區域優勢不一樣。

如上圖，左邊公司和右邊公司，它的配送的時間有差距，可以看見比如說在北方，右邊那個公司就沒有左邊這個公司好。

一個商家要發貨的時候，它對每一條線路都要做一個選擇，比如說商家如果在杭州，杭州到上海需要誰來發，杭州到廣州、北京、武漢分別用誰來發，下面又有很多的配送公司，這是一個組合優化的問題，我怎么樣對每一條線路，用什么樣的配比分配我的訂單最終最優化，這個事情用人做非常難，而且簡單粗暴，他不會細到每條線路怎么分，但是交給算法來做，就會很精細。我們做了一個引擎，考慮時效、服務、成本等等，把所有的因子考核到一起，求一個最優的分配方案，然后自動地為這個商家提供一個智能發貨的解決方案。

我剛才提到很多算法，我們是一家互聯網公司，以技術為核心，我們希望通過整合社會化物流，提升整個中國的物流水平。積累下來的技術，希望能夠開放，給整個社會上的物流公司使用，能夠提升整個中國社會的物流水平。如路徑規劃的算法的引擎，我們已經在跟多個合作伙伴對接，剛才提到的箱型推薦的算法已經開放出來了，還有地址庫，地址怎么分類，地址的聚合的服務，標準化的服務，還有只能分單的算法，對每個配送公司怎么去分他的訂單，這些算法我們都對外開放，提供給所有物流合作伙伴。以該方式來提升整個中國物流的效率。

未來發展方向

從技術的方面來講，我們覺得未來的發展方向是這樣的：第一點是從Model-driven的方法到Data-driven的方法。剛才說到傳統的物流優化一般用的是運籌優化的模型，運籌優化一般會有一個目標函數，比如成本，然后我有約束，比如當日達訂單比例是多少，這個倉庫訂單不能超過多少，這輛車裝的東西不能超過多少，這些約束列好以后，需要把它求解，這是一個以模型為中心解決問題的方法。

但是在互聯網時代積累了非常多的數據問題。

一類問題可能我們解了很多，它們有一點不一樣，但是有很多地方是一樣的，比如說農村配送，我每天要配送的村點其實不會變，但是它的量會變，所以我昨天求解的路徑規劃和今天求解的路徑規劃應該是有很大的關聯，而傳統的模型驅動的方法，我把這個關聯性就丟掉了，我昨天的解沒有用。我解了同樣的一類問題幾次以后，我應該是可以總結歸納出一些方法，為明天求解同樣的問題或者類似的問題會有幫助，這是采用Data-driven的方法解決問題。我們也用一些深度學習或者是機器學習的方法做這方面的研究，這的確是一個非常讓人激動得方向，它的確是把傳統的領域注入了一些新的活力。

第二類是算法一定要產品化。算法做得再深，不考慮各種各樣的邊角料的情況肯定不行，特別是物流行業，我要應用到實操有很多環節需要不斷地打磨。就像剛才提到的路徑規劃的算法，在運行過程中得到非常多的反饋，那些反饋我們又會加回去。我們把算法平臺化，不會為單獨一個問題解一個算法，因為問題實在太多，單獨為每個問題建模，在可擴展性上會遇到很大問題。剛才也提到大部分的算法已經對外開放，所以未來也會繼續在這方面努力把我們的算法能力，把我們人工智能方面的能力對外開放，提升物流行業的智能化。

雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。