王 堃 黃曉旭

華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院 北京 102206

網(wǎng)上超市物流配送問題研究

王 堃 黃曉旭

華北電力大學(xué)經(jīng)濟(jì)與管理學(xué)院 北京 102206

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

物流工程；網(wǎng)上超市；車輛路徑問題

一、引言

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

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

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

二、問題描述

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

三、求解算法

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

（一）遺傳算法

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

（二）鄰域搜索算法

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

（三）算法步驟

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

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

Step2對Z使用領(lǐng)域搜索得到新的Z，在該Z下應(yīng)用遺傳算法，在規(guī)定的迭代次數(shù)下得到新的滿意解和目標(biāo)函數(shù)Hk；

Step3若Hk≤H*，令H*=Hk，轉(zhuǎn)Step 4；否則轉(zhuǎn)Step4；

Step4若k=kmax，則計算結(jié)束，輸出當(dāng)前滿意解；否則令k=k+1，轉(zhuǎn)Step2.

四、結(jié)論

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

[1]王艷瑋,王拖拖,?，摤摚r農(nóng)產(chǎn)品網(wǎng)上超市物流配送模式選擇研究[J]．經(jīng)濟(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．