王 堃 黃曉旭

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

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

王 堃 黃曉旭

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

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

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

一、引言

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

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

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

二、問題描述

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

三、求解算法

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

（一）遺傳算法

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

（二）鄰域搜索算法

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

（三）算法步驟

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

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

Step2對(duì)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，則計(jì)算結(jié)束，輸出當(dāng)前滿意解；否則令k=k+1，轉(zhuǎn)Step2.

四、結(jié)論

本文考慮網(wǎng)上超市的實(shí)際情況，建立了兩級(jí)車輛路徑問題的優(yōu)化模型，并提出了針對(duì)兩級(jí)車輛路徑問題的協(xié)同優(yōu)化的思想。該模型和思想結(jié)合算法程序及實(shí)際算例分析，將有助于解決網(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．