多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題研究

王 勇，羅思妤

(重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院，重慶 400074)

0 引 言

隨著電子商務(wù)的快速發(fā)展和市場需求的不斷增長，有限的物流服務(wù)設(shè)施資源與逐漸擴(kuò)大的物流需求規(guī)模之間的矛盾日益凸顯，城市物流網(wǎng)絡(luò)對設(shè)施協(xié)同性和資源配置時(shí)效性提出了更高的要求。共享運(yùn)輸經(jīng)濟(jì)的興起和第三方信息共享平臺(tái)的推廣，在創(chuàng)新配送與收集運(yùn)營模式，提高網(wǎng)絡(luò)資源利用和降低運(yùn)營成本等方面進(jìn)行了有效地探索和實(shí)踐，物流網(wǎng)絡(luò)合作聯(lián)盟應(yīng)運(yùn)而生[1]。研究多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題，有助于促進(jìn)共同配送與收集合作聯(lián)盟構(gòu)建和確保物流網(wǎng)絡(luò)收益的合理分配，并有利于深化物流企業(yè)之間的有效合作，加強(qiáng)網(wǎng)絡(luò)資源整合以及促進(jìn)城市物流系統(tǒng)的資源共享與可持續(xù)發(fā)展。國內(nèi)外學(xué)者的相關(guān)研究工作主要集中在多中心共同配送、多中心配送與收集以及物流合作聯(lián)盟等方面。

多中心共同配送網(wǎng)絡(luò)優(yōu)化可以實(shí)現(xiàn)區(qū)域內(nèi)配送路線的合理規(guī)劃，有效減少配送路線交叉重疊的現(xiàn)象，降低物流網(wǎng)絡(luò)運(yùn)營成本。在多中心共同配送網(wǎng)絡(luò)優(yōu)化問題研究方面，LIU Guike等[2]設(shè)計(jì)了一種模擬退火算法，研究了多中心共同配送的綠色車輛路徑問題，研究結(jié)果表明，共同配送相對于獨(dú)立配送模式，可以有效降低運(yùn)營總成本和碳排放量；LI Hongqi等[3]設(shè)計(jì)了一種基于節(jié)約算法的兩階段啟發(fā)式算法，研究了考慮物流設(shè)施實(shí)時(shí)轉(zhuǎn)運(yùn)能力變化的兩級多中心車輛路徑問題；ZHANG Wenyu等[4]設(shè)計(jì)了一種基于矩陣運(yùn)算的變鄰域搜索算法，研究了多中心合作的多中心車輛路徑問題，并通過不同目標(biāo)優(yōu)化間的比較驗(yàn)證了多目標(biāo)優(yōu)化的有效性; DENG Yirui等[5]設(shè)計(jì)了一種遺傳-禁忌混合算法，研究了考慮集中運(yùn)輸?shù)亩嘀行暮献鞯能囕v路徑問題，研究結(jié)果表明，合作環(huán)境下實(shí)施集中運(yùn)輸能提高資源利用率；盛虎宜等[6]提出一種改進(jìn)的蟻群算法，研究了引入共同配送策略的集送貨一體化車輛路徑問題，研究結(jié)果表明，多中心共同配送策略能夠有效縮短車輛行駛總距離和降低物流配送成本；王勇等[7]構(gòu)建了最小化配送成本的整數(shù)規(guī)劃模型，研究了多中心共同配送問題，并應(yīng)用最小費(fèi)用剩余節(jié)約方法(MCRS)對合作聯(lián)盟的收益分配問題進(jìn)行了研究。由此可知，多中心共同配送優(yōu)化能夠?qū)崿F(xiàn)網(wǎng)絡(luò)運(yùn)輸資源的優(yōu)化配置，并有效縮短配送距離和降低物流運(yùn)營總成本，而物流聯(lián)盟收益的合理分配是促進(jìn)聯(lián)盟成員合作的有效方法。

在多中心共同配送網(wǎng)絡(luò)優(yōu)化研究的基礎(chǔ)上，部分學(xué)者研究了多中心配送與收集網(wǎng)絡(luò)優(yōu)化問題。范厚明等[8]設(shè)計(jì)了一種自適應(yīng)變鄰域文化基因算法，研究了貨物收集需求隨機(jī)情況下的多中心共同配送與收集車輛路徑優(yōu)化問題；A.SORIANO等[9]提出一種改進(jìn)的自適應(yīng)大鄰域搜索算法，對多周期的多中心配送與收集問題進(jìn)行了研究，并通過對多中心離散需求的集中運(yùn)輸，實(shí)現(xiàn)網(wǎng)絡(luò)服務(wù)效率的有效提升；H.HERNNDEZ-PéREZ等[10]構(gòu)建了最小化網(wǎng)絡(luò)運(yùn)營成本的優(yōu)化模型，并設(shè)計(jì)一種分支定界算法研究了合作的配送與收集問題；徐東洋等[11]引入貪婪思想設(shè)計(jì)了基于大規(guī)模鄰域搜索的迭代局部搜索算法，研究了多中心配送與收集車輛路徑優(yōu)化問題；S.UMAR SHERIF 等[12]研究了貨物庫存成本、運(yùn)輸成本和碳排放成本在內(nèi)的運(yùn)營成本最小化的二級多中心配送與收集綠色車輛路徑優(yōu)化問題；B.OLGUN等[13]設(shè)計(jì)了一種基于局部搜索和可變鄰域下降方法的超啟發(fā)式算法，研究了多中心配送與收集的綠色車輛路徑問題。由此可知，多中心間離散需求的集中運(yùn)輸和轉(zhuǎn)運(yùn)調(diào)度可以有效減少長距離配送(收集)和交錯(cuò)運(yùn)輸?shù)痊F(xiàn)象，而合理化的集中運(yùn)輸和轉(zhuǎn)運(yùn)調(diào)度是多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟構(gòu)建的關(guān)鍵。

