基于聯合配送與資源共享的多中心車輛路徑優化研究

石永強 黃韻怡 張智勇

（華南理工大學電子商務系，廣東 廣州 510006）

一、引言

中國快遞物流行業市場規模隨著產業的優化調整而不斷擴大，全國快遞業務量從2016年的312.8億件增長到2020年的833.6億件，年均復合增長率高達27.8%。隨著快件量爆炸式增長，快遞物流公司往往在一個城市內租用多個配送中心，以爭取更高的配送效率?，F實中，以運輸業務為主的公司由于配送中心重型設備功能和分揀流程的差異，同一公司管理下的不同配送中心只能中轉、分撥不同類別的產品，但下游客戶可能同時需要幾種產品。許多企業出于管理方便的考慮，各配送中心單獨組織配送，互不共享資源，只追求局部最優而非全局最優。在這種情況下，如何打破多個配送中心間的資源壁壘，盤活公司運輸和客戶資源，允許貨車合并訂單、中途到其他配送中心取貨，是幫助公司減少資源浪費的同時降低運輸成本的關鍵。

上述問題屬于多中心車輛路徑問題（MDVRP， Multi-depot Vehicle Routing Problem）的引申，國內外學者對MDVRP進行了研究。郎茂祥[1]較早研究了MDVRP，采用最近距離分配法將多配送中心問題分解單配送中心問題。Yang[2]利用混合遺傳算法研究了帶時間窗的多種環境車輛類型的多目標VRP。Li[3]等研究了封閉式多中心的同時取送貨問題。楊翔[4]設計了虛擬配送中心的編碼方法輔助求解MDVRP。范厚明[5]構建了兩階段優化模型，求解了多中心聯合配送模式下集貨需求隨機的VRP。另外，一些公司實際上并不關心車輛是否必須全部回到原配送中心，尤其是當物流活動外包給第三方車輛配送時。這類問題屬于半開放式的車輛路徑問題，Bae[6]、Jian Li[7]、劉家利[8]、馬冰山[9]等對相關問題進行了研究，論證了非封閉式的方案能節省車輛運輸成本和使用成本。

多配送中心車輛路徑問題的相關討論已非常廣泛，但現階段極少文獻對多配送中心聯合配送下，車輛行駛中途到其他配送中心取貨、合并客戶需求訂單這方面有研究，因此本文針對該情況下的聯合配送問題進行研究。

二、問題描述

本文研究的是，多個配送中心可共享車輛、車場及客戶資源，使用多車型的異質車輛完成配送的聯合配送模式。本文還考慮配送中心的功能限制，各中心所處理產品類型不同，允許車輛中途取貨以合并配送訂單。因此，本文要解決的是半開放式、帶時間窗、考慮配送中心資源共享的多中心車輛路徑 問 題（MDVRPSDR，Multi-depot VRP under Shared Depot Resources）。

圖1是簡化的問題示意圖，假設原方案由2個配送中心（A、B）和6個客戶組成，配送中心配備有成本結構不同的自有車和外租車，各配送中心（下稱“DC”）獨立配送。三角形表示配送中心，其中A只提供A’產品，B只提供B’產品。圓為客戶，圓內左邊數字是客戶對A’的需求，右邊數字是客戶對B’的需求。原方案中，一共使用了3輛自有車（1、3、4）和1輛外租車（2），貨車配送完畢后需回到起始DC。

圖1 優化前后對比圖

當配送方案從獨立模式優化為共享模式時：①路徑2和3優化為路徑6，車從A攜帶6單位A’出發，到達B處后取9單位B’，再依次向b、c配送，由此減少啟用一臺車。②路徑4優化為路徑7，由封閉性優化為開放性。③DC開放車場供任意車輛?？?，路徑1優化為路徑5，車輛從a直接回到更近的B，減少行駛距離。④優化各路徑所使用的車輛性質，使得運輸成本更低。

三、模型建立

設某公司有DC，各DC只存儲一種產品，且產品互異，所有DC要服務一群客戶，滿足以下假設：

①一個客戶可能只需要一種產品，或同時需要多種產品。②每個客戶最多只能被一輛車訪問。③每個客戶的某種產品需求只由一輛車服務。④車輛的最大容量與車型有關，由于城區配送路程有限，不考慮車輛最大行駛距離的限制。⑤客戶處對可容納的車型有限制，車型過大時會造成卸貨擁堵，產生超限懲罰成本。⑥自有車在結束配送后必須回到任一DC?？浚庾廛噭t直接離開，不需要考慮返程。

