基于TLV 三維約束的多配送中心VRP 問題

王長瓊，王艷麗，邱 杰，曹乜蜻，劉曉宇

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

1 引言

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

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

2 問題描述

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

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

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

3 模型構(gòu)建

3.1 模型假設(shè)

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

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

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

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

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

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

3.2 符號說明

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

Phk：每臺車輛的載重量；

Bhk：每臺車輛的額定容積；

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

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

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

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

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

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

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

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

rhki：客戶rhki在第h個區(qū)域中的路徑k中的順序為i（不包括配送中心）；

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

thi：車輛在客戶i的等待時間；

ta：在每個客戶點的卸車時間；

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

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

3.3 模型建立

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

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

（3）其他約束條件

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

4 實例驗證

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

4.1 各點距離計算和參數(shù)設(shè)置

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

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

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

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

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

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

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

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

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

4.3 實驗結(jié)果

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

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

圖1 遺傳算法收斂圖像

4.4 靈敏度分析

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

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

表4 單位運輸成本和固定車輛成本對車輛路徑的影響

5 結(jié)論

本文根據(jù)電子商務(wù)環(huán)境下的配送特點，針對快遞包裹配送構(gòu)建了一個基于軟時間窗、車輛載重量、體積TLV三維約束的多配送中心車輛路徑優(yōu)化問題的模型。在該模型中將快遞包裹劃分為大件快遞和小件快遞兩個變量，從而對快遞包裹的體積進(jìn)行約束，并采用遺傳算法對該模型進(jìn)行求解。利用matlab對具體實例進(jì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é)報,2016,50(9):97-104.

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

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

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

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

[7]覃運梅,毛海軍,黑秀玲.基于自動快遞機(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é)報,2016,30(4):166-172.