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

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

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

1 引言

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

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

2 問題描述

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

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

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

3 模型構建

3.1 模型假設

為了便于問題的描述和構建相應的數學模型，針對該多配送中心三維約束模型提出了如下假設條件：

（1）配送區域內，每個配送中心至少服務一個快遞網點。

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

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

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

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

3.2 符號說明

Kh：每個配送中心的車輛數；

Phk：每臺車輛的載重量；

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

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

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

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

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

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

dij：客戶i到j的距離；

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

Rhk：第h個區域中的第k條路徑；

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

Shi：車輛到達客戶i的時刻；

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

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

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

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

3.3 模型建立

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

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

（3）其他約束條件

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

4 實例驗證

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

4.1 各點距離計算和參數設置

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

表1 前20個快遞網點相關數據

例中其它參數設置見表2。

表2 模型相關參數設定

4.2 遺傳算法參數設置

利用遺傳算法對該算例進行求解，算法參數的設定對算法的性能及運行效率有極大影響，該算例中相應的遺傳算法參數設置如下：

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

（2）種群初始化。設定種群規模為2 500、進化代數為250、交叉概率0.8、變異概率0.1，隨機產生2 500個個體，組成初始種群。

（3）適應度評價。采用倒數法將目標函數轉換成適應度函數，通過適應度函數評價每條染色體的適應度函數值。

4.3 實驗結果

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

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

圖1 遺傳算法收斂圖像

4.4 靈敏度分析

為了分析單位運輸成本w1和單位車輛固定成本w4帶來的影響，在保持其他參數不變的情況下，分別將 w1和 w4增大10%、30%、50%、80%，運行8次程序，計算結果見表4。可以看出w1和w4對車輛的路徑分配均會產生影響，且當參數在某一范圍內發生變化時，各配送中心的車輛數量及車輛的路徑分配結果不會發生改變。說明該模型針對不同的參數變化能夠及時作出相應調整的同時也具有一定的穩定性。

表3 車輛路徑優化結果

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

5 結論

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

[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]郭森,秦貴和,張晉東,等.多目標車輛路徑問題的粒子群優化算法研究[J].西安交通大學學報,2016,50(9):97-104.

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

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

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

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

[7]覃運梅,毛海軍,黑秀玲.基于自動快遞機的快遞配送車輛路徑優化研究[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]繆朝煒,蘇瑞澤,張杰.越庫配送車輛調度問題的自適應遺傳算法研究[J].管理工程學報,2016,30(4):166-172.