王新杰,陳淮莉
上海海事大學 物流科學與工程研究院,上海 201306
近年來,電子商務蓬勃發展,產品更新換代速度不斷加快,根據《中國電子商務報告2020》顯示,該年全國網上零售額突破117 601億元,同比增長10.9%[1],隨著直播帶貨等銷售形式的產生,以及電商7天無理由退貨等政策的推廣,消費者由于利益驅動、沖動消費、信息不對稱以及產品缺陷等因素造成的網絡購物退貨的現象越來越多[2]。例如,阿里巴巴集團在2016年至2020年間籌劃的“雙十一”活動中,商品退貨率處于25%至40%之間,而研究表明電商零售產品的平均退貨成本普遍比傳統零售產品高[3]。因此,科學合理的組織電子商務逆向物流,有助于物流企業減少退貨時間,降低運輸成本,提高客戶滿意度,打通“第五利潤源”。共享經濟背景下,共享物流模式成為新發展趨勢,不少物流企業通建立橫、縱向合作,通過共享物流資源實施協同運輸,從而降低成本,車輛路徑問題(vehicle routing problem,VRP)是其核心問題。
國內外學者對共享物流模式下車輛路徑優化問題已做出系列探索。起初,學者基于車輛資源共享情景,將協同運輸模式引入到城市物流中進行研究,Liu等[4]基于多配送中心問題,以空車移動距離最小化為目標,提出兩階段貪婪算法對大規模算例進行求解。Wang等[5]提出協同的兩級物流聯合配送網絡,建立以總成本最小為目標的線性優化模型,并運用一種蟻群算法和遺傳算法相結合的混合啟發式算法進行求解,有效減少城市貨物運輸系統的交叉運輸現象。接著,學者針對縱向共享模式展開研究,Zhang等[6]基于二級物流網絡,提出了一種通過承運方與倉庫之間的協作來縮短運輸距離的路徑優化模型,并設計基于鄰域搜索的EVNS算法,證明了模型的有效性。He等[7]研究了由制造商和零售商組成的雙渠道電子商務供應鏈中的物流服務共享及其競爭問題,分別在有、無縱向物流服務共享的情景下,探索公司利潤的變化,為縱向物流服務共享模式下車輛路徑問題的研究奠定了基礎。
隨著研究深入,學者發現若物流企業之間開展橫向合作,共享車輛、物流中心、客戶訂單等資源,則可以較大程度地避免過遠運輸、交叉運輸和迂回運輸的現象,從而降低成本。Li等[8]基于配送中心共享的帶時間窗開放式多中心車輛路徑問題,提出自適應局部搜索混合遺傳算法進行求解,證明了解的質量優勢。劉家利等[9]基于車輛租賃和車輛共享,提出了帶時間窗的多配送中心開環車輛路徑問題,并結合掃描算法和C-W節約算法設計混合遺傳算法求解,通過實例證明算法具有良好的性能。葛顯龍等[10]面向跨區域多中心多車型開放式聯合配送車輛路徑問題,引入時間軸概念,建立“多對多”動態車輛路徑優化模型,并利用云遺傳算法進行求解,開辟了動態多中心聯合配送的車輛路徑優化問題研究。付朝暉等[11]首次考慮客戶服務關系變化與客戶需求的異質性情況,在共享客戶需求、配送車輛以及物流中心的情境下,設計多中心橫向共享物流模式,并建立以總成本最小為目標的共同配送車輛路徑優化模型,通過改進的蟻群算法進行求解,證明物流企業之間通過共同配送,可以大幅度降低物流成本,但是未考慮客戶時間窗約束,有一定局限性。范厚明等[12]在已有研究的基礎上,融合隨機需求理論,研究集貨需求隨機情況下,多中心聯合的同時取送貨車輛路徑問題,并設計自適應變鄰域文化基因算法進行求解,但是未考慮多中心聯合后的利潤分配問題。Yong等[13]將共同配送理論應用到冷鏈物流領域中,提出物流設施共享的多中心協同車輛路徑問題,以成本與冷藏車數量最小為目標,建立雙目標整數規劃模型,并利用k-means算法和禁忌搜索非支配排序遺傳算法求解,豐富了冷鏈物流車輛路徑優化的研究。
綜上所述,國內外學者對橫、縱向共享物流模式下車輛路徑問題的研究已取得豐富成果。電子商務逆向物流由于其需求規模大、分布廣泛、單一需求量小、具有時間窗約束等特點,更適于橫向共享物流模式。然而,目前將共享物流模式運用于電子商務逆向物流的研究并不多,同時考慮到現實中的物流企業若建立橫向聯盟,需要科學的共同利潤分配機制作為支撐,而很少學者關注到聯盟參與者之間的利潤分配問題。鑒于此,本文提出多中心聯合取送貨的車輛路徑優化與利潤分配問題,在共享車輛與客戶訂單的條件下,考慮客戶時間窗約束,以變動運輸成本、固定運輸成本和懲罰成本之和最小為目標,建立MJVRPSDPTW模型,并根據模型特征設計基于大鄰域搜索的混合遺傳算法進行求解,最后利用Shapley值法對物流企業聯盟后的共同利潤進行分配,并通過對比聯盟前后的物流成本,驗證模型有效性。
在區域內有若干家物流企業,每個物流企業擁有一個物流中心和若干客戶點。物流企業聯盟前與聯盟后的網絡差異如圖1所示,觀察可知,聯盟之前四個物流中心相互獨立,各自服務對應的客戶,從而存在大量交叉運輸的現象。然而,當物流企業建立橫向聯盟后,通過共享車輛、物流中心與客戶訂單等資源,可以實現開放式聯合取送貨的運作方式。該模式下各物流中心服務鄰近客戶,通過集成運輸實現物流中心與客戶訂單共享,從而減少交叉運輸、過遠運輸等現象,最終對聯盟共同利潤進行合理分配,以保證聯盟穩定性。相比聯盟前,該模式減少車輛空駛里程,降低網絡的總物流成本,同時有利于緩解交通擁堵和減輕碳排放。

