李麗瀅，羅繼康，牛莉霞

（遼寧工程技術(shù)大學(xué) 工商管理學(xué)院，葫蘆島 125000）

0 引言

隨著生鮮電商的快速發(fā)展，人們對(duì)于高質(zhì)量生鮮商品的需求得以滿(mǎn)足。生鮮商品由于具有保存不易、易腐等特性，配送難度高于普通貨物。若配送路徑規(guī)劃不合理，則會(huì)導(dǎo)致配送時(shí)間長(zhǎng)，使生鮮商品的損耗和配送成本增加[1]。國(guó)家下發(fā)的《“十四五”冷鏈物流發(fā)展規(guī)劃》中提出要優(yōu)化冷鏈物流網(wǎng)絡(luò)，健全冷鏈物流服務(wù)體系，聚焦“肉類(lèi)、水果、蔬菜等生鮮食品以及疫苗等醫(yī)藥產(chǎn)品[2]。科學(xué)合理的冷鏈物流配送體系是冷鏈物流企業(yè)降本增效的必要條件，多中心冷鏈共同配送是提高冷鏈配送服務(wù)質(zhì)量的重要手段。研究新鮮度約束下的多中心冷鏈共同配送及利潤(rùn)分配有助于實(shí)現(xiàn)冷鏈物流企業(yè)之間資源的合理配置，提高交付商品的新鮮度，降低企業(yè)運(yùn)營(yíng)成本，促進(jìn)冷鏈物流產(chǎn)業(yè)的可持續(xù)發(fā)展。近年來(lái)，眾多學(xué)者對(duì)于多中心冷鏈共同配送路徑優(yōu)化及利潤(rùn)分配問(wèn)題進(jìn)行了一系列的研究。

針對(duì)冷鏈物流配送的車(chē)輛路徑問(wèn)題研究中，LI等[3]以生鮮商品配送成本最小化為目標(biāo)，設(shè)計(jì)自適應(yīng)模擬退火變異遺傳算法求解，為生鮮物流企業(yè)提供了配送方案。趙志學(xué)、劉長(zhǎng)石、王寧等[4-6]針對(duì)考慮生鮮商品新鮮度的冷鏈物流車(chē)輛路徑問(wèn)題，分別利用自適應(yīng)改進(jìn)的蟻群算法、改進(jìn)的蟻群算法和單親遺傳算法進(jìn)行求解，研究表明冷鏈物流企業(yè)配送時(shí)考慮生鮮商品的新鮮度可以有效降低企業(yè)成本。趙邦磊[7]等設(shè)計(jì)改進(jìn)的ACO算法，解決了多目標(biāo)優(yōu)化的冷鏈配送模型。李軍濤等[8]設(shè)計(jì)自適應(yīng)災(zāi)變遺傳算法，有效的解決了模糊時(shí)間窗下的冷鏈物流配送路徑優(yōu)化問(wèn)題。舒輝、張佳佳、王思洪等[9-11]分別設(shè)計(jì)自適應(yīng)遺傳算法、粒子群算法、GAMS與遺傳算法相結(jié)合解決冷鏈物流配送路徑優(yōu)化問(wèn)題。王勇等[12]綜合考慮客戶(hù)時(shí)間窗和生鮮商品溫度控制，建立生鮮商品配送成本最少和生鮮商品價(jià)值損失最小的雙目標(biāo)模型，并設(shè)計(jì)GA-TS混合算法進(jìn)行求解。DEVAPRIYA等[13]利用進(jìn)化的啟發(fā)式算法研究易腐商品運(yùn)輸優(yōu)化問(wèn)題，結(jié)果表明生鮮商品的配送車(chē)輛比普通商品的配送車(chē)輛在物流成本、客戶(hù)滿(mǎn)意度、交付生鮮商品新鮮度等方面有更高的要求。由上述文獻(xiàn)可知，生鮮商品的配送研究主要集中于單中心配送，并且考慮在新鮮度約束下的生鮮商品配送研究較少。因此考慮新鮮度約束下多中心生鮮配送研究還有待進(jìn)一步深度拓展。