若以配送總成本最小為目標函數，基于以上假設和定義，可建立以下數學模型：

上述函數式中，（1）式為目標函數，即車輛啟用成本、可變運輸成本、違反時間窗懲罰成本、超限成本之和最小。（2）表示一個客戶只被訪問一次。（3）表示車輛在一次運輸中可以配送一種或多種產品。（4）表示車輛進出平衡。（5）規定兩個DC之間最多可以直接互通一次。（6）表示載重約束和客戶處可容納車型的限制。（7）表示每個客戶的每種產品只由一輛車提供服務。（8）指滿足客戶的所有需求。（9）為初始載重量。（10）確保沒有子回路。（11）表示自有車可從任意DC出發，空車回到任意DC。（12）為早到等待時間。（13）表明車輛按順序訪問路徑中的點。（14）表明變量之間的關系。（15）為超限懲罰成本。（16）～（19）為決策變量。

四、算法設計

本文選擇模擬退火算法與遺傳算法混合使用，SA有局部搜索能力強的優點，但全局搜索能力差，容易受參數的影響，而GA能有效跳出局部最優的優點，缺點是受初始解影響較大。因此本文結合海明距離過濾機制，設計混合模擬退火-改進自適應遺傳算法（SA-AGA），以SA的最優解為AGA的初始解，并設計自適應算子與過濾機制，避免AGA陷入局部最優，解決算法的缺陷問題。

1.編解碼方式及初始化種群

染色體采用連續自然數編碼，利用虛擬DC編碼方式來決定路徑。從1開始，取n+m-1個連續不重復的自然數作為編碼的表示，1～n為客戶編號，n+1～n+m-1為虛擬DC的編號，虛擬DC之間的距離為0。解碼分為三個階段：一階段將個體解碼為子路徑；二階段根據就近原則和客戶需求將DC插入到子路徑的首、尾、中途；三階段為子路徑選定用車方案。

在初始化種群方面，以隨機法生成SA的初始解，再利用SA生成最優解，將其復制NIND次作為AGA的初代種群。SA具體步驟為：種群初始化；能量值計算；同一溫度層內隨機擾動MaxInIter次；按Metropolis準則接受新解；依照冷卻因子α來更新溫度Tn，繼續下一個溫度層的隨機擾動，直到完成降溫次數MaxOutIter次。

為便于理解，假設有3個DC（A， B， C）和10個客戶（1，2，...，10），用11、12、13表示虛擬DC，表示最多使用4臺車，共有3種產品A’、B’、C’，分別存放在配送中心A、B、C。

（1）第一階段解碼

以虛擬DC為分割點劃分路徑，若虛擬DC的編碼位置相鄰，則它們之間無路徑。例如編碼為{7， 2， 13， 3， 6， 1， 5， 9，4， 12， 11， 8， 10}時，解出3條路徑{7， 2}，{3， 6， 1， 5， 9，4}，{8， 10}。

（2）第二階段解碼

對一階段解碼得出的子路徑的配送方案進行“匹配首尾DC、中間插入DC”的操作。以上述第一階段的第二個路徑{3， 6，1， 5， 9， 4}的解碼過程為例，為便于理解，各客戶的需求用0和1表示，如圖2所示。先判斷結尾客戶4離C最近，則選定C為終點，接著決定起點和中途取貨的DC。根據路徑上客戶對的需求種類不同，有以下三種可能。

一是路徑中的客戶共有一種需求。無需中途取貨，計算子路徑的需求量總和，派出1輛容量大于等于需求量總和且限載盡可能小的車完成運輸，起點為存放該種需求產品的配送中心。

二是路徑中的客戶共有兩種需求。先計算需要多大容量的車，再分析如何中途取貨。如圖2，客戶對A’、B’產品有需求，因此A、B均可為起點，選定起點后再中途插入其他DC。若選A作起點，對非起點DC對應的需求找到首個“需求非0位置”，即客戶7前的位置，把B插入到7前的任意位置。最后對比所有插入方案的路徑長度，擇更短者為解碼結果。

圖2 兩種需求時的二階段解碼示意圖

三是路徑中的客戶共有三種需求。選擇車輛容量和插入DC的思路與（1）和（2）相似。

（3）第三階段解碼

處理第二階段的解碼結果，決策各子路徑使用自有車還是外租車。根據車輛成本信息，以當前路徑的運輸成本最低為原則來抉擇車輛性質。

2.適應度函數

利用目標函數式（1）構建適應度函數，如下式。

3.選擇操作

