王長(zhǎng)瓊，王艷麗，邱 杰，曹乜蜻，劉曉宇

（武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063）

1 引言

隨著互聯(lián)網(wǎng)的普及，電子商務(wù)隨之快速發(fā)展，相比于傳統(tǒng)的物流配送，電子商務(wù)配送的配送網(wǎng)點(diǎn)位置分散、配送物品大小各異、配送服務(wù)時(shí)間要求也更加嚴(yán)格。傳統(tǒng)物流配送VRP（Vehicle Routing Problem）問題中的單配送中心車輛調(diào)度問題已經(jīng)被證明是NP難題，多配送中心車輛調(diào)度問題使本來就具有NP復(fù)雜性的調(diào)度問題的求解更增添了難度。因此，對(duì)電子商務(wù)環(huán)境下多配送中心VRP問題的研究具有更重要的現(xiàn)實(shí)意義。Yu B，Yang ZZ，Yao BZ采用蟻群和禁忌搜索的混合算法對(duì)帶有硬時(shí)間窗約束的車輛調(diào)度問題進(jìn)行求解[1]。郭森、秦貴和等采用改進(jìn)的粒子群算法對(duì)多目標(biāo)車輛路徑問題進(jìn)行了求解[2]。殷胭，葉春明采用聚類分析最短距離分配法將多配送中心車輛調(diào)度問題分解為多個(gè)單配送中心車輛調(diào)度問題進(jìn)行求解[3]。金濤、葉勇等分別采用改進(jìn)差分進(jìn)化算法和狼群算法對(duì)多配送中心的車輛調(diào)度問題進(jìn)行了求解[4-5]。在電子商務(wù)配送方面，楊浩熊、李金丹等采用聚類分析法劃分配送區(qū)域，建立電子商務(wù)環(huán)境下的VRPTW模型，并用遺傳算法進(jìn)行求解[6]。覃運(yùn)梅、毛海軍等提出了基于自動(dòng)快遞機(jī)的快遞配送新模式，采用元胞遺傳算法對(duì)該優(yōu)化模型進(jìn)行求解[7]。

目前，關(guān)于電商配送的VRP問題的研究雖已成為學(xué)術(shù)界研究的熱點(diǎn)問題，但大多數(shù)研究為單配送中心問題，關(guān)于多配送中心問題的研究主要集中在將各個(gè)客戶需求點(diǎn)固定地劃分給每個(gè)配送中心，從而將多配送中心問題轉(zhuǎn)化為多個(gè)單配送中心問題。除此之外，在對(duì)配送車輛的載重量進(jìn)行約束的基礎(chǔ)上融入對(duì)車輛體積約束的研究也相對(duì)較少。為了使電商配送VRP問題的模型更接近實(shí)際情況，本文建立了一種基于TLV三維約束的多配送中心車輛路徑優(yōu)化模型，該模型根據(jù)具體的配送任務(wù)，動(dòng)態(tài)的將客戶劃分給不同的配送中心，并利用遺傳算法對(duì)該模型進(jìn)行求解。

2 問題描述

電子商務(wù)配送呈現(xiàn)出新的特點(diǎn)，配送物品主要針對(duì)的是快遞包裹，而快遞包裹的重量和體積都存在明顯的差異。另外，配送網(wǎng)點(diǎn)位置分散，配送時(shí)間要求更加嚴(yán)格。因此電商配送中的VRP問題可具體描述如下：

假設(shè)某區(qū)域有多個(gè)配送中心，為該區(qū)域內(nèi)多個(gè)快遞網(wǎng)點(diǎn)進(jìn)行配送。根據(jù)不同的配送任務(wù)，每個(gè)快遞網(wǎng)點(diǎn)可被任意一個(gè)配送中心服務(wù)。各快遞網(wǎng)點(diǎn)的坐標(biāo)位置已知、快遞大小件需求量已知，且有時(shí)間窗要求，各配送中心坐標(biāo)已知，有多臺(tái)車完成配送服務(wù)，配送車輛在時(shí)間窗外抵達(dá)快遞網(wǎng)點(diǎn)都須支付一定的懲罰費(fèi)用，在每個(gè)快遞網(wǎng)點(diǎn)都需要一定的卸車時(shí)間，配送過程中每輛車的快遞總量不得超過車輛的載重和額定容積。每輛車只執(zhí)行一次配送任務(wù)，一個(gè)快遞網(wǎng)點(diǎn)僅能由一輛車服務(wù)一次，每輛車從某一配送中心出發(fā)，配送完成后必須返回該配送中心。