在多中心共同配送以及合作利潤(rùn)分配的研究中，葉勇等[14]建立了車(chē)輛總行駛路徑最小的目標(biāo)模型，設(shè)計(jì)狼群算法進(jìn)行求解。葛嘉怡等[15]構(gòu)建改進(jìn)模糊Shapley值的收益分配模型對(duì)醫(yī)藥冷鏈?zhǔn)找孢M(jìn)行分配。辜勇、FITRIANA等[16,17]針對(duì)多中心協(xié)同配送下的車(chē)輛路徑問(wèn)題，將大規(guī)模多配送中心路徑問(wèn)題轉(zhuǎn)換為多個(gè)單配送中心路徑問(wèn)題，設(shè)計(jì)改進(jìn)蟻群算法求解該模型，證明了該模型的有效性。葛顯龍等[18]研究了前置倉(cāng)獨(dú)立配送與協(xié)作配送的生鮮配送問(wèn)題，設(shè)計(jì)改進(jìn)的遺傳算法進(jìn)行求解。范厚明等[19]在已有的研究基礎(chǔ)上，在多中心共同配送問(wèn)題中考慮客戶(hù)集貨的隨機(jī)需求，設(shè)計(jì)預(yù)優(yōu)化和重優(yōu)化兩階段對(duì)路徑進(jìn)行規(guī)劃，深化了多中心共同配送相關(guān)的理論研究。饒衛(wèi)振等[20]設(shè)計(jì)貪婪算法和大鄰域搜索算法構(gòu)成的兩階段算法，從理論視角下計(jì)算車(chē)輛協(xié)作與不協(xié)作狀態(tài)下的配送距離和能耗量。BEN ALAIA等[21]研究了封閉式多車(chē)輛多中心配集貨車(chē)輛路徑優(yōu)化問(wèn)題，利用遺傳算法和粒子群算法對(duì)該問(wèn)題進(jìn)行求解，但是未考慮到利潤(rùn)分配問(wèn)題。FERNáNDEZ等[22]研究了共享客戶(hù)資源的協(xié)作車(chē)輛問(wèn)題，通過(guò)對(duì)基礎(chǔ)實(shí)例集進(jìn)行計(jì)算，與非共享客戶(hù)資源模式進(jìn)行比較，得出獨(dú)立運(yùn)營(yíng)商合作具有潛在效益的結(jié)論。王勇等[23]設(shè)計(jì)混合啟發(fā)式算法求解網(wǎng)絡(luò)運(yùn)營(yíng)成本最小和車(chē)輛使用數(shù)最小的雙目標(biāo)模型，運(yùn)用最小費(fèi)用剩余節(jié)約方法（MCRS）求解多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟的利潤(rùn)分配問(wèn)題，為可持續(xù)的城市物流網(wǎng)絡(luò)規(guī)劃和共享物流合作聯(lián)盟的構(gòu)建提供決策支持。由上述文獻(xiàn)可知，多配送中心共同配送問(wèn)題方面的研究已取得了一系列的進(jìn)展，進(jìn)而對(duì)多中心冷鏈物流共同配送以及共同配送所帶來(lái)的利潤(rùn)進(jìn)行分配等方面提供了研究切入。

綜上所知，現(xiàn)有的文獻(xiàn)主要集中在將冷鏈物流、多中心共同配送、聯(lián)盟利潤(rùn)分配分開(kāi)進(jìn)行研究，將冷鏈物流、多中心共同配送并對(duì)聯(lián)盟利潤(rùn)進(jìn)行分配結(jié)合考慮的研究涉及較少。其次，學(xué)者大多研究的是企業(yè)共享客戶(hù)資源和所有車(chē)輛?？紤]到現(xiàn)實(shí)中存在企業(yè)之間進(jìn)行共同配送時(shí)，共享客戶(hù)資源但只共享轉(zhuǎn)運(yùn)車(chē)輛的形式。鑒于此，本文針對(duì)生鮮商品的特性，在滿(mǎn)足交付商品新鮮度約束的前提下，建立轉(zhuǎn)運(yùn)車(chē)輛和配送車(chē)輛的固定成本、運(yùn)輸成本、制冷成本、貨損成本以及時(shí)間窗懲罰成本之和最小為目標(biāo)的車(chē)輛路徑優(yōu)化模型，設(shè)計(jì)一種基于K-means聚類(lèi)的改進(jìn)混合蟻群算法進(jìn)行求解。最后通過(guò)Shapley值法對(duì)冷鏈物流企業(yè)組建聯(lián)盟所獲得的共同利潤(rùn)進(jìn)行合理分配，通過(guò)對(duì)比聯(lián)盟組建前后企業(yè)的成本，證明該模型的可行性。本文的研究對(duì)豐富和完善當(dāng)前的冷鏈配送網(wǎng)絡(luò)具有重要的現(xiàn)實(shí)意義。

1 模型構(gòu)建

1.1 問(wèn)題描述

目前大部分冷鏈物流企業(yè)擁有各自的物流中心和若干客戶(hù)，由于物流中心建設(shè)時(shí)序、客戶(hù)契約關(guān)系等因素，物流中心之間很少有合作關(guān)系，各自獨(dú)立完成配送服務(wù)。如圖1中a所示，這種配送方式會(huì)出現(xiàn)過(guò)遠(yuǎn)運(yùn)輸、交叉運(yùn)輸和生鮮商品損壞、違反時(shí)間窗等問(wèn)題。如果企業(yè)之間建立多中心冷鏈共同配送聯(lián)盟，共享客戶(hù)資源，共享轉(zhuǎn)運(yùn)車(chē)輛，就可以消除以上弊端。如圖1中b所示，企業(yè)冷鏈物流中心1、2、3分別將各自?xún)蓚€(gè)配送距離較遠(yuǎn)的客戶(hù)交由其他兩個(gè)企業(yè)進(jìn)行配送，使用冷藏卡車(chē)在物流中心1、2、3之間轉(zhuǎn)運(yùn)因客戶(hù)服務(wù)關(guān)系轉(zhuǎn)變的生鮮商品，然后各個(gè)物流中心使用冷藏貨車(chē)根據(jù)客戶(hù)的地理位置、時(shí)間窗和生鮮商品的新鮮度要求對(duì)客戶(hù)進(jìn)行服務(wù)，以配送成本最小化為目標(biāo)優(yōu)化配送路線(xiàn)，實(shí)現(xiàn)物流網(wǎng)絡(luò)中資源的有效利用。最后，不合理的利潤(rùn)分配機(jī)制會(huì)導(dǎo)致聯(lián)盟成員的利潤(rùn)分配不均，合作關(guān)系不會(huì)維持很久。因此，基于優(yōu)化后的網(wǎng)絡(luò)，利用合作博弈論中的Shapely值法，將節(jié)約成本作為聯(lián)盟的利潤(rùn)分配值，通過(guò)衡量聯(lián)盟內(nèi)成員對(duì)聯(lián)盟節(jié)約值帶來(lái)的邊際貢獻(xiàn)值進(jìn)行利潤(rùn)分配，保證聯(lián)盟合作關(guān)系的穩(wěn)定。