結合最佳精英選擇法和輪盤賭法，先將適應度最大的前20%的精英個體直接復制到子代，其余個體按輪盤賭方法進行選擇。

4.交叉和變異

對被選中的染色體以概率pc進行OX交叉操作，再以概率pm將該染色體上隨機兩個位置的基因對換。安海[10]在線性自適應遺傳算子和非線性自適應遺傳算子的基礎上，使用了曲線底部比余弦函數更平滑的sigmoid函數來構造遺傳算子。該文獻經算例分析，證明提出的算子在求解時有收斂速度更快、結果更準確的優點，因此本文使用該遺傳算子，如式（21）～（22）所示。fmax為當前種群的適應度最大值；favg為當前種群的適應度平均值；fb為要進行交叉的個體中適應度更大一方的適應度值；fm為要變異個體的適應度值；pmmax、pmmin為最大、最小變異概率，pcmax、pcmin為最大、最小交叉概率；經作者論證，A為9.903438。

5.海明距離過濾機制

本文設置海明距離（指兩個個體的基因排列差異位數）過濾機制，從第二代開始執行該機制，直到最大迭代次數。目的是在選擇操作前，濾掉相似度過高的個體，以保證個體多樣性。設置適應度差值門檻D和海明距離閾值Ham_dis：D用于判斷個體間的適應度值差異大小，Ham_dis用于判斷個體間編碼相似程度。對每一代執行過濾機制的具體步驟如下：

圖3 海明距離過濾機制流程圖

6.終止機制

進化代數達到最大代數限制Maxgen時，算法終止。

五、實例分析

本文以廣州市某專注于快遞業務的A公司為例，使用調研樣本數據進行算例分析，通過對比各配送中心獨立配送和多中心聯合配送兩種模式，評價聯合模式下資源共享方案的有效性。

1.算例描述

已知廣州市某A公司有3個一級配送中心（J、H、L），三者中轉的產品各不相同，分別為函件類普通包裹、電商快遞包裹、高時效要求的標準快件（以下用P、D、B指代三種包裹）。全市配送網共有88個客戶，各客戶的位置用經緯度表示。88個客戶的日均需求量如表1所示。由于各客戶的卸貨場地大小不同，均有最大可入車型的限制Ti（3t、5t、8t）。車輛相關信息如下：車輛的日均運輸成本包括固定啟用成本和變動成本（如燃油、保養維護等）；單次卸貨時間與車輛噸位大小成正相關，3t、5t、8t貨車分別對應20min、30min、40min；所有車輛的行駛平均速度Vk=30km/h；車輛滿載時按每噸500件計算，裝載率=（本車配送件數/本車滿載件數）×100%。

表1 客戶信息（部分）

A公司原有配送方案是3個DC獨立安排配送，起點、終點為同一個DC，無中途取貨。部分客戶會被重復訪問，客戶需要騰出多次接貨時間，車輛平均裝載率不高。因此，基于同樣的需求和車輛，A公司可組織聯合配送，本文用SA-AGA求解聯合配送下的優化方案。

2.結果分析

圖4 最優路徑圖

求解結果顯示：獨立配送方案啟用了6輛3t車、7輛5t車、13輛8t車，其中外租車15輛；聯合配送方案啟用了20輛3t車、4輛5t車、2輛8t車，其中外租車17輛。使用相同算法對獨立配送模式求解，將其與聯合配送模式對比。優化后的部分路徑安排如表2所示，優化前后的配送方案效果對比如表3所示。

表2 聯合配送下的路徑安排（部分）

表3 優化前后的成本與裝載率對比

由表2、表3可知，當在聯合配送模式下，整體所啟用的車輛總數減少，配送總里程從1769.9千米降至1615.4千米，下降了8.7%，平均裝載率從84.9%上升到87.8%，違反時間窗與限重的總次數更少。因此，多中心共享運輸資源和客戶資源、允許中途取貨的聯合配送模式，比獨立配送模式有更好的效果與效益。

六、結語

本文建立了多配送中心資源共享、多產品、半開放式、異質車輛的車輛路徑優化模型，并設計混合模擬退火-改進自適應遺傳算法，使用了三階段解碼法和過濾機制克服經典算法的缺點。通過A公司的實例分析驗證了多中心聯合配送的可行性，為三個配送中心確定了要使用的車輛和要服務的下游需求點，并將其與各中心獨立配送的模式作對比，結果表明：允許中途取貨、合并需求的聯合配送模式和獨立配送模式相比，前者使用的車輛總數更少，車輛平均裝載率更高，總配送成本更低。