需要解決的問題是：如何合理地部署各配送中心的車輛，安排各車輛的配送路徑，盡量滿足各快遞網(wǎng)點(diǎn)的需求和時(shí)間窗限制，并使總配送成本最低。

3 模型構(gòu)建

3.1 模型假設(shè)

為了便于問題的描述和構(gòu)建相應(yīng)的數(shù)學(xué)模型，針對(duì)該多配送中心三維約束模型提出了如下假設(shè)條件：

（1）配送區(qū)域內(nèi)，每個(gè)配送中心至少服務(wù)一個(gè)快遞網(wǎng)點(diǎn)。

（2）所有配送車輛同一車型，載重量和額定容積已知。

（3）單個(gè)快遞網(wǎng)點(diǎn)的需求量不大于車輛的裝載量，每個(gè)快遞網(wǎng)點(diǎn)可以由任意配送中心的車輛進(jìn)行配送。

（4）一個(gè)快遞網(wǎng)點(diǎn)的貨物只能由一輛車完成，且所有客戶都應(yīng)該得到服務(wù)。

（5）其他假設(shè)：道路通暢，貨物在運(yùn)輸途中不會(huì)變質(zhì)損壞。

3.2 符號(hào)說明

Kh：每個(gè)配送中心的車輛數(shù)；

Phk：每臺(tái)車輛的載重量；

Bhk：每臺(tái)車輛的額定容積；

Qhi：第h個(gè)配送中心服務(wù)的第i個(gè)客戶的大件快遞需求量；

qhi：第h個(gè)配送中心服務(wù)的第i個(gè)客戶的小件快遞需求量；

[ahi,bhi]：要求貨物送到的時(shí)間范圍；

a1，a2：每件小件快遞和大件快遞的重量；

c1，c2：每件小件快遞和大件快遞的體積；

dij：客戶i到j(luò)的距離；

nhk：第h個(gè)配送中心第k臺(tái)車輛配送的客戶數(shù)（nhk=0表示未使用第k臺(tái)車輛）；

Rhk：第h個(gè)區(qū)域中的第k條路徑；

rhki：客戶rhki在第h個(gè)區(qū)域中的路徑k中的順序?yàn)閕（不包括配送中心）；

Shi：車輛到達(dá)客戶i的時(shí)刻；

thi：車輛在客戶i的等待時(shí)間；

ta：在每個(gè)客戶點(diǎn)的卸車時(shí)間；

tij：配送車輛從客戶i到j(luò)的旅行時(shí)間；

w1,w2,w3,w4：分別為單位運(yùn)輸成本、早于時(shí)間窗到的懲罰成本、晚于時(shí)間窗到的懲罰成本、單位固定車輛成本。

3.3 模型建立

（1）目標(biāo)函數(shù)。以運(yùn)輸距離最短、時(shí)間成本最小、車輛使用成本最小為目標(biāo)函數(shù)。即：

式（2）保證每條路徑上各快遞網(wǎng)點(diǎn)貨物的重量之和不超過配送車輛的載重量；式（3）保證每條路徑上各快遞網(wǎng)點(diǎn)貨物的體積之和不超過配送車輛的額定容積；式（4）表示每條配送路徑上配送車輛到達(dá)下一個(gè)快遞網(wǎng)點(diǎn)的時(shí)刻=到達(dá)當(dāng)前快遞網(wǎng)點(diǎn)的時(shí)刻+配送車輛在當(dāng)前快遞網(wǎng)點(diǎn)的等待時(shí)間+配送車輛在當(dāng)前快遞網(wǎng)點(diǎn)的卸貨時(shí)間+從當(dāng)前快遞網(wǎng)點(diǎn)到下一個(gè)網(wǎng)點(diǎn)配送車輛的行駛時(shí)間；式（5）表示配送車輛在某個(gè)快遞網(wǎng)點(diǎn)的等待時(shí)間取決于車輛到達(dá)該客戶的時(shí)刻與該客戶時(shí)間窗開始時(shí)刻的關(guān)系。