圖1 聯盟前后對比Fig.1 Comparison before and after alliance
在實際中,聯盟的組織者可以是該物流網絡中的一家物流企業,也可以是第三方物流平臺,本研究設定聯盟組織者為其中一家物流企業[14]。為了模型更貼合實際,現在做出如下假設:
(1)各物流中心的貨源不限,車輛數不限。
(2)客戶點具有時間窗約束和同時取送貨需求。
(3)每個客戶點的需求信息和位置信息已知,必須且僅被服務一次。
(4)各物流中心通過廂式貨車對各客戶點進行取貨和送貨服務,且物流中心之間通過半掛式卡車進行調配貨物。
(5)客戶服務關系改變時,需對應貨物從原物流中心調配至新物流中心。
(6)用于運輸的車輛具有容量約束且是同類型的。
(7)車輛從物流中心出發,完成服務后返回最近的物流中心。
此外,為簡化模型計算,將車輛行駛速度、單位運價、車輛固定成本、車輛載重量等參數設為整數。
(1)集合
N:各節點集合,N={1,2,…,n,n+1,…,n+m},包含n個客戶點和m個物流中心;
C:各客戶點集合,C={1,2,…,n};
D:各物流中心集合,D={n+1,…,n+m};
K:廂式貨車集合,k∈K;
T:半掛式卡車集合,t∈T;
(2)參數
pi:客戶點i的取貨需求量,i∈C;
di:客戶點i的送貨需求量,i∈C;
si:廂式貨車在客戶點i的服務時間,i∈C;
[ai,bi]:客戶點i的服務時間窗;
α:廂式貨車早于ai到達客戶點時的懲罰系數;
β:廂式貨車晚于bi到達客戶點時的懲罰系數;
Pij:物流中心i調配至物流中心j的取貨量;
Dij:物流中心i調配至物流中心j的送貨量;
lij:i和j兩節點之間的距離,i,j∈N;
c1:廂式貨車單位變動運輸成本;
c2:半掛式卡車單位變動運輸成本;
f1:廂式貨車固定運輸成本;
f2:半掛式卡車固定運輸成本;
Qk:廂式貨車最大載重;
Qt:半掛式卡車最大載重;
v:廂式貨車平均速度;
M:無窮大的正數;
(3)變量
xijk:廂式貨車k從客戶點i出發到客戶點j時為1,否則為0,其中i,j∈C;
tik:廂式貨車k到達客戶點i的時間,其中i∈C;
qijk:廂式貨車k從客戶點i出發到客戶點j時的負載,其中i,j∈C;
yk:廂式貨車k投入使用時為1,否則為0;
Xijt:半掛式卡車t從物流中心i出發至物流中心j時為1,否則為0,其中i,j∈D;
rijt:半掛式卡車t從物流中心i出發至物流中心j時負載,其中i,j∈D;
Zhij:客戶h的服務關系由物流中心i轉移至物流中心j時為1,否則為0,其中h∈C且i,j∈D;
Yt:半掛式卡車t投入使用時為1,否則為0。
該MJVRPSDPTW模型的總成本包括:固定運輸成本、變動運輸成本以及懲罰成本。其中固定運輸成本是指廂式貨車和半掛式卡車的啟動成本,不隨運輸距離而變化;變動運輸成本是指廂式貨車和半掛式卡車的保養和燃料等費用,與運輸距離成正比;懲罰成本是指廂式貨車超出時間窗對客戶進行服務造成的損失,模型具體數學表達如下。
1.3.1 目標函數
廂式貨車的變動運輸成本與固定運輸成本:

半掛式卡車的變動運輸成本與固定運輸成本:

廂式貨車超出時間窗服務的懲罰成本:

總運輸成本為三者之和,則目標函數表示為總成本最小,如式(4)所示:

該模型滿足的約束條件如下:


約束(5)表示任意客戶只能被一輛廂式貨車服務一次,約束(6)表示廂式貨車不能從一個物流中心直接到另一個物流中心,約束(7)表示半掛式卡車只能在物流中心之間調配貨物,不能對客戶點進行服務,約束(8)和(9)保證決策變量的一致性,約束(10)表示廂式貨車從物流中心出發,完成任務后返回任一個物流中心,約束(11)和約束(12)分別為廂式貨車和半掛式卡車的容量約束,約束(13)表示廂式貨車的載重變化,約束(14)表示半掛式卡車從物流中心i調配至j的送貨量,約束(15)表示半掛式卡車從物流中心j調配返回物流中心i的集貨量,約束(16)表示廂式貨車服務時間的連續性,約束(17)用于消除子回路。
在處理多中心車輛路徑問題過程中,大多學者通過客戶劃分的方式將其轉化為多個單一中心問題處理,這種方式使各中心之間相互獨立,不能從整體上對物流網絡進行優化,得到的結果往往較差,故本文采用整體法,提出虛擬中心概念。假設所有廂式貨車均從虛擬中心出發,先到達實際物流中心再到達客戶點進行服務,服務完成后要求先回到實際物流中心,最后返回虛擬中心[15]。其中,虛擬中心并不實際存在,其與實際中心之間的距離、運費等參數均為0。
文本提出的MJVRPSDPTW是VRP的變體,屬于NP難問題。此外,該問題基于開放式車輛路徑且考慮時間窗約束,計算難度遠大于傳統VRP問題,很難得到精確解。因此,采用啟發式算法求其近似最優解,遺傳算法(GA)具有良好的魯棒性和并行性,但傳統的遺傳算法易陷入局部最優,從而過早收斂[16]。大鄰域搜索算法(LNS)可通過“破壞”和“修復”算子,對現有解動態優化的局部搜索算法,具有良好的深度搜索能力。因此,本文設計了一種基于大鄰域搜索的混合遺傳算法進行求解,旨在將遺傳算法良好的全局尋優能力與大鄰域搜索算法局部尋優能力相結合,從而快速找到最優解,算法總體設計思路如下:
(1)設置虛擬中心,對多中心網絡進行整體優化。
(2)遺傳算法的選擇算子采用精英保留與輪盤賭相結合的策略;交叉算子采用OX交叉方式;變異算子采用兩點交換的方式。
(3)將大鄰域搜索算法的“破壞”與“修復”思想用于遺傳算法的局部搜索過程中。
算法的具體步驟如下:
步驟1編碼
本文采用自然數編碼的方式,數字0表示虛擬中心,基因序列為客戶服務的順序。
步驟2參數設置
輸入客戶點、物流中心坐標、客戶取送貨需求量、時間窗、單位距離運費、車輛最大容量等模型參數。令種群規模為pop,最大迭代次數為max,交叉概率為pc,變異概率為pm,當前迭代次數為ξ,當前總成本為costξ。
步驟3種群初始化
采用載重約束與時間窗約束[17]生成初始種群。
步驟4解碼
計算適應度函數值前要對個體進行解碼,即實現虛擬中心到實際中心的轉換。此處定義算子,輸入虛擬中心的鄰近客戶點以及各節點之間的距離矩陣,從而得到距離最近的實際物流中心。具體示意如圖2所示,其中49至52代表四個實際物流中心。