構(gòu)建穩(wěn)定的網(wǎng)絡(luò)聯(lián)盟，可以促進(jìn)配送與收集中心的有效合作，亦為提升網(wǎng)絡(luò)服務(wù)能力的重要途徑之一。WANG Yong等[14]設(shè)計(jì)了一種改進(jìn)的粒子群-蟻群混合算法，研究了兩級多中心配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題，研究結(jié)果表明，建立配送與收集合作聯(lián)盟比獨(dú)立的配送網(wǎng)絡(luò)聯(lián)盟更能有效提高物流網(wǎng)絡(luò)的服務(wù)效率和降低車輛使用數(shù)；YU Yang等[15]提出了一種精確算法，證明了配送中心和收集中心可以通過線路合作有效縮短車輛行駛距離和降低配送與收集運(yùn)營總成本，并提出了一種改進(jìn)的Shapley模型進(jìn)行合作聯(lián)盟成員的利潤分配；ZHANG Mengdi等[16]構(gòu)建了一個(gè)最大化聯(lián)盟利潤的整數(shù)線性規(guī)劃模型，研究了多中心合作的物流網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題，并探討了合作程度與合作聯(lián)盟規(guī)模對物流網(wǎng)絡(luò)的影響；LIU Lin等[17]提出了一種自適應(yīng)大鄰域搜索算法，研究了兩級多中心合作的車輛路徑優(yōu)化問題，研究結(jié)果表明，全局合作相對于局部合作可以有效降低物流網(wǎng)絡(luò)運(yùn)營總成本；H.FARVARESH 等[18]設(shè)計(jì)了一種分層啟發(fā)式算法，研究了帶時(shí)間窗的共同配送與收集車輛路徑問題，并提出了聯(lián)盟序列選擇方法和探討了合作聯(lián)盟穩(wěn)定性。文獻(xiàn)[14]～[18]主要為集中在合作聯(lián)盟網(wǎng)絡(luò)構(gòu)建和收益分配模型選擇等方面的研究，而在收益分配機(jī)制和多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟相結(jié)合方面的研究還有待進(jìn)一步深入。

筆者研究了多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題。首先，建立了網(wǎng)絡(luò)運(yùn)營總成本最小和車輛使用數(shù)量最少的雙目標(biāo)優(yōu)化模型，并提出了基于k-means聚類算法的Im-NSGA-Ⅱ混合算法，在混合算法中設(shè)計(jì)了貪婪算法生成高質(zhì)量初始可行解，并利用精英保留策略提高了混合算法的尋優(yōu)和收斂能力；其次，運(yùn)用MCRS方法對合作聯(lián)盟利潤進(jìn)行分配，并根據(jù)嚴(yán)格單調(diào)路徑原則和雪球理論對合作聯(lián)盟穩(wěn)定性進(jìn)行討論；最后，通過實(shí)例分析討論了不同合作模式對多中心配送與收集網(wǎng)絡(luò)的成本與車輛使用數(shù)的影響，進(jìn)而為解決物流共同配送與收集問題提供新的方法和途徑。

1 問題描述

合理的城市配送和收集網(wǎng)絡(luò)運(yùn)營體系是整個(gè)物流網(wǎng)絡(luò)降本增效的基礎(chǔ)。長期以來，由于各物流設(shè)施的建設(shè)時(shí)序不同、運(yùn)力能力有限、客戶服務(wù)契約關(guān)系限制等因素，導(dǎo)致配送與收集過程中交錯(cuò)運(yùn)輸、長距離運(yùn)輸?shù)炔缓侠磉\(yùn)輸現(xiàn)象頻發(fā)。利用互聯(lián)網(wǎng)等新型智能技術(shù)在線組建配送與收集合作聯(lián)盟，構(gòu)建多中心共同配送與收集網(wǎng)絡(luò)運(yùn)營體系，能夠有效降低多中心配送與收集網(wǎng)絡(luò)的運(yùn)營成本和提高網(wǎng)絡(luò)資源利用率；而合理的利潤分配機(jī)制能夠提高配送與收集網(wǎng)絡(luò)的穩(wěn)定性和可靠性，促進(jìn)物流網(wǎng)絡(luò)的可持續(xù)發(fā)展。