（3）其他約束條件

式（6）表示每條路徑上的快遞網(wǎng)點(diǎn)數(shù)不超過總網(wǎng)點(diǎn)數(shù)；式（7）表示每個(gè)配送中心至少要服務(wù)一個(gè)快遞網(wǎng)點(diǎn)；式（8）表示每個(gè)快遞網(wǎng)點(diǎn)都要得到配送服務(wù)；式（9）表示每條路徑客戶的組成；式（10）限制每個(gè)客戶僅能由一臺(tái)車輛送貨；式（11）表示決策變量。

4 實(shí)例驗(yàn)證

在武漢市5家快遞公司官網(wǎng)選取了291個(gè)快遞網(wǎng)點(diǎn)，利用百度地圖的坐標(biāo)拾取系統(tǒng)確定了各個(gè)快遞網(wǎng)點(diǎn)的位置坐標(biāo)，另外選取武漢市某快遞公司的3個(gè)集散中心位置坐標(biāo)作為本算例的配送中心位置坐標(biāo)。由于在該模型的約束條件中考慮到了車輛體積的約束，因此將每個(gè)網(wǎng)點(diǎn)的需求量劃分為兩部分，即：大件快遞需求量以及小件快遞需求量。并為每個(gè)快遞網(wǎng)點(diǎn)設(shè)置相應(yīng)的時(shí)間窗上限及下限。借助Matlab軟件用遺傳算法進(jìn)行編程，以配送運(yùn)輸成本最小、時(shí)間窗懲罰成本最小以及車輛固定使用成本最小為目標(biāo)函數(shù)，對(duì)武漢市快遞配送網(wǎng)點(diǎn)進(jìn)行車輛路徑優(yōu)化。前20個(gè)快遞網(wǎng)點(diǎn)數(shù)據(jù)見表1。

4.1 各點(diǎn)距離計(jì)算和參數(shù)設(shè)置

由于該快遞網(wǎng)點(diǎn)和配送中心的坐標(biāo)是在百度地圖中選取的經(jīng)緯度坐標(biāo)值，傳統(tǒng)的距離公式已不再適用，當(dāng)已知兩點(diǎn)的經(jīng)緯度分別為(ix,iy)、(jx,jy)，需采用以下公式將經(jīng)緯度坐標(biāo)轉(zhuǎn)化為實(shí)際距離，該算

表1 前20個(gè)快遞網(wǎng)點(diǎn)相關(guān)數(shù)據(jù)

例中其它參數(shù)設(shè)置見表2。

表2 模型相關(guān)參數(shù)設(shè)定

4.2 遺傳算法參數(shù)設(shè)置

利用遺傳算法對(duì)該算例進(jìn)行求解，算法參數(shù)的設(shè)定對(duì)算法的性能及運(yùn)行效率有極大影響，該算例中相應(yīng)的遺傳算法參數(shù)設(shè)置如下：

（1）對(duì)個(gè)體的編碼進(jìn)行設(shè)計(jì)，采用實(shí)數(shù)編碼方法構(gòu)造染色體，針對(duì)不同配送中心進(jìn)行編碼，然后將每個(gè)配送中心的編碼進(jìn)行串聯(lián)，每個(gè)配送中心的編碼格式為：[車輛數(shù) 顧客數(shù) 顧客訪問順序 車輛分配順序]。

（2）種群初始化。設(shè)定種群規(guī)模為2 500、進(jìn)化代數(shù)為250、交叉概率0.8、變異概率0.1，隨機(jī)產(chǎn)生2 500個(gè)個(gè)體，組成初始種群。

（3）適應(yīng)度評(píng)價(jià)。采用倒數(shù)法將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)，通過適應(yīng)度函數(shù)評(píng)價(jià)每條染色體的適應(yīng)度函數(shù)值。

4.3 實(shí)驗(yàn)結(jié)果

