網上超市物流配送問題研究

王 堃 黃曉旭

華北電力大學經濟與管理學院 北京 102206

網上超市物流配送問題研究

王 堃 黃曉旭

華北電力大學經濟與管理學院 北京 102206

網上超市的物流配送問題是提高企業效率的關鍵。物流配送的優化問題，可以歸結為車輛路徑問題。本文以網上超市的物流配送為背景，對其車輛路徑問題進行研究。本研究對網上超市優化配送路徑、降低配送成本、提高物流管理水平，最終增加企業核心競爭力，具有重要價值。

物流工程；網上超市；車輛路徑問題

一、引言

互聯網自應用以來，就一直以其便利性和及時性獲得大眾的青睞。網上支付的便利化，以及B2C電子商務領域的迅猛發展，使得“網上購物”成為當下社會的一個日常活動。由于采購成本的降低，更多的居民開始把視線投向日常用品的購買，因此專門售賣日常用品和生鮮食品的電子商務網站，即“網上超市”，應運而生。對于如京東、美國亞馬遜這類普通的網上零售商，每個訂單僅包含有2～3件商品。而對于網上超市，平均每個訂單包含7～8種商品、高達16.7件商品。網上超市的這些特性，決定了以往適用于普通網上零售的車輛路徑問題的模型、算法等已無法滿足其實際需要。因此更為復雜、但更貼合網上超市物流配送實際的車輛路徑問題研究就成為了優化網上超市物流配送成本的關鍵。

現有研究主要集中于對網上超市產品的經濟性的評價，以網上超市為應用背景的物流配送車輛路徑問題的研究較少。近些年國外相關的研究有很多，較為相關的是Sch?nberger等人研究了一個只配送兩種商品的CVRP，即將兩個單獨的VRP問題通過一個約束結合在一起，解決了一個包含有36個客戶的問題，并針對不同的約束情況進行了對比試驗，其結果表明其所采用的約束不影響配送路線的選擇，而只影響配送的調度。

對兩個車輛路徑問題進行建模時，不僅要考慮單級車輛路徑問題中的優化問題，還要考慮兩個車輛路徑問題的整體優化效果，因此其建模和求解過程將十分復雜。網上超市的特征更加劇了其物流配送的求解難度。已有的車輛路徑問題的模型、算法等已無法滿足其實際需要。需要提出一套適用于求解網上超市物流配送問題的方法，降低物流配送成本，提高訂單履行效率。

二、問題描述

不同于傳統的物流配送問題，對于網上超市而言，由于其訂單中的商品種類多、數量大，是否對客戶的訂單進行拆分、在哪個階段進行拆分對模型的建立及求解極為重要。考慮到拆分訂單后多次配送會對客戶的體驗造成負面影響，同時客戶對送貨時間也存在要求，因此，網上超市物流配送問題實際上研究的是兩個帶時間窗及容量限制的車輛路徑問題。問題可定義為：一個配送中心需要在指定的時間段內通過附近的中轉站對多個客戶進行送貨，單個客戶的需求量小于車載容量，供貨點和中轉站之間（第一級配送）在進行物流配送時允許對客戶的訂單進行拆分，而中轉站到客戶之間（第二級配送）在配送時不允許對訂單進行拆分，不同的配送階段所采用的車輛的容量不同，部分客戶對送貨時間存在要求，超過該要求顧客將拒絕收貨。優化的目標是在滿足車載容量的限制條件和顧客的硬時間窗要求下，以最小的成本進行配送。

三、求解算法

大型網上超市的應用背景，決定了本研究中的兩個車輛路徑問題的集成優化與其他兩級車輛路徑問題的研究相比難度很大。需要對客戶點進行聚類，以縮減求解規模；分析兩級車輛路徑方案形成的規律，實現基于計算機的車輛路徑方案的快速生成；構造高質量算法，對大規模車輛路徑問題進行快速求解。

（一）遺傳算法

遺傳算法（Genetic Algorithm）是由Holland在1975年提出來，并首先由Lawrence J. Fogel應用于求解車輛路徑問題的。遺傳算法主要是模仿生物進化的過程，將初始可行解二進制化為所謂“基因”，并利用遺傳和變異的思想對解進行優化。遺傳算法是一種比較經典的智能優化算法，由于其收斂速度快而局部搜索能力弱，因此通常用來和其他局部搜索快的方法如禁忌搜索算法等相結合。

（二）鄰域搜索算法

鄰域搜索算法是一種經典的啟發式算法，該算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。鄰域搜索算法簡單、靈活及易于實現，常被應用于計算機科學（主要是人工智能）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

（三）算法步驟

初始解的確定對于啟發式算法具有極重要的意義。好的初始解可以減少算法在尋路過程中所消耗的時間，提高在規定時間內滿意解的質量。對于一般的模型，初始解的生成常采用隨機生成的方法。然而，對于帶時間窗的問題來說，隨機生成的解通常無法成為可行解。在實際的物流配送過程中，存在著一些彈性較好的配送路線，這些路線可以在時間緊張或遇突發情況時保證配送的效率。本文結合實際情況，根據現有的一般配送路線對模型進行優化，可以大幅提高算法的效率。

Step1輸入初始解{X,Y,Z}，并計算該情況下的目標函數H*，令k=0；

Step2對Z使用領域搜索得到新的Z，在該Z下應用遺傳算法，在規定的迭代次數下得到新的滿意解和目標函數Hk；

Step3若Hk≤H*，令H*=Hk，轉Step 4；否則轉Step4；

Step4若k=kmax，則計算結束，輸出當前滿意解；否則令k=k+1，轉Step2.

四、結論

本文考慮網上超市的實際情況，建立了兩級車輛路徑問題的優化模型，并提出了針對兩級車輛路徑問題的協同優化的思想。該模型和思想結合算法程序及實際算例分析，將有助于解決網上超市物流配送成本難題，幫助網上超市企業更好更快發展。

[1]王艷瑋,王拖拖,常瑩瑩．生鮮農產品網上超市物流配送模式選擇研究[J]．經濟與管理, 2013, 4: 69–74．

[2]SCH?NBERGER J． The Two-Commodity Capacitated Vehicle Routing Problem with Synchronization[J]． IFACPapersOnLine, Elsevier Ltd．, 2015, 48(3): 168–173．