圖1 多中心冷鏈共同配送聯(lián)盟建立前后對(duì)比

1.2 符號(hào)說(shuō)明

1）集合

節(jié)點(diǎn)集合Z={1,2,...,n,n+1,...,n+m}；

配送客戶(hù)集合M={1,2,...,m}；

生鮮物流中心集合N={1,2,...,n}；

L：在物流中心之間轉(zhuǎn)運(yùn)資源的冷藏卡車(chē)集合，l∈L；

K：物流中心進(jìn)行配送的冷藏貨車(chē)集合，k∈K

2）參數(shù)

f1：冷藏卡車(chē)l的固定成本

f2：冷藏貨車(chē)k的固定成本

c1：冷藏卡車(chē)l的單位運(yùn)輸成本

c2：冷藏貨車(chē)k的單位運(yùn)輸成本

Dij：物流中心i到物流中心j的距離

dij：客戶(hù)i到客戶(hù)j的距離

Tijl：冷藏卡車(chē)從物流中心i到物流中心j的時(shí)間

Tijk：冷藏貨車(chē)從客戶(hù)點(diǎn)i到客戶(hù)點(diǎn)j行駛時(shí)間

b1、b2：冷藏卡車(chē)開(kāi)門(mén)時(shí)和運(yùn)輸時(shí)的單位時(shí)間制冷成本

λ1、λ2：冷藏貨車(chē)開(kāi)門(mén)時(shí)和運(yùn)輸時(shí)的單位時(shí)間制冷成本

[αi,bi]：客戶(hù)i的時(shí)間窗

δ：生鮮商品單位產(chǎn)品價(jià)值

α：冷藏貨車(chē)早于αi到達(dá)客戶(hù)點(diǎn)i的懲罰系數(shù)

β：冷藏貨車(chē)晚于bi到達(dá)客戶(hù)點(diǎn)i的懲罰系數(shù)

Qij：物流中心i調(diào)配到物流中心j的送貨量

Pij：物流中心i調(diào)配到物流中心j的取貨量

Qt：時(shí)間點(diǎn)t時(shí)冷藏卡車(chē)在物流中心之間調(diào)配的實(shí)時(shí)裝載量

qi：配送客戶(hù)i的需求量

Gl：冷藏卡車(chē)l的最大裝載量

Gk：冷藏貨車(chē)k的最大裝載量

3）決策變量

Xijk：冷藏貨車(chē)從客戶(hù)點(diǎn)i出發(fā)到客戶(hù)點(diǎn)j時(shí)為1，否則為0，其中i,j∈M；

Yk：冷藏貨車(chē)k被使用時(shí)為1，否則為0；

Wijl：冷藏卡車(chē)l是從物流中心i出發(fā)到物流中心j為1，否則為0，其中i,j∈N

Yl：冷藏卡車(chē)l被使用時(shí)為1，否則為0。

Erij：客戶(hù)r的服務(wù)關(guān)系從物流中心i轉(zhuǎn)移到物流中心j時(shí)為1，否則為0，r∈M，i,j∈N

1.3 模型構(gòu)建

1.3.1 新鮮度約束

生鮮商品具有易損性，配送時(shí)間和配送距離會(huì)影響生鮮商品的新鮮度，在運(yùn)輸過(guò)程中會(huì)產(chǎn)生貨損成本，生鮮商品的新鮮度衰減函數(shù)表達(dá)如式(1)：

其中，θ(t)為生鮮商品t時(shí)刻的新鮮度，θ0為生鮮商品的初始新鮮度，為新鮮度衰減系數(shù)，要求θ(ti)≥Gb，ti為到達(dá)客戶(hù)點(diǎn)i的時(shí)間，Gb為商品交付時(shí)要滿(mǎn)足客戶(hù)的最低新鮮度。

1.3.2 成本模型

本文所研究的新鮮度限制約束下多中心冷鏈共同配送模型問(wèn)題以車(chē)輛固定成本、運(yùn)輸成本、制冷成本、貨損成本和時(shí)間窗懲罰成本之和最小化建立模型：

1）C1為冷藏卡車(chē)和冷藏貨車(chē)的固定成本