圖2 解碼Fig.2 Decoding
步驟5適應度函數
以總成本的倒數作為適應度函數,總成本越小則染色體的適應度值越大,具體如式(18)所示:

步驟6選擇操作
此處采用精英保留策略與輪盤賭相結合的方式,將適應度值最高的個體保留至下一代,用于替換下一代初始適應度值最低的個體,同時對所有個體通過輪盤賭的方式進行選擇和復制。
步驟7交叉操作
當滿足概率pc時,發生交叉操作。此處采用OX交叉[20]方式,具體如圖3所示。

圖3 OX交叉Fig.3 OX crossover operator
步驟8變異操作
當滿足一個較小概率pm時,染色體發生變異,從而保證多樣性。此處采用隨機交換兩個客戶基因位的方式,進行變異操作。
步驟9破壞算子
該算子旨在減少車輛數,從當前解A中移除λ個客戶,剩余部分解用A′表示,移除的客戶組成集合L,則具體步驟如下:首先,從短路徑中隨機選擇一個客戶移除。其次,在A′中選擇與上一個被移除客戶之間相關性最高的客戶移除,不斷重復直至移除λ-1個客戶,其相關性計算如式(19)所示[18]:

其中,為i和j間標準化后的距離;Vij為0-1變量,當i和j在同一條路徑上時Vij取0,否則為1。
步驟10修復算子
將L中的客戶依此選擇最優的位置插回A′中,得到改進后的解A″。在此過程中,要滿足客戶時間窗約束和車輛容量約束,同時使新個體的適應度值更高。具體如下:(1)隨機選取L中的一個客戶Li,在A′中找到滿足時間窗和車輛容量約束的所有插入點;若無合適插入點,則在末尾插入新路徑,并將Li作為新路徑的首個客戶。(2)計算客戶在各可能插入點的插入成本,并選擇最小成本對應的插入點進行插入。(3)返回(1)循環,直至將L中所有客戶均插入A′,從而得到新解A″,當新解適應度值大于解A的適應度值時,保留新解A″。
步驟11更新迭代
更新當前最優適應度值,用精英個體代替種群中適應度值最低的個體,并返回步驟4,記ξ=ξ+1。
步驟12結束
當迭代次數ξ達到最大迭代次數max時,結束算法并輸出當前最優解。
該算法流程如圖4所示。

圖4 混合遺傳算法流程Fig.4 Hybrid genetic algorithm steps
當多個物流企業建立聯盟U后,開展聯合取送貨服務,大大降低了運營成本。接著基于優化后的網絡,計算共同利潤,即總成本的節約值C(U),以及可分配共同利潤M(U)。通常聯盟的組織者會將一定比例的共同利潤作為其組織聯盟的報酬,并將剩余利潤按照科學合理的方法分配給各聯盟參與者[19],具體如式(20)和(21)所示:

其中,v0(ξ)表示成員ξ未參與聯盟時的成本。v(U)為聯盟U的總運營成本;ρ表示聯盟組織者提取利潤的比例,且0≤ρ≤1。
Shapley值法是由Shapley[20]提出的多人合作博弈利潤分配問題的一種求解方法,應滿足行為理性假設與收益理性假設。在此處,行為理性假設指任意物流企業ξ在參與聯盟后的最終成本v(ξ)不大于獨立運營的成本v0(ξ),具體如式(22)和(23)所示,其中,η(ξ)為成員參與聯盟后的初始成本;φ(ξ)為成員參與聯盟后得到的利潤分配值。

收益理性假設是指,任意兩個子聯盟U1與U2合作后的總成本不大于其獨立運營的成本之和,數學表達如式(24)所示:

