石永強 黃韻怡 張智勇

（華南理工大學(xué)電子商務(wù)系，廣東 廣州 510006）

一、引言

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

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

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

二、問題描述

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

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

圖1 優(yōu)化前后對比圖

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

三、模型建立

設(shè)某公司有DC，各DC只存儲一種產(chǎn)品，且產(chǎn)品互異，所有DC要服務(wù)一群客戶，滿足以下假設(shè)：

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

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

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

四、算法設(shè)計

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

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

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

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

為便于理解，假設(shè)有3個DC（A， B， C）和10個客戶（1，2，...，10），用11、12、13表示虛擬DC，表示最多使用4臺車，共有3種產(chǎn)品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所示。先判斷結(jié)尾客戶4離C最近，則選定C為終點，接著決定起點和中途取貨的DC。根據(jù)路徑上客戶對的需求種類不同，有以下三種可能。

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

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

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

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

（3）第三階段解碼

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

2.適應(yīng)度函數(shù)

利用目標函數(shù)式（1）構(gòu)建適應(yīng)度函數(shù)，如下式。

3.選擇操作

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

4.交叉和變異

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

5.海明距離過濾機制

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

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

6.終止機制

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

五、實例分析

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

1.算例描述

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

表1 客戶信息（部分）

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

2.結(jié)果分析

圖4 最優(yōu)路徑圖

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

表2 聯(lián)合配送下的路徑安排（部分）

表3 優(yōu)化前后的成本與裝載率對比

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

六、結(jié)語

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