固定成本主要包括駕駛員工資、車(chē)輛的固定費(fèi)用等，與車(chē)輛使用數(shù)成正比。

2）C2冷藏卡車(chē)和冷藏貨車(chē)的運(yùn)輸成本

運(yùn)輸成本主要包括冷藏卡車(chē)和冷藏貨車(chē)的保養(yǎng)維修、油費(fèi)等。

3）C3為冷藏卡車(chē)和冷藏貨車(chē)的制冷成本

制冷成本主要包括冷藏卡車(chē)和冷藏貨車(chē)運(yùn)輸時(shí)為了保持車(chē)廂溫度恒定所產(chǎn)生的費(fèi)用以及防止卸貨時(shí)車(chē)門(mén)敞開(kāi)導(dǎo)致車(chē)廂溫度上升所產(chǎn)生的預(yù)冷費(fèi)用。

4）C4為生鮮商品的貨損成本

由于裝卸時(shí)間相較于運(yùn)輸時(shí)間較短，因此貨損成本只包括物流中心之間運(yùn)輸生鮮商品和物流中心配送商品過(guò)程中產(chǎn)生的貨損成本。

5）C5為時(shí)間窗懲罰成本

懲罰成本指生鮮商品無(wú)法在顧客規(guī)定的時(shí)間窗內(nèi)送達(dá)產(chǎn)生的成本。

1.4 約束條件

式(8)表示所有的客戶(hù)只被冷藏貨車(chē)服務(wù)一次；式(9)表示車(chē)輛k將貨物送到客戶(hù)點(diǎn)i時(shí)產(chǎn)品新鮮度必須大于等于產(chǎn)品保質(zhì)的最低標(biāo)準(zhǔn)；式(10)表示車(chē)輛k從物流中心O出發(fā)，完成客戶(hù)點(diǎn)服務(wù)后返回物流中心O；式(11)表示冷藏卡車(chē)l只在物流中心之間調(diào)配貨物；式(12)表示冷藏貨車(chē)k只用來(lái)服務(wù)客戶(hù)；式(13)表示冷藏卡車(chē)l調(diào)配貨物時(shí)的載重量不超過(guò)其最大載重量；式(14)表示冷藏貨車(chē)k服務(wù)客戶(hù)i時(shí)的載重量不超過(guò)其最大載重量；式(15)表示到達(dá)客戶(hù)點(diǎn)j的時(shí)間等于冷藏卡車(chē)到達(dá)物流中心i的時(shí)間與冷藏貨車(chē)到達(dá)客戶(hù)點(diǎn)j的時(shí)間之和；式(16)表示冷藏卡車(chē)從物流中心i調(diào)配到物流中心j的送貨量；式(17)表示冷藏卡車(chē)從物流中心j調(diào)配到物流中心i的集貨量；式(18)表示消除子回路。

2 基于K-means聚類(lèi)的混合蟻群算法

針對(duì)多中心冷鏈共同配送車(chē)輛路徑優(yōu)化模型，設(shè)計(jì)基于K-means聚類(lèi)的混合蟻群算法來(lái)求解該模型。根據(jù)客戶(hù)的地理位置，通過(guò)K-means聚類(lèi)算法計(jì)算客戶(hù)點(diǎn)距離物流中心的歐氏距離，并將其分配到離該客戶(hù)距離最近的物流中心。應(yīng)用節(jié)約算法形成各聚類(lèi)單元初始路線(xiàn)。然后設(shè)計(jì)改進(jìn)混合的蟻群算法對(duì)各聚類(lèi)單元之間的路徑進(jìn)行優(yōu)化，其中將局部搜索算法的局部尋優(yōu)能力應(yīng)用于容易陷入局部最優(yōu)的蟻群算法，通過(guò)不斷迭代，最終得到最優(yōu)配送路線(xiàn)。

2.1 K-means聚類(lèi)算法

本文使用的K-means聚類(lèi)算法是在聚類(lèi)點(diǎn)坐標(biāo)已知的前提下，計(jì)算各個(gè)客戶(hù)點(diǎn)到聚類(lèi)點(diǎn)的歐式距離，根據(jù)計(jì)算結(jié)果將客戶(hù)點(diǎn)分配到距離最近的聚類(lèi)點(diǎn)，確定客戶(hù)和物流中心的服務(wù)關(guān)系。假設(shè)物流中心i的坐標(biāo)為(xi,yi)，客戶(hù)點(diǎn)j的坐標(biāo)為(xj,yj)，則客戶(hù)與物流中心的計(jì)算公式為：

2.1.1 改進(jìn)的混合蟻群算法