多中心共同配送與收集車輛路徑優(yōu)化問題聚焦于考慮配送與取貨需求服務(wù)關(guān)系變化和貨物調(diào)度運(yùn)輸，實(shí)現(xiàn)配送中心與取貨中心間的物流資源共享，從而降低配送與取貨網(wǎng)絡(luò)運(yùn)營成本，減少配送與收集車輛數(shù)量。多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化前后對比如圖1。在多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化前〔圖1(a)〕，配送中心、收集中心各自獨(dú)立運(yùn)營，導(dǎo)致了各個(gè)配送中心、收集中心的服務(wù)網(wǎng)絡(luò)交錯(cuò)重疊以及交錯(cuò)運(yùn)輸、長距離運(yùn)輸、違反客戶時(shí)間窗等現(xiàn)象的存在。在多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化后〔圖1(b)〕，由獨(dú)立運(yùn)營導(dǎo)致的各項(xiàng)問題得到相應(yīng)地解決。一方面，將配送客戶或取貨客戶分配給距離較近的物流設(shè)施，合理地劃分配送與收集服務(wù)區(qū)域，減少配送與收集網(wǎng)絡(luò)中的交錯(cuò)運(yùn)輸與長距離運(yùn)輸?shù)痊F(xiàn)象；另一方面，安排卡車集中調(diào)運(yùn)各個(gè)配送中心與收集中心間的貨物，有效地協(xié)調(diào)各個(gè)配送與收集區(qū)域間的客戶需求與物流資源，進(jìn)而實(shí)現(xiàn)網(wǎng)絡(luò)資源的集約化，減少配送與收集車輛數(shù)量。同時(shí)，優(yōu)化配送與收集服務(wù)區(qū)域內(nèi)與區(qū)域間的車輛路線，能夠快速響應(yīng)客戶的時(shí)間窗需求，降低網(wǎng)絡(luò)運(yùn)營總成本，并提高客戶滿意度。如圖1(b)，將原本由DC2進(jìn)行服務(wù)的客戶C5改變?yōu)橛蒁C1進(jìn)行服務(wù)，能夠使客戶C5的時(shí)間窗要求得以滿足；車輛從DC1出發(fā)完成客戶C4和C5的配送任務(wù)后，執(zhí)行客戶C23和客戶C24的收集任務(wù)，隨后返回取貨中心PC1，能夠減少配送與收集車輛數(shù)量。

圖1 多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化前后對比Fig. 1 The comparison before and after the multi-center joint distribution and pickup network optimization

圖1中實(shí)線與虛線上的數(shù)值分別表示卡車與車輛的行駛時(shí)間，配送中心與取貨中心時(shí)間窗的開始時(shí)間為卡車和車輛的出發(fā)時(shí)間。假設(shè)卡車單位時(shí)間的運(yùn)輸成本為45元，配送與收集車輛單位時(shí)間的運(yùn)輸成本為40元，違反客戶時(shí)間窗的單位時(shí)間的懲罰成本為35元，每輛卡車的維護(hù)成本為18元，每輛配送與收集車輛的維護(hù)成本為15元，每個(gè)配送中心與收集中心參與合作時(shí)能夠獲得100元合作激勵(lì)。表1展示了多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)前后的運(yùn)營指標(biāo)對比。結(jié)果表明，多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化消除了違反客戶時(shí)間窗的現(xiàn)象，降低了配送與收集成本、配送與收集車輛維護(hù)成本，進(jìn)而使運(yùn)營總成本從2 705元降低至2 111元，使配送與收集車輛使用數(shù)量從11輛降低為9輛。

表1 多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化前后各項(xiàng)成本與車輛使用數(shù)對比Table 1 Comparison of the costs and the number of vehicles before and after the multi-center jointdistribution and pickup network optimization

2 模型建立

2.1 符號定義

為構(gòu)建多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化數(shù)學(xué)模型，筆者定義了多中心共同配送與收集網(wǎng)絡(luò)中的物流設(shè)施、客戶、車輛等集合及物流設(shè)施容量、客戶需求、車輛行駛時(shí)間等變量。多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化問題的變量定義如表2。

表2 模型相關(guān)變量定義Table 2 The definition of the related variables for the model

2.2 模型構(gòu)建

以多中心共同配送與收集網(wǎng)絡(luò)運(yùn)營總成本H最小化和配送與收集車輛使用數(shù)量U最小化為目標(biāo)，建立多中心共同配送與收集雙目標(biāo)優(yōu)化模型：

minH=H1+H2+H3+H4

(1)

(2)

式中：H1為僅執(zhí)行配送任務(wù)和僅執(zhí)行收集車輛的運(yùn)輸成本和維護(hù)成本；H2為同時(shí)執(zhí)行配送和收集任務(wù)車輛的運(yùn)輸成本和維護(hù)成本；H3為用于配送中心與收集中心間貨物調(diào)運(yùn)卡車的運(yùn)輸成本和維護(hù)成本；H4為配送中心與收集中心的固定成本和配送與收集車輛違反客戶時(shí)間窗的懲罰成本，并考慮合作激勵(lì)，如式(3)～(6)：

(3)

(4)

(5)

(6)

約束條件：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

αi≤tiv≤βi(?i∈I,?v∈V)

(20)

t′mv+tmiv-M(1-xmiv)≤tiv(?m∈M,?i∈I,

i≠m)

(21)

t′mv+tmiv+M(1-xmiv)≥tiv(?m∈M,?i∈I,

i≠m)

(22)

αj≤tjv≤βj(?j∈J,?v∈V)

(23)

t′nv+tnjv-M(1-xnjv)≤tjv(?m∈M,?j∈J,j≠m)

(24)

t′nv+tnjv+M(1-xnjv)≥tjv(?m∈M,?j∈J,j≠m)

(25)