根據Shapley值相關理論[21]可知,成員ξ的利潤分配值φ(ξ)如式(25)所示,且最終聯盟成本v(ξ)如式(26)所示。其中,Dξ表示大聯盟D中包含成員ξ的所有子集形成的集合,|U|表示子聯盟U的成員個數,v(U{ξ})表示子聯盟U去掉成員ξ之后的成本。

由于目前沒有共享物流模式下,多中心聯合取送貨問題的標準數據集,故以MDVRPTW數據集(http://neumann.hec.ca/chairedistributique/data/mdvrp/new)為基礎,附加客戶服務關系與客戶取貨需求量,作為本文的測試數據。其中,各數據集的物流中心數為4,各客戶的服務關系為[1,4]之間的隨機整數,分別對應4個物流中心。此外,各數據集的客戶數目最小為48,最大為192。設廂式貨車最大載重量Qk=100,平均行駛速度v=60,固定運輸成本f1=200,單位變動運輸成本c1=1;半掛式卡車最大載重量Qt=200,固定運輸成本f2=300,單位變動運輸成本c2=2,時間窗懲罰系數α=0且β=10。
算法在Windows10(64 bit,16 GB)環境下,采用MATLAB R2020a進行開發,其參數設置如下:種群規模pop=200,最大迭代次數max=100,交叉概率pc=0.9,變異概率pm=0.4。
4.2.1 聯合取送貨路徑優化結果分析
在修改后的MDVRPTW數據集中,采用pr01至pr14進行實驗,其中數據集pr01至pr04分別與數據集pr11至pr14擁有相同的節點坐標、客戶取送貨需求與服務時長,僅客戶服務時間窗不同。為驗證所提出的基于大鄰域搜索混合遺傳算法的有效性,本文分別與基于客戶劃分的兩階段規劃法及經典遺傳算法進行對比,結果如表1所示。其中,IN為數據集名稱,ND為物流中心數量,NC為客戶數目,NV、NT分別為廂式貨車與半掛式卡車的數量,TC為總成本,NTW為超出時間窗進行服務的客戶數。

表1 不同算法的多中心聯合取送貨路徑優化結果Table 1 Optimization results of multi-center joint pick-up and delivery path with different algorithms
觀察表1可知:(1)根據TC值,基于大鄰域搜索的混合遺傳算法在每個算例中得到的總成本均最低。相比兩階段規劃法,總成本平均節約15.93%,相比經典遺傳算法平均節約50.42%。(2)根據NV和NT值,基于大鄰域搜索的混合遺傳算法在各算例中使用的廂式貨車數與半掛式卡車數均為最小,證明該算法擁有更高的車輛使用效率。其首要原因在于,整體法能夠對“多對多”式網絡進行整體優化,打破兩階段規劃法各中心相互獨立的限制,增強各物流中心之間的協作,實現車輛資源的有效共享。其次,該算法在經典遺傳算法的基礎上引進“破壞”與“修復”算子,增強了局部搜索能力,在保證客戶服務水平的條件下降低車輛使用數目。(3)在客戶數、中心數以及客戶取送貨需求相同的條件下,不同的服務時間窗會對配送方案及總成本造成較大的差異,面對大規模數據集,基于大鄰域搜索的混合遺傳算法會通過適當違反客戶時間窗的方式靈活調整配送方案,從而減少車輛數及行駛路程,確保總成本最低。
4.2.2 不同模式下路徑優化結果分析
此處以pr03數據為例,分別在多中心聯合取送貨模式與獨立運營模式下進行對比實驗,路徑優化結果對比如表2所示,分析可知:(1)獨立運營模式下,4個物流中心只對各自的客戶進行服務,不涉及資源共享,故物流中心之間不存在集中調配,而聯合取送貨模式下,物流中心之間通過半掛式卡車進行貨物調配,實現客戶訂單共享;(2)獨立運營模式下,廂式貨車總行駛里程為10 798.36 km,而聯合取送貨模式下,廂式貨車總行駛里程為3 424.78 km,由于存在大量交叉運輸等現象,獨立運營模式的廂式貨車總里程比聯合取送貨模式高出15.5%;(3)獨立運營模式下的總成本為17 020.79,聯合取送貨模式下的總成本為14 733.84,聯合取送貨模式通過資源共享,使車輛運行更加有序,故總成本相比獨立運營模式減少了13.44%。

表2 不同模式下路徑優化結果Table 2 Optimization results of different mode
聯合取送貨與獨立運營兩種不同模式下,pr03算例路徑優化圖如圖5所示,其中4個矩形代表物流中心,144個圓形代表客戶點,物流中心之間加粗線代表半掛式卡車的貨物調配路徑,細線代表廂式貨車的路徑。觀察可知:(1)圖5(a)通過多中心聯合取送貨,整個網絡較為有序,各物流中心主要為鄰近客戶點進行服務,有效減少了不合理運輸的現象。但是,圖5(b)采用各中心獨立運營模式,物流中心只服務對應的客戶,整體上存在大量交叉運輸、過遠運輸與迂回運輸的現象。(2)圖5(a)中,4個物流中心之間存在路徑連接,說明半掛式卡車在物流中心進行貨物調配,實現客戶訂單共享,而圖5(b)的4個物流中心之間不存在資源共享。(3)圖5(a)中,部分廂式貨車從一個物流中心出發,而到另一個物流中心終止服務,說明開放式網絡實現車輛與物流中心共享,從而提高車輛滿載率,減少空駛里程。然而,圖5(b)的各廂式貨車從一個物流中心出發,最終必須返回同一個物流中心,存在空駛里程,車輛有效利用率較低。(4)圖5(a)中,部分廂式貨車為降低總成本,通過違反少量軟時間窗約束,避免迂回運輸,從而減少總里程。圖5(b)中,由于每輛廂式貨車服務的客戶數較少,很少存在違反時間窗的現象,但總成本較高。

圖5 不同模式下pr03優化結果對比Fig.5 Optimization results of pr03 of different mode
4.2.3 不同聯盟下成本對比分析
在實際中,聯盟的成員數不同,其總成本的節約值也不同。以pr01數據集的路徑規劃結果為基礎,利用Shapley值法對各物流中心在不同合作聯盟下產生的利潤進行分配,結果如表3所示。

表3 優化后網絡的各聯盟利潤分配Table 3 Profit distribution of each alliance after optimization
其中,v0(U)是指在優化后的網絡中,各成員未合作情況下的成本之和,v(U)指成員合作情況下的聯盟總成本,φ(U)指聯盟合作后產生的共同利潤。觀察可知,在不同的聯盟情況下,當聯盟內企業數為2時,產生的平均共同利潤為2 219.3;當聯盟內企業數為3時,平均共同利潤為3 904;當聯盟內企業數為4時,平均共同利潤為6 589,即大聯盟產生的共同利潤最大。此外,在優化后的網絡中,各中心在聯盟前的利潤分別為313、432、997和1 298,而在大聯盟D中,各物流中心的利潤分別為1 760、1 494、1 776和1 559,對比可知大聯盟中各物流中心的利潤分配值最高,即大聯盟的穩定性最高。綜上所述,在一定程度下,參與聯盟的企業數越多,產生的共同利潤越大。
共享模式下的電子商務逆向物流,可以降低企業運輸成本,提高客戶滿意度,打通“第五利潤源”,而科學的車輛路徑規劃與合理的聯盟利潤分配是關鍵。本文針對多中心聯合取送貨的車輛路徑優化與利潤分配問題進行研究,結論如下:
(1)在共享車輛與客戶訂單的條件下,考慮客戶同時取送貨情景與時間窗約束,建立MJVRPSDPTW模型,對共享物流與VRPSDP問題做進一步延伸。
(2)設計一種基于大鄰域搜索的混合遺傳算法進行求解。首先,該算法基于虛擬中心,從整體上優化網絡。其次,將“破壞”與“修復”算子融入遺傳算法的鄰域搜索環節,增強了算法的局部尋優能力。通過多組算例對比實驗,證明本文算法優于兩階段規劃法與經典遺傳算法,驗證了模型及算法的有效性。
(3)基于優化后的網絡,利用Shapley值法對不同聯盟情況下的各物流企業進行利潤分配,結果證明大聯盟的共同利潤最大且聯盟最為穩定。
最后,本研究對多個物流企業開展共享物流模式具有一定的參考價值。但是,本文未考慮網絡的動態變化及客戶需求的不確定性。因此,時變交通網絡及客戶需求的不確定性是未來繼續研究的方向。