多中心冷鏈物流車(chē)輛路徑優(yōu)化模型屬于VRP的拓展問(wèn)題，它是在經(jīng)典VRP的基礎(chǔ)上考慮多中心、客戶(hù)時(shí)間窗、新鮮度等因素，屬于NP-hard問(wèn)題。蟻群算法屬于啟發(fā)式算法，可以依靠其較強(qiáng)的魯棒性和搜索較優(yōu)解等優(yōu)點(diǎn)，有效的解決路徑優(yōu)化問(wèn)題。但是蟻群算法收斂速度慢并且容易陷入局部最優(yōu)。通過(guò)設(shè)計(jì)動(dòng)態(tài)信息素?fù)]發(fā)因子更新機(jī)制和信息素增量獎(jiǎng)勵(lì)機(jī)制來(lái)幫助算法跳出局部最優(yōu)。另外，局部搜索算法可通過(guò)插入、互換、2-opt操作提高算法的局部搜索能力，進(jìn)而提高算法的全局搜索能力。因此，本文旨在將蟻群算法的全局尋優(yōu)能力和局部搜索算法的局部?jī)?yōu)化能力相結(jié)合，從而快速求得最優(yōu)解。算法流程如圖2所示。

圖2 改進(jìn)的混合蟻群算法流程

2.1.2 構(gòu)建路徑

在蟻群算法中，螞蟻在剛開(kāi)始搜索時(shí)具有盲目性，所以采用文獻(xiàn)[24]中節(jié)約矩陣原理形成初始路線(xiàn)。路徑上信息素濃度的高低和啟發(fā)函數(shù)重要程度因子的大小決定螞蟻選擇下一路徑的概率。為了形成最優(yōu)路徑，避免陷入局部最優(yōu)，設(shè)計(jì)確定性選擇和隨機(jī)性選擇相結(jié)合的策略，并且在轉(zhuǎn)移概率公式內(nèi)引入車(chē)輛等待時(shí)間與時(shí)間窗寬度啟發(fā)式因子，利用輪盤(pán)賭去選擇下一個(gè)要轉(zhuǎn)移的點(diǎn)。轉(zhuǎn)移概率如式(20)所示：

其中：Tabuk記錄螞蟻已經(jīng)走過(guò)的路徑，τij(t)為t時(shí)刻路徑i、j上的信息素，為t時(shí)刻路徑i、j的可見(jiàn)度，width=bj-αj為時(shí)間窗寬度，α、β、γ、λ分別為信息素因子、啟發(fā)式因子、時(shí)間窗寬度因子、等待時(shí)間因子，Pc為轉(zhuǎn)移規(guī)則的參數(shù)，Pc=[0，1]。

2.1.3 自適應(yīng)信息素因子更新機(jī)制

螞蟻從客戶(hù)點(diǎn)i到下一個(gè)客戶(hù)點(diǎn)j會(huì)分泌一種叫“信息素”的化學(xué)物質(zhì)，螞蟻會(huì)根據(jù)路徑上信息素濃度的高低選擇下一個(gè)要走的路徑。同時(shí)信息素也會(huì)揮發(fā)，當(dāng)螞蟻經(jīng)過(guò)所有客戶(hù)點(diǎn)后，需要對(duì)全局路徑上的信息素進(jìn)行更新，通過(guò)不斷迭代最終螞蟻找到最優(yōu)路徑。信息素更新公式為：

信息素?fù)]發(fā)系數(shù)ρ的取值影響著蟻群算法的全局搜索能力和收斂速度，ρ值過(guò)大，算法容易陷入局部最優(yōu)，ρ值過(guò)小算法收斂速度過(guò)快。為了快速準(zhǔn)確的得到最優(yōu)路徑，設(shè)計(jì)一種動(dòng)態(tài)信息素?fù)]發(fā)系數(shù)更新機(jī)制，如式(23)所示：

其中：N為當(dāng)前迭代次數(shù)，N_max為最大迭代次數(shù)，ρmin為信息素?fù)]發(fā)因子最小值。

式(22)中Δτij(t)表示本次迭代中路徑i，j上信息素的增量，表示螞蟻k在路徑i，j上留下的信息素。為了進(jìn)一步增強(qiáng)算法的全局尋優(yōu)能力和加快收斂速度，設(shè)計(jì)一種信息素獎(jiǎng)勵(lì)機(jī)制：記錄當(dāng)前最優(yōu)路徑為Route_best，計(jì)算每次迭代螞蟻的路徑長(zhǎng)度為Route_iter，若Route_iter＜Route_best，則對(duì)該螞蟻?zhàn)哌^(guò)的路徑進(jìn)行信息素獎(jiǎng)勵(lì)，采用式(24)，若Route_iter≥Route_best，則采用正常信息素更新方式，采用式(25)。

2.1.4 局部搜索算法

蟻群算法容易陷入“早熟”，得到的解不一定是全局最優(yōu)解。為了彌補(bǔ)這一缺陷，增大解的空間性，在每次迭代的最優(yōu)解的基礎(chǔ)上，引入“插入”、“互換”、“2-opt”局部搜索操作，對(duì)路徑內(nèi)進(jìn)行搜索。若操作后的成本小于操作前的成本則保留該路徑。若操作后的成本大于操作前的成本，則保留操作前的路徑。操作方式如下：

1）插入操

在路徑上隨機(jī)選擇兩個(gè)客戶(hù)點(diǎn)i、j，將客戶(hù)點(diǎn)j從路徑中刪除，然后將客戶(hù)點(diǎn)j插入到客戶(hù)點(diǎn)i的后面，如圖3所示。

圖3 插入

2）互換操