t′iv+tijv-M(1-xijv)≤atjv(?i,j∈C,i≠j,?v∈V)

(26)

t′iv+tijv+M(1-xijv)≥tjv(?i,j∈C,i≠j,

?v∈V)

(27)

(28)

(29)

(30)

(31)

(32)

(33)

(34)

Zd={0,1} (?d∈D)

(35)

Zp={0,1} (?p∈P)

(36)

ydd′s={0,1} (?d,d′∈D,d≠d′,?s∈S)

(37)

ypp′s={0,1} (?p,p′∈P,p≠p′,?s∈S)

(38)

xdiv={0,1} (?d∈D,?i∈I,?v∈V)

(39)

xpjv={0,1} (?p∈P,?j∈J,?v∈V)

(40)

xmiv={0,1} (?m∈M,?i∈I,i≠m,?v∈V)

(41)

xnjv={0,1} (?n∈N,?j∈J,j≠m,?v∈V)

(42)

xijv={0,1} (?i,j∈C,i≠j,?v∈V)

(43)

Edid′={0,1} (?d,d′∈D,d≠d′,?i∈I)

(44)

Epjp′={0,1} (?p,p′∈P,p≠p′,?j∈J)

(45)

式(7)表示每個(gè)配送客戶僅由一輛從配送中心出發(fā)的車輛進(jìn)行服務(wù)；式(8)和式(9)表示每個(gè)收集客戶僅由一輛從收集中心出發(fā)的獨(dú)立執(zhí)行收集服務(wù)的車輛進(jìn)行服務(wù)，或者僅由一輛同時(shí)執(zhí)行配送和收集服務(wù)的車輛進(jìn)行服務(wù)；式(10)～(12)表示配送與收集車輛在服務(wù)一個(gè)客戶后，離開該客戶去服務(wù)下一個(gè)客戶；式(13)～(14)分別表示獨(dú)立執(zhí)行配送服務(wù)車輛和獨(dú)立執(zhí)行收集服務(wù)車輛的裝載量不超過車輛的最大裝載量；式(15)表示同時(shí)執(zhí)行配送和收集服務(wù)車輛的裝載量不超過車輛的最大裝載量；式(16)～(17)表示卡車的裝載量不超過最大裝載量；式(18)～(19)分別表示配送和收集的貨物量不超過配送中心和收集中心的最大容量；式(20)表示每輛配送車輛在配送客戶的時(shí)間窗內(nèi)對其進(jìn)行服務(wù)；式(21)～(22)表示配送車輛到達(dá)配送客戶的時(shí)間；式(23)表示每輛收集車輛在收集客戶的時(shí)間窗內(nèi)對其進(jìn)行服務(wù)；式(24)～(25)表示收集車輛到達(dá)收集客戶的時(shí)間；式(26)～(27)表示同時(shí)執(zhí)行配送和收集的車輛到達(dá)收集客戶的時(shí)間；式(28)～(30)表示配送與收集車輛的行駛時(shí)間不超過路線允許的最大行駛時(shí)間；式(31)～(32)表示集中調(diào)運(yùn)的貨物運(yùn)輸量等于改變客戶服務(wù)關(guān)系的客戶總需求量；式(33)～(34)表示消除線路上的子回路；式(35)～(45)表示決策變量。

3 基于k-means聚類算法的Im-NSGA-Ⅱ混合算法

為了求解多中心共同配送與收集雙目標(biāo)優(yōu)化模型，筆者提出了基于k-means聚類算法的Im-NSGA-Ⅱ混合算法。首先，設(shè)計(jì)k-means聚類算法對多中心配送與收集網(wǎng)絡(luò)的服務(wù)區(qū)域進(jìn)行合理地劃分，將客戶分配給臨近的物流設(shè)施；其次，根據(jù)k-means聚類算法的結(jié)果，設(shè)計(jì)貪婪算法在各個(gè)服務(wù)區(qū)域內(nèi)與服務(wù)區(qū)域間生成初始的車輛行駛路線；最后，利用NSGA-Ⅱ?qū)囕v行駛路線進(jìn)行優(yōu)化，進(jìn)而生成多中心配送與收集優(yōu)化線路?；趉-means聚類算法的Im-NSGA-Ⅱ混合算法的流程如圖2。

圖2 基于k-means聚類算法的Im-NSGA-Ⅱ混合算法流程Fig. 2 Flow chart of the hybrid algorithm based on Im-NSGA-Ⅱ and k-means clustering algorithm

3.1 k-means聚類算法

對客戶進(jìn)行聚類分析，合理地劃分多中心共同配送與收集網(wǎng)絡(luò)中各中心的服務(wù)區(qū)域，一方面能夠減少多中心共同配送與收集網(wǎng)絡(luò)中的交錯(cuò)運(yùn)輸、長距離運(yùn)輸?shù)痊F(xiàn)象，降低多中心共同配送與收集網(wǎng)絡(luò)運(yùn)營總成本；另一方面將多中心車輛路徑優(yōu)化問題轉(zhuǎn)化為單中心車輛路徑優(yōu)化問題，降低了混合算法的計(jì)算復(fù)雜度，并通過將客戶分配給臨近的設(shè)施，減少初始可行解的總行駛距離，加快混合算法的搜索速度。k-means聚類算法過程如下：