該算例中編號(hào)1、2、3分別代表三個(gè)配送中心，編號(hào)4～294分別代表291個(gè)快遞網(wǎng)點(diǎn)。通過matlab程序運(yùn)行，該算例的運(yùn)行收斂圖如圖1所示，說明該遺傳算法可以有效的解決本文所構(gòu)建的車輛調(diào)度優(yōu)化模型。具體的車輛路徑優(yōu)化結(jié)果見表3。

利用matlab程序運(yùn)行，可得到總配送成本為：10 659.46，第一配送中心需6輛車，為66個(gè)快遞網(wǎng)點(diǎn)進(jìn)行配送服務(wù)。第二配送中心需要9輛車，為92個(gè)快點(diǎn)網(wǎng)點(diǎn)進(jìn)行配送。第三配送中心需要10輛車，為133個(gè)快遞網(wǎng)點(diǎn)進(jìn)行配送。

圖1 遺傳算法收斂圖像

4.4 靈敏度分析

為了分析單位運(yùn)輸成本w1和單位車輛固定成本w4帶來的影響，在保持其他參數(shù)不變的情況下，分別將 w1和 w4增大10%、30%、50%、80%，運(yùn)行8次程序，計(jì)算結(jié)果見表4?？梢钥闯鰓1和w4對(duì)車輛的路徑分配均會(huì)產(chǎn)生影響，且當(dāng)參數(shù)在某一范圍內(nèi)發(fā)生變化時(shí)，各配送中心的車輛數(shù)量及車輛的路徑分配結(jié)果不會(huì)發(fā)生改變。說明該模型針對(duì)不同的參數(shù)變化能夠及時(shí)作出相應(yīng)調(diào)整的同時(shí)也具有一定的穩(wěn)定性。

表3 車輛路徑優(yōu)化結(jié)果

表4 單位運(yùn)輸成本和固定車輛成本對(duì)車輛路徑的影響

5 結(jié)論

本文根據(jù)電子商務(wù)環(huán)境下的配送特點(diǎn)，針對(duì)快遞包裹配送構(gòu)建了一個(gè)基于軟時(shí)間窗、車輛載重量、體積TLV三維約束的多配送中心車輛路徑優(yōu)化問題的模型。在該模型中將快遞包裹劃分為大件快遞和小件快遞兩個(gè)變量，從而對(duì)快遞包裹的體積進(jìn)行約束，并采用遺傳算法對(duì)該模型進(jìn)行求解。利用matlab對(duì)具體實(shí)例進(jìn)行驗(yàn)證，表明了該模型的有效性，可以為配送站點(diǎn)合理安排配送車輛及配送路徑提供一定的依據(jù)。

[1]Yu B,Yang ZZ,Yao BZ.A hybrid algorithm for vehicle routing problem with time windows[J].Expert Systems with Applications,2011,38(1):435-441.

[2]郭森,秦貴和,張晉東,等.多目標(biāo)車輛路徑問題的粒子群優(yōu)化算法研究[J].西安交通大學(xué)學(xué)報(bào),2016,50(9):97-104.

[3]殷脂,葉春明.多配送中心物流配送車輛調(diào)度問題的分層算法模型[J].系統(tǒng)管理學(xué)報(bào),2014,(4):602-606.

[4]金濤.多配送中心物流車輛調(diào)度的改進(jìn)差分進(jìn)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(3):232-235.

[5]葉勇,張惠珍.多配送中心車輛路徑問題的狼群算法[J].計(jì)算機(jī)應(yīng)用研究,2016,28(2):67-71.

[6]楊浩雄,李金丹,張浩.電商配送中的車輛調(diào)度問題優(yōu)化研究[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(15):32-37.

[7]覃運(yùn)梅,毛海軍,黑秀玲.基于自動(dòng)快遞機(jī)的快遞配送車輛路徑優(yōu)化研究[J].公路交通科技,2015,32(10):134-140.

[8]Huang Y,Zhao L,Woensel T V,et al.Time-dependent vehicle routing problem with path flexibility[J].Transportation Research Part B Methodological,2017,95:169-195.

[9]繆朝煒,蘇瑞澤,張杰.越庫配送車輛調(diào)度問題的自適應(yīng)遺傳算法研究[J].管理工程學(xué)報(bào),2016,30(4):166-172.