在路徑上隨機(jī)選擇兩個(gè)客戶(hù)點(diǎn)i、j，將客戶(hù)點(diǎn)i的位置和客戶(hù)點(diǎn)j的位置進(jìn)行互換，如圖4所示。

圖4 互換

3）2-opt

在路徑上隨機(jī)選擇兩個(gè)客戶(hù)點(diǎn)i、j，客戶(hù)點(diǎn)i保持不變，倒序排列客戶(hù)點(diǎn)i、j間的客戶(hù)，如圖5所示。

圖5 2-opt

2.2 算法檢驗(yàn)

為了驗(yàn)證改進(jìn)的混合蟻群算法的有效性，將該算法與改進(jìn)的蟻群算法[25]、遺傳算法進(jìn)行對(duì)比分析。選取Cordeau的數(shù)據(jù)集（http://iescm.com/vrp/instances/P5MDVRPTW.asp）中pr01-pr04作為驗(yàn)證算例基礎(chǔ)，數(shù)據(jù)集中物流中心數(shù)為4，客戶(hù)規(guī)模分別為48、96、144、192，并附加客戶(hù)需求量、客戶(hù)關(guān)系、客戶(hù)服務(wù)時(shí)間，對(duì)比結(jié)果如表1。其次選取文獻(xiàn)[25]中的多中心配送問(wèn)題實(shí)例進(jìn)行檢驗(yàn)，該算例包括4個(gè)物流中心和48個(gè)客戶(hù)點(diǎn)坐標(biāo)、需求、時(shí)間窗以及服務(wù)時(shí)間，對(duì)比結(jié)果如表2所示。其中TL為行駛路徑，TC為總成本，AVG/%為平均值改進(jìn)幅度。

表1 MDVRPTW標(biāo)準(zhǔn)算例對(duì)比

表2 MDVRPTW實(shí)例對(duì)比

編程采用MatlabR2021a進(jìn)行開(kāi)發(fā)，操作系統(tǒng)為Windows10，電腦內(nèi)存為8G，CPU為Intel i5-11260H，主頻為2.6GHz。關(guān)鍵參數(shù)設(shè)置如下：螞蟻數(shù)量m=客戶(hù)數(shù)×1.5，最大迭代次數(shù)inter_max=100，選擇概率Pc=0.7，交叉概率Pm=0.8。

對(duì)四組規(guī)模不同的算例的計(jì)算結(jié)果如表1所示，本文所提出的改進(jìn)的混合蟻群算法在總行駛路徑和總成本方面均優(yōu)于改進(jìn)的蟻群算法和遺傳算法。在平均行駛路徑方面，改進(jìn)混合蟻群算法計(jì)算得到的平均行駛距離比改進(jìn)的蟻群算法減少了6.8%，比遺傳算法減少了11.5%。在平均總成本方面，改進(jìn)的混合蟻群算法的計(jì)算結(jié)果比改進(jìn)的蟻群算法節(jié)約了8.1%，比遺傳算法節(jié)約了11.7%。

對(duì)文獻(xiàn)[25]的實(shí)例數(shù)據(jù)計(jì)算5次結(jié)果如表2所示，本文所提出的改進(jìn)蟻群算法所求平均行駛路徑和平均總成本分別是1278.8元、27804.3千米，比改進(jìn)蟻群算法減少12.6%、18.5%，比遺傳算法降低了17.8%、23.2%。其中表3為最優(yōu)車(chē)輛行駛路線(xiàn)。

表3 改進(jìn)的混合蟻群算法最優(yōu)路徑

根據(jù)上述對(duì)比結(jié)果可知，改進(jìn)的混合蟻群算法在求解質(zhì)量上比其他算法有更大的優(yōu)勢(shì)。其主要原因在于設(shè)計(jì)的動(dòng)態(tài)信息素衰減系數(shù)、信息素獎(jiǎng)勵(lì)機(jī)制和局部搜索操作提高了算法的全局尋優(yōu)能力，避免了算法陷入局部最優(yōu)。證明了改進(jìn)的混合蟻群算法在求解MDVRPTW問(wèn)題的有效性。

3 基于Shapley值的利潤(rùn)分配模型

多家冷鏈物流企業(yè)成立聯(lián)盟，共享客戶(hù)資源和轉(zhuǎn)運(yùn)車(chē)輛，最大的收益是成本的降低。聯(lián)盟將這部分成本節(jié)約值作為利潤(rùn)進(jìn)行分配，并將利潤(rùn)合理、準(zhǔn)確分配給參與聯(lián)盟的物流企業(yè)來(lái)保證聯(lián)盟的穩(wěn)定運(yùn)行。合作博弈論理論中Shapley值法是Shapley LS（1953）[26]所提出的求解多人合作的利潤(rùn)分配方法，本文選用該方法進(jìn)行利潤(rùn)分配。

3.1 聯(lián)盟可分配利潤(rùn)