Step 1輸入配送中心和收集中心的數(shù)量和位置坐標(biāo)，輸入配送客戶和收集客戶的位置坐標(biāo)。

Step 2判斷參與合作的物流設(shè)施是否僅包含配送中心或者收集中心，如果滿足判斷條件，則轉(zhuǎn)到Step 3；如果不滿足判斷條件，則轉(zhuǎn)至Step 4。

Step 3設(shè)置k個(gè)配送中心或者收集中心作為初始聚類中心。

Step 4設(shè)置k={k1,k2}個(gè)配送中心和收集中心作為初始聚類中心，其中包含k1個(gè)配送中心，k2個(gè)收集中心。

Step 5計(jì)算每個(gè)客戶到初始聚類中心的距離，將每個(gè)客戶分配給臨近的聚類中心。

Step 6更新k個(gè)聚類中心，重新評價(jià)每個(gè)客戶到新聚類中心的距離。

Step 7重復(fù)Step 5～Step 6, 將所有客戶逐一分配給聚類中心，且聚類中心穩(wěn)定不變。

Step 8計(jì)算最新的聚類中心到每個(gè)配送中心與收集中心的距離，將各個(gè)聚類中心的客戶簇群分配給臨近的配送中心或收集中心。

Step 9輸出聚類結(jié)果。

3.2 基于k-means聚類算法的Im-NSGA-Ⅱ混合算法的實(shí)現(xiàn)過程

根據(jù)“先聚類，后優(yōu)化”的思想[19]，運(yùn)用基于k-means聚類算法的Im-NSGA-Ⅱ混合算法求解多中心共同配送與收集雙目標(biāo)優(yōu)化模型，相關(guān)變量定義如表3。

表3 算法相關(guān)變量定義Table 3 The definition of the related variables for the algorithm

混合算法的具體實(shí)現(xiàn)過程如下：

Step 1設(shè)置最大優(yōu)化次數(shù)γ_max、最大迭代次數(shù)run_max、種群規(guī)模pop_size、染色體選擇概率ρsel、染色體交叉概率ρcro以及染色體變異概率ρmut等算法相關(guān)參數(shù)。

Step 2設(shè)計(jì)貪婪算法生成初始可行解。運(yùn)用掃描算法[20]生成初始解直至初始父代種群Parent_γ的種群規(guī)模達(dá)到pop_size大小，此時(shí)設(shè)置γ=1，run=1。Step 2.1～Step 2.3為貪婪算法生成初始可行解的過程：

Step 2.1計(jì)算任意兩個(gè)配送客戶或者收集客戶節(jié)點(diǎn)之間形成的路徑的距離，并按距離值分別將路徑從小到大排序。

Step 2.2依次判斷路徑是否為子路徑，如果是子路徑即添加到當(dāng)前路徑中，否則直接判斷下一路徑。判斷子路徑的規(guī)則：①添加該路徑后不會(huì)使任何節(jié)點(diǎn)的連接邊數(shù)量大于2；②添加該路徑不會(huì)使路徑閉合；③添加該路徑生成的單條路徑中的客戶總需求不超過車輛最大裝載量；④添加該路徑時(shí)滿足客戶的時(shí)間窗要求。

Step 2.3執(zhí)行Step 2.2直到?jīng)]有子路徑存在，此時(shí)將每條路徑的兩個(gè)端點(diǎn)分別與配送中心或收集中心連接形成閉合回路。

Step 3評價(jià)初代父代種群Parent_γ中每個(gè)個(gè)體的雙目標(biāo)函數(shù)值H(網(wǎng)絡(luò)運(yùn)營總成本)和U(配送與收集車輛使用數(shù))，并構(gòu)造Pareto非支配解集[21]，執(zhí)行非支配排序操作以及計(jì)算個(gè)體的擁擠距離。

Step 4執(zhí)行精英保留策略，根據(jù)適應(yīng)度函數(shù)值，選擇當(dāng)前初代父代種群Parent_γ中適應(yīng)度值較高的一定數(shù)量的個(gè)體記錄為精英個(gè)體。此類精英個(gè)體得以保留，不參與隨后的遺傳選擇、交叉和變異操作。

Step 5對非精英個(gè)體執(zhí)行遺傳選擇、交叉和變異操作以生成子代個(gè)體。過程主要包括：運(yùn)用錦標(biāo)賽選擇方法選擇父代個(gè)體[22]；采用部分映射交叉算子對父代個(gè)體進(jìn)行交叉操作；采用反轉(zhuǎn)突變算子對個(gè)體基因進(jìn)行變異操作[23]。

Step 6在Step 5生成的子代個(gè)體中，用Step 4保留的精英個(gè)體替換遺傳交叉和變異操作后適應(yīng)度值較低的個(gè)體，以此生成新子代種群Offspring_γ。

Step 7結(jié)合初代父代種群Parent_γ和新子代種群Offspring_γ生成新一代種群，新種群大小為2倍pop_size，并根據(jù)新種群中每個(gè)個(gè)體非支配排序的Rank值和擁擠距離，選擇個(gè)體組成新一代父代種群Parent_(γ+1)，Parent_(γ+1)種群大小為pop_size。

Step 8令run=run+1，判斷當(dāng)前迭代次數(shù)run是否達(dá)到最大值run_max。若run≤run_max，返回k-means聚類算法Step 6；若run≥run_max，則轉(zhuǎn)到該混合算法Step 9。

Step 9令γ=γ+1，判斷當(dāng)前優(yōu)化代數(shù)γ是否達(dá)到最大值γ_max。若γ≤γ_max，返回該混合算法Step 3；若γ≥γ_max,結(jié)束混合算法的循環(huán)迭代操作。

Step 10輸出Pareto最優(yōu)解集，在Pareto最優(yōu)解集中選擇最優(yōu)解[23]，結(jié)束算法。

3.3 算法檢驗(yàn)

為了驗(yàn)證筆者提出的Im-NSGA-Ⅱ混合算法的有效性，將Im-NSGA-Ⅱ混合算法與NSGA-Ⅱ[24]和多目標(biāo)遺傳算法(MOGA)[25]進(jìn)行比較。實(shí)驗(yàn)數(shù)據(jù)采用Cordeau標(biāo)準(zhǔn)算例[26]，并根據(jù)多中心共同配送與收集網(wǎng)絡(luò)特征進(jìn)行修改，如表4。根據(jù)已有相關(guān)文獻(xiàn)[27,28]，設(shè)置算法參數(shù)如表5?？紤]到啟發(fā)式算法結(jié)果存在隨機(jī)性, 每組實(shí)驗(yàn)運(yùn)算10次，并選取10次運(yùn)算結(jié)果中的最優(yōu)解和對應(yīng)的運(yùn)算時(shí)間進(jìn)行對比，如表6。

表4 數(shù)據(jù)集特征Table 4 The characteristics of the data sets

表5 混合算法參數(shù)設(shè)置Table 5 Parameter setting of the hybrid algorithm

表6 不同算法的計(jì)算結(jié)果對比Table 6 Calculation results comparison of different algorithms

將Im-NSGA-Ⅱ混合算法與NSGA-Ⅱ和MOGA求解的成本進(jìn)行t檢驗(yàn)和p值檢驗(yàn)，得到t檢驗(yàn)值分別為-10.004 9和-7.089 91，p值分別為3.14E-09和7.14E-07，由此可知，Im-NSGA-Ⅱ算法與NSGA-Ⅱ和MOGA算法求解得到的成本值結(jié)果存在顯著性差異。由表6可知，Im-NSGA-Ⅱ混合算法與NSGA-Ⅱ和MOGA求解所得的成本結(jié)果存在顯著性差異。在成本方面，Im-NSGA-Ⅱ混合算法求解的物流成本平均值為2 735.06元，比NSGA-Ⅱ求解的物流成本平均值2 852.52元降低了4.12%，比MOGA求解的物流成本平均值2 908.38元降低了5.96%；在車輛使用數(shù)量方面，Im-NSGA-Ⅱ混合算法求解的車輛使用數(shù)量平均值為16輛，低于NSGA-Ⅱ和MOGA求解得到的車輛使用數(shù)量；在運(yùn)算時(shí)間方面，Im-NSGA-Ⅱ混合算法的平均運(yùn)算時(shí)間為155.15 s，比 NSGA-Ⅱ的平均運(yùn)算時(shí)間162.35 s節(jié)約了7.2 s，比 MOGA的平均運(yùn)算時(shí)間164.65 s節(jié)約了9.5 s。結(jié)果表明：筆者提出的Im-NSGA-Ⅱ混合算法相對于NSGA-Ⅱ和MOGA具有更好的搜索能力和尋優(yōu)能力。

4 合作聯(lián)盟的利潤分配

4.1 基于MCRS法的利潤分配模型

通過多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化，能夠節(jié)約配送與收集網(wǎng)絡(luò)運(yùn)營總成本，節(jié)約的運(yùn)營總成本即為合作聯(lián)盟可能獲得的利潤。多中心共同配送與收集網(wǎng)絡(luò)在線組建合作聯(lián)盟，由第三方物流平臺(tái)提供協(xié)商等一系列支持，因此聯(lián)盟A的利潤Φ(A)是在第三方物流平臺(tái)收取δ比例的利潤后得到，如式(46)：

Φ(A)=(1-δ)×max{∑r∈AΨ0(r)-Ψ(A),0}

(46)

MCRS方法通常用于研究合作過程中各聯(lián)盟成員的利潤分配問題[7]。根據(jù)表2中的相應(yīng)變量定義，應(yīng)用MCRS方法計(jì)算合作聯(lián)盟成員的利潤分配值，如式(47):

(47)

(48)

(49)

s.t.:

φr(A,θ)≥φ0(r) (r∈A)

(50)

(51)

4.2 合作聯(lián)盟序列選擇及穩(wěn)定性檢驗(yàn)

假定穩(wěn)定的合作聯(lián)盟構(gòu)建基于合作聯(lián)盟形成過程中每個(gè)成員獲得的利潤隨著新成員的加入而逐漸增加，因此，利用嚴(yán)格單調(diào)路徑選擇原則[14]對合作聯(lián)盟建立的序列進(jìn)行選擇。第o個(gè)成員加入聯(lián)盟π時(shí)聯(lián)盟成員r的利潤增加百分比如式(52):

(52)

為了進(jìn)一步加強(qiáng)合作聯(lián)盟的穩(wěn)定性，選用合理的利潤分配方法能夠確保對聯(lián)盟利潤進(jìn)行公平地分配。根據(jù)雪球理論[7]，利潤分配方案與核心值之間距離值越小，越能夠保證利潤分配的合理性，核心值計(jì)算公式如式(53):