假設(shè)聯(lián)盟的參與者有N個(gè)成員，則能夠形成2N-1個(gè)聯(lián)盟子集，其中T=(1,2,3…,t)為N的任意一個(gè)子集，V(T)為定義在N上的一個(gè)實(shí)數(shù)值函數(shù)，即V(T)是聯(lián)盟T可分配的利潤(rùn)，C(T)為聯(lián)盟T的總成本，C(i)為成員i獨(dú)立運(yùn)營(yíng)成本。每個(gè)聯(lián)盟的成本節(jié)約值為該聯(lián)盟的利潤(rùn)分配值，計(jì)算方法如式(26)所示：

3.2 聯(lián)盟成員利潤(rùn)分配值

Shapley值模型的核心是根據(jù)每個(gè)成員對(duì)聯(lián)盟所做的貢獻(xiàn)程度進(jìn)行分配利潤(rùn)。根據(jù)式(27)計(jì)算結(jié)果可知聯(lián)盟的可分配利潤(rùn)值，根據(jù)式(28)計(jì)算每個(gè)成員i在聯(lián)盟中可分得利潤(rùn)。

其中：Ti為包含成員i的聯(lián)盟，|T|為聯(lián)盟中成員個(gè)數(shù)，w(|T|)為加權(quán)因子，V(T)為聯(lián)盟總收益，V(T/i)為除去成員i獲得的收益，[V(T)-V(T/i)]為成員i在聯(lián)盟中所產(chǎn)生的邊際貢獻(xiàn)，為聯(lián)盟成員所分得收益值。

4 算例分析

本文所提出的模型為帶時(shí)間窗的多中心車(chē)輛配送問(wèn)題，選取MDVRPTW標(biāo)準(zhǔn)算例（https//github.com/PariseC/Algorithms_for_solving_VRP/tree/master/data/MDVRPTW）來(lái)驗(yàn)證模型的可行性，隨機(jī)選取該算例的50個(gè)客戶(hù)，算例有3個(gè)物流中心，客戶(hù)服務(wù)關(guān)系是[1,3]的隨機(jī)整數(shù)。

算例參數(shù)設(shè)置如下：冷藏卡車(chē)的載重Gl=20t，冷藏貨車(chē)的載重為Gk=10t，冷藏卡車(chē)單位固定成本f1=800元/輛，冷藏卡車(chē)單位運(yùn)輸成本c1=16元/km，冷藏貨車(chē)車(chē)單位固定成本f2=400元/輛，冷藏貨車(chē)單位運(yùn)輸成本c2=9元/km，車(chē)輛平均行駛速度為V=60km/h，冷藏卡車(chē)開(kāi)門(mén)時(shí)和運(yùn)輸過(guò)程中單位時(shí)間制冷成本分別為λ1=50元/h，λ2=0.8元/km，冷藏貨車(chē)開(kāi)門(mén)時(shí)和運(yùn)輸過(guò)程中單位時(shí)間制冷成本分別為b1=20元/h，b1=0.3元/km，生鮮商品的單位價(jià)值δ=5元，生鮮商品的腐敗率δ=0.002，時(shí)間窗早到等待因子=30元/h，時(shí)間窗晚到懲罰因子β=50元/h，產(chǎn)品最低新鮮度要求Gb=0.75。算法參數(shù)設(shè)置：螞蟻數(shù)量m=50，最大迭代次數(shù)inter_max=100，信息素重要程度因子α=1，啟發(fā)函數(shù)重要程度因子β=3，等待時(shí)間重要程度因子λ=2，時(shí)間窗跨度重要因子γ=3，更新信息素濃度常數(shù)Q=5，信息素獎(jiǎng)勵(lì)系數(shù)μ=1.5，選擇概率Pc=0.7，交叉概率Pm=0.8。

4.1 不同配送模式下路徑和成本分析

應(yīng)用K-means聚類(lèi)算法確定客戶(hù)的服務(wù)關(guān)系，表4為聚類(lèi)前服務(wù)關(guān)系歸屬表，表5為聚類(lèi)后服務(wù)關(guān)系歸屬表。應(yīng)用改進(jìn)的混合蟻群算法計(jì)算不同配送模式下總行駛距離和成本，表6為獨(dú)立運(yùn)營(yíng)模式和共同配送模式下對(duì)比結(jié)果。由對(duì)比結(jié)果可知：

表4 聚類(lèi)前服務(wù)關(guān)系歸屬表

表5 聚類(lèi)后服務(wù)關(guān)系歸屬表

表6 不同模式下優(yōu)化結(jié)果

1）獨(dú)立運(yùn)營(yíng)模式下各個(gè)企業(yè)冷鏈物流中心之間的客戶(hù)資源未共享，各個(gè)物流中心之間不存在資源的集中調(diào)配，總行駛距離為1752.13千米，車(chē)輛行駛路徑圖如圖6所示。在共同配送模式下，共享客戶(hù)資源減少了大量的過(guò)遠(yuǎn)運(yùn)輸、交叉運(yùn)輸?shù)龋傂旭偩嚯x為947.42千米，比獨(dú)立配送減少了45.9%，車(chē)輛行駛路徑圖如圖7所示。

圖6 物流中心獨(dú)立運(yùn)營(yíng)模式下路徑優(yōu)化結(jié)果

圖7 物流中心共同配送模式下路徑優(yōu)化結(jié)果

2）獨(dú)立運(yùn)營(yíng)模式總成本為19994.83元，而共同配送模式下總成本為14627.59元，減少了行駛距離和車(chē)輛使用數(shù)，使配送順序和車(chē)輛調(diào)配更合理，故使成本下降26.8%。

4.2 不同聯(lián)盟模式下利潤(rùn)分配分析

聯(lián)盟規(guī)模的大小會(huì)影響聯(lián)盟最后的利潤(rùn)。假設(shè)上述算例中DC1、DC2、DC3分別為三家冷鏈物流企業(yè)A、B、C的物流中心，利用Shapley值法計(jì)算每個(gè)企業(yè)在不同聯(lián)盟中的利潤(rùn)。如果三個(gè)企業(yè)未組建聯(lián)盟，各自單獨(dú)配送，各自從聯(lián)盟獲利0元。若企業(yè)A和企業(yè)B組建聯(lián)盟，可產(chǎn)生共同利潤(rùn)2275.68元，企業(yè)A和企業(yè)C組建聯(lián)盟，可產(chǎn)生共同利潤(rùn)533.53元，企業(yè)B和企業(yè)C組建聯(lián)盟，可產(chǎn)生共同利潤(rùn)574.63元。如果企業(yè)A、B和企業(yè)C達(dá)成共識(shí)組建聯(lián)盟，可產(chǎn)生共同利潤(rùn)4792.24元。

利用Shapley值利益分配模型（式(27)、式(28)）計(jì)算建立聯(lián)盟后企業(yè)A、B、C的利潤(rùn)分配值。結(jié)果如表7所示，當(dāng)企業(yè)A與企業(yè)B建立聯(lián)盟時(shí)可分得的利潤(rùn)均為1137.84元，當(dāng)企業(yè)A與企業(yè)C建立聯(lián)盟時(shí)可分得的利潤(rùn)均為266.665元，當(dāng)企業(yè)B和企業(yè)C建立聯(lián)盟時(shí)可分的利潤(rùn)均為287.315元，但當(dāng)企業(yè)A、B、C共同組建聯(lián)盟時(shí)可分的利潤(rùn)分別為2874.07元、1894.63元、1023.54元。通過(guò)對(duì)比不同聯(lián)盟組合下的利潤(rùn)分配值發(fā)現(xiàn)，組建成大聯(lián)盟之后，聯(lián)盟的整體運(yùn)營(yíng)成本比小聯(lián)盟運(yùn)營(yíng)成本降低更多，各成員比獨(dú)立配送和兩兩組建聯(lián)盟所獲得的利潤(rùn)值更明顯。

表7 不同聯(lián)盟體下的利潤(rùn)分配表

5 結(jié)語(yǔ)

冷鏈物流企業(yè)之間建立聯(lián)盟有助于優(yōu)化當(dāng)前物流網(wǎng)絡(luò)，可以大幅降低企業(yè)成本，而科學(xué)合理規(guī)劃車(chē)輛路徑和建立聯(lián)盟利潤(rùn)分配機(jī)制是關(guān)鍵。本文對(duì)于多中心共同配送及利潤(rùn)分配進(jìn)行了研究，得到了以下的結(jié)論：

1）本文提出的多中心冷鏈共同配送車(chē)輛路徑優(yōu)化問(wèn)題，可以解決物流中心獨(dú)立配送中過(guò)遠(yuǎn)運(yùn)輸、交叉運(yùn)輸、生鮮商品交付時(shí)新鮮度低的弊端。

2）運(yùn)用K-means聚類(lèi)算法對(duì)客戶(hù)進(jìn)行分類(lèi)，引入節(jié)約算法提高了初始解的質(zhì)量，通過(guò)改進(jìn)蟻群算法概率轉(zhuǎn)移規(guī)則、設(shè)計(jì)動(dòng)態(tài)更新信息素衰減系數(shù)和信息素獎(jiǎng)勵(lì)機(jī)制，提高了算法的全局搜索能力，最后結(jié)合局部搜索算法提高了算法的局部搜索能力。通過(guò)選取標(biāo)準(zhǔn)算例和實(shí)例分別進(jìn)行計(jì)算，證明本文算法的求解質(zhì)量?jī)?yōu)于改進(jìn)蟻群算法和經(jīng)典遺傳算法，證明了本文算法的有效性。

3）根據(jù)算例計(jì)算結(jié)果證明，多中心冷鏈配送聯(lián)盟能夠有效的減少冷鏈企業(yè)車(chē)輛配送距離、車(chē)輛使用數(shù)量進(jìn)而提高了企業(yè)的利潤(rùn)，并且聯(lián)盟規(guī)模越大企業(yè)可獲得的利潤(rùn)越多。

本文的研究能夠?yàn)槎鄠€(gè)企業(yè)建立多中心冷鏈共同配送聯(lián)盟提供較好的解決方案，但是本文未考慮不同溫度下的生鮮商品和客戶(hù)的動(dòng)態(tài)需求。因此，在多中心共同配送聯(lián)盟的研究中考慮不同溫度下的生鮮商品和客戶(hù)動(dòng)態(tài)需求是下一步研究的方向。