(53)

5 算例及結(jié)果分析

5.1 算例相關(guān)數(shù)據(jù)

筆者以重慶市某企業(yè)的物流網(wǎng)絡(luò)為例進(jìn)行研究，其中DC1，DC2，DC3表示配送中心，PC1，PC2表示收集中心，C1～C180表示客戶點(diǎn)，配送中心、收集中心和客戶點(diǎn)的相應(yīng)地理位置分布如圖3。

圖3 多中心配送與收集網(wǎng)絡(luò)地理位置分布Fig. 3 Geographical location of multi-center distributionand pickup network

根據(jù)已有文獻(xiàn)和實(shí)際調(diào)研[14,23,27]，相應(yīng)參數(shù)設(shè)置如下：pop_size=100，γ_max=250，run_max=10，ρsel=0.7，ρcro=0.9，ρmut=0.2，fs=0.106；hs=3.4，fv=0.053，hv=3.9，ue=0.2，ud=0.3，Gs=10 000，Gv=1 000，W=52，F(xiàn)1=800，F(xiàn)2=850，F(xiàn)3=950，F(xiàn)4=700，F(xiàn)5=800，Qs=600，Qv=200，c1=600，c2=650，c3=750，c4=500，c5=600，δ=0.1。

5.2 多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化方案

應(yīng)用MATLAB R2016b軟件運(yùn)用筆者提出的k-means聚類算法計(jì)算得到各配送中心與收集中心的服務(wù)區(qū)域范圍，如圖4。應(yīng)用MATLAB R2016b軟件運(yùn)用Im-NSGA-Ⅱ算法計(jì)算得到優(yōu)化后的配送與收集車輛路徑，如表7。

圖4 配送中心與收集中心服務(wù)區(qū)域Fig. 4 The service area of distribution center and pickup center

表7 多中心共同配送與收集車輛路徑方案Table 7 Vehicle routing schemes of multi-center joint distribution and pickup network

由圖4可知，多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化方法通過將客戶分配給臨近的配送中心或收集中心，從而對物流配送與收集服務(wù)區(qū)域進(jìn)行合理地劃分，有效地減少了原有服務(wù)區(qū)域重疊的問題。表7中，多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化前車輛使用數(shù)為19輛，其中DC1使用4輛車，DC2使用4輛車，DC3使用3輛車，PC1使用4輛車，PC2使用4輛車；多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化后車輛使用數(shù)至11輛，其中DC1使用2輛車，DC2使用3輛車，DC3使用4輛車，PC1使用1輛車，PC2使用1輛車，各配送中心與收集中心使用車輛數(shù)均得到了降低。由此可知，多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化方法通過對物流配送與收集服務(wù)區(qū)域內(nèi)與區(qū)域間的車輛路徑進(jìn)行優(yōu)化，有效地降低了配送與收集車輛使用數(shù)。

5.3 多中心共同配送與收集合作聯(lián)盟

5.3.1 多中心配送與收集合作聯(lián)盟構(gòu)建

運(yùn)用式(47)計(jì)算配送與收集合作聯(lián)盟利潤值，并對多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化前后的相關(guān)成本及車輛使用數(shù)進(jìn)行對比分析，如表8。多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化前后的配送成本、收集成本、懲罰成本、運(yùn)營總成本和配送與收集車輛使用數(shù)對比情況如圖5。

表8 多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化前后對比Table 8 Comparison before and after multi-center joint distribution and pickup alliance optimization

圖5 多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化前后的運(yùn)營總成本和車輛使用數(shù)對比Fig. 5 Comparison of the total operating cost and the number ofused vehicles before and after multi-center joint distribution andpickup alliance optimization

由表8和圖5可知，多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化前，網(wǎng)絡(luò)運(yùn)營總成本為43 702 元，配送與收集車輛使用數(shù)為19輛；多中心共同配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化后，網(wǎng)絡(luò)運(yùn)營總成本降低至29 088元，配送與收集車輛使用數(shù)減少至11輛。因此，組建合作聯(lián)盟能夠有效地降低網(wǎng)絡(luò)運(yùn)營總成本和車輛使用數(shù)，同時(shí)合理地分配合作聯(lián)盟所得利潤，從而增強(qiáng)合作聯(lián)盟的穩(wěn)定性。

5.3.2 多中心配送與收集合作聯(lián)盟序列選擇

利用式(52)計(jì)算合作聯(lián)盟中的每個(gè)配送中心與收集中心的利潤增加百分比，如圖6。當(dāng)配送中心和收集中心以{PC1,PC2,DC2,DC3,DC1}序列加入合作聯(lián)盟時(shí)，能夠確保每個(gè)配送中心和收集中心的利潤增加百分比隨著新聯(lián)盟成員的加入而嚴(yán)格遞增。首先，PC1和PC2合作，PC1的利潤增加百分比由13.10% 提高至24.59%；然后，DC2加入合作聯(lián)盟，PC1的利潤增加百分比由24.59% 提高至34.05%，PC2的利潤增加百分比由23.58% 提高至35.09%；其次，DC3加入合作聯(lián)盟，使得PC1的利潤增加百分比提高至37.80%，PC2的利潤增加百分比提高到37.69%，DC2的利潤增加百分比由26.73% 提高至41.10%；最后，DC1加入合作聯(lián)盟，使得各合作聯(lián)盟成員利潤增加百分比達(dá)到40.74%、40.54%、42.46%、40.46%和37.33%。

圖6 多中心配送與收集合作聯(lián)盟序列Fig. 6 The sequence of multi-center distribution and pickup collaborative alliances

5.3.3 多中心配送與收集合作聯(lián)盟穩(wěn)定性

選用合適的利潤分配方法有利于提高合作聯(lián)盟穩(wěn)定性。利用式(53)計(jì)算得出核心值，并將MCRS、CGA、EPM和Shapley方法計(jì)算得出的利潤分配方案與核心值進(jìn)行對比(圖7)。由圖7可知，MCRS得出的利潤分配方案優(yōu)于CGA、EPM和Shapley方法得出的利潤分配方案。

圖7 利潤分配方案與核心值比較Fig. 7 Comparison of profit allocation scheme and core value

5.3.4 不同合作模式下多中心共同配送與收集網(wǎng)絡(luò)對比分析

為進(jìn)一步探討合作模式對多中心共同配送與收集網(wǎng)絡(luò)的影響，筆者將合作模式分為僅配送中心共享、僅收集中心共享和多中心共同配送與收集，并對3種不同合作模式下的網(wǎng)絡(luò)成本和車輛使用數(shù)進(jìn)行對比分析，如圖8和表9。

圖8 不同合作模式下運(yùn)營總成本與車輛使用數(shù)量對比Fig. 8 Comparison of the total operating cost and the number ofused vehicles based on different cooperation modes

表9 不同合作模式下多中心共同配送與收集網(wǎng)絡(luò)優(yōu)化方案比較Table 9 Comparison of multi-center joint distribution and pickup optimization schemes based on different cooperation modes

由圖8和表9可知，在運(yùn)營總成本方面，多中心共同配送與收集模式下的網(wǎng)絡(luò)運(yùn)營總成本為26 088元，小于僅配送中心共享模式下的網(wǎng)絡(luò)運(yùn)營總成本33 476元及僅收集中心共享模式下的網(wǎng)絡(luò)運(yùn)營總成本36 192元；在車輛使用數(shù)方面，多中心共同配送與收集模式下的車輛使用數(shù)為11輛，小于僅配送中心共享模式下的車輛使用數(shù)15輛及僅收集中心共享模式下的車輛使用數(shù)16輛。在配送與收集共享路線數(shù)方面，多中心共同配送與收集模式下的共享路線數(shù)為5條，小于僅配送中心共享模式下的共享路線數(shù)3條及僅收集中心共享模式下的共享路線數(shù)1條。因此，配送中心與收集中心間的合作更能充分地優(yōu)化物流資源配置，從而帶來更明顯的資源整合優(yōu)勢，降低網(wǎng)絡(luò)運(yùn)營成本，提高網(wǎng)絡(luò)運(yùn)行效率。

6 結(jié) 論

筆者針對多中心配送與收集網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題，首先，構(gòu)建了物流運(yùn)營總成本最小化和車輛使用數(shù)最小化的雙目標(biāo)優(yōu)化模型；其次，提出了結(jié)合k-means聚類算法和Im-NSGA-Ⅱ算法的混合啟發(fā)式算法，并在Im-NSGA-Ⅱ算法中設(shè)計(jì)了貪婪算法生成初始可行解和采用精英保留策略提高了算法的尋優(yōu)能力；然后，將Im-NSGA-Ⅱ混合算法與NSGA-Ⅱ算法和MOGA算法進(jìn)行了對比分析，驗(yàn)證了筆者所提混合算法的有效性；最后，應(yīng)用MCRS方法進(jìn)行多中心配送與收集合作聯(lián)盟的利潤分配研究，按照嚴(yán)格單調(diào)路徑原則確定聯(lián)盟最優(yōu)序列選擇過程并與其他方法比較驗(yàn)證了合作聯(lián)盟穩(wěn)定性。

以重慶市某企業(yè)的配送與收集網(wǎng)絡(luò)為例，驗(yàn)證了筆者提出的模型和算法的有效性。計(jì)算結(jié)果表明，優(yōu)化后的多中心共同配送與收集網(wǎng)絡(luò)物流運(yùn)營總成本和車輛使用數(shù)分別減少了17 614元和8輛。此外，不同合作模式下的比較結(jié)果表明，相對于僅配送中心共享模式，多中心共同配送與收集共享模式物流運(yùn)營總成本和車輛使用數(shù)分別減少了7 388元和4輛，而相對于僅收集中心共享模式，多中心共同配送與收集共享模式物流運(yùn)營總成本和車輛使用數(shù)分別減少了10 104元和5輛。因此，筆者所提模型和算法可用于第三方物流企業(yè)進(jìn)行多中心共同配送與收集網(wǎng)絡(luò)設(shè)計(jì)以及多中心合作聯(lián)盟構(gòu)建。研究結(jié)果可為多中心共同配送與收集優(yōu)化問題提供新的研究思路，并有利于推動(dòng)城市智慧物流、共享物流服務(wù)模式和數(shù)據(jù)驅(qū)動(dòng)的物流與供應(yīng)鏈可持續(xù)發(fā)展。