王 勇,周 雪,劉 永,許茂增
(重慶交通大學(xué),經(jīng)濟與管理學(xué)院,重慶 400074)
共享經(jīng)濟的發(fā)展為城市物流多中心共同配送網(wǎng)絡(luò)構(gòu)建帶來了新的機遇,而實現(xiàn)配送車輛在多個中心之間的合理化共享調(diào)度,是城市物流配送企業(yè)獲取最大化市場收益的關(guān)鍵。第三方物流的快速發(fā)展,使得物流配送企業(yè)可以通過車輛租賃方式實現(xiàn)車輛的使用和共享,進而拓展其物流配送能力。多中心共同配送網(wǎng)絡(luò)構(gòu)建涉及穩(wěn)健的網(wǎng)絡(luò)聯(lián)盟構(gòu)建和合作機制設(shè)計,而基于車輛共享的多中心共同配送網(wǎng)絡(luò)可以實現(xiàn)物流配送效率的有效提升和物流資源的集約化利用。國內(nèi)外學(xué)者在多中心共同配送和車輛共享調(diào)度方面進行了一系列研究。
在多中心共同配送問題方面,盛虎宜等[1]設(shè)計了一種改進的蟻群算法,研究了多中心聯(lián)合配送的生鮮品半開放式車輛路徑問題。劉明等[2]提出一種混合協(xié)同配送模式,并應(yīng)用改進的啟發(fā)式搜索算法研究了應(yīng)急物資的配送問題。范厚明等[3]研究了生鮮商品多中心共同配送問題,并應(yīng)用蟻群算法求解了冷藏車的配送路徑。王勇等[4]提出改進的遺傳—粒子群混合優(yōu)化算法,研究了多中心共同配送的收益分配優(yōu)化問題。LI等[5]應(yīng)用一種基于儲蓄的變鄰域搜索算法,研究了考慮實時轉(zhuǎn)運能力變化的兩級多中心共同配送問題。WANG等[6]提出一種基于蟻群與遺傳算法的混合算法,研究了兩級設(shè)施多中心共同配送問題。由上述文獻可知,多中心共同配送問題方面的研究已取得了一系列的進展,但在多中心共同配送的合作序列選擇以及合作聯(lián)盟構(gòu)建等方面還需進一步拓展研究。
在車輛共享調(diào)度方面,劉家利等[7]提出了不同配送中心間的車輛共享機制,研究了企業(yè)運力不足時車輛租賃和自有車輛的調(diào)度決策問題。JIN等[8]研究了純電動汽車的共享模式,并提出了應(yīng)用多種定價策略來提高共享車輛的使用率。WANG等[9]在多中心開放式車輛路徑問題中引入了車輛共享機制,減少了總運營成本和車輛使用數(shù),但未涉及考慮多中心內(nèi)部和多中心間閉合式的車輛共享問題以及多中心合作的收益分配問題的研究。Friedrich等[10]探討了車輛共享系統(tǒng)在多式聯(lián)運公共交通網(wǎng)絡(luò)中的優(yōu)勢,提出了有效控制出行需求的建議。上述文獻在將車輛共享機制與多中心共同配送聯(lián)盟相結(jié)合方面的研究還有待深入。
本文研究了基于車輛共享的多中心共同配送網(wǎng)絡(luò)優(yōu)化問題,首先,建立了包含最小化物流成本和車輛數(shù)的雙目標優(yōu)化模型,并提出一種基于K-Means時空聚類的Clarke-Wright-帶精英策略的快速非支配排序遺傳算法(Clarke-Wright-fast elitist Non-dominated Sorting Genetic Algorithm-Ⅱ,CW-NSGA-Ⅱ)混合算法求解雙目標優(yōu)化模型,在混合算法過程中設(shè)計了聚類單元間染色體選擇、交叉和變異的精英循環(huán)迭代過程,提高了種群多樣性,增強了算法的全局和局部搜索能力;然后,應(yīng)用改進的Shapley值法和嚴格單調(diào)路徑原則研究了合作聯(lián)盟穩(wěn)定性和最優(yōu)聯(lián)盟序列選擇;最后,通過實例分析探討了非共享、配送中心內(nèi)部共享和全局共享3種模式下的車輛使用數(shù),共享線路數(shù)和物流成本的變化,進而為車輛共享模式下的物流配送問題提供新的研究思路。
在現(xiàn)代的城市物流配送網(wǎng)絡(luò)中,由于配送中心的建設(shè)時序和長期服務(wù)契約關(guān)系等現(xiàn)象的普遍存在,且物流企業(yè)間缺乏有效的資源共享和合作聯(lián)盟構(gòu)建,進而導(dǎo)致物流配送過程中存在延遲送達、長距離配送和交錯運輸?shù)痊F(xiàn)象。為了有效地提高配送資源的利用率和降低多中心物流配送網(wǎng)絡(luò)的運營成本,需要進行多中心間配送車輛的合理共享調(diào)度和多中心共同配送網(wǎng)絡(luò)優(yōu)化的合作聯(lián)盟構(gòu)建,進而提高多中心共同配送網(wǎng)絡(luò)的可靠性和穩(wěn)定性。
不同于多配送中心考慮multi-trip的車輛路徑規(guī)劃問題[11],基于車輛共享的多中心共同配送網(wǎng)絡(luò)優(yōu)化問題需要考慮客戶服務(wù)關(guān)系變化而在多個配送中心之間進行集中運輸調(diào)度,且車輛可以在配送中心內(nèi)部和配送中心之間實現(xiàn)資源共享,進而減少車輛使用數(shù)和降低物流運營成本。本文結(jié)合調(diào)研數(shù)據(jù)繪制了基于車輛共享的多中心共同配送網(wǎng)絡(luò)優(yōu)化前后對比圖(如圖1),由于未考慮客戶需求的異質(zhì)性,圖1中未考慮車輛在客戶處的服務(wù)時間。圖1a表示多中心共同配送網(wǎng)絡(luò)優(yōu)化前,配送中心服務(wù)客戶配送線路的各時間窗存在時間交錯和重疊等現(xiàn)象,且配送線路存在大量交錯運輸和長距離運輸?shù)那闆r,且存在違反時間窗的客戶點,而多中心共同配送網(wǎng)絡(luò)優(yōu)化后(如圖1b),客戶被分配到臨近的配送中心接受物流服務(wù),配送中心間進行合作產(chǎn)生配送需求變化的集中運輸。此外,配送中心服務(wù)客戶配送線路的各時間窗以及實現(xiàn)車輛共享的各配送線路不存在時間窗交錯和重疊的現(xiàn)象,進而實現(xiàn)了配送中心內(nèi)部以及配送中心之間有效的車輛共享,并消除了違反時間窗的客戶點。如:配送車輛SV2在配送中心DC2中[1,8]和[18,26]兩個時間域及配送中心DC5中[9,17]時間域內(nèi)的三條配送線路的車輛共享。由于優(yōu)化線路間存在部分線路通行時間交叉的現(xiàn)象,優(yōu)化后的多中心共同配送網(wǎng)絡(luò)存在非共享和共享車輛行駛路線共存的情況。
圖1中線路上的數(shù)值表示車輛的行程時間,且以配送中心時間窗開始時間為車輛的出發(fā)時間。假設(shè)單位時間的運輸成本為80元,單位時間的配送成本為50元,違反時間窗的單位時間懲罰成本為30元,運輸車輛的租賃成本為150元/輛·次,配送車輛的租賃成本為100元/輛·次,聯(lián)盟后的外部收益為450元。如表1所示為基于車輛共享的多中心共同配送優(yōu)化前后服務(wù)時間、車輛使用數(shù)和物流成本等指標的比較。結(jié)果表明,基于車輛共享的多中心共同配送網(wǎng)絡(luò)降低了配送服務(wù)時間,消除了違反時間窗的客戶點,并減少了配送車輛使用數(shù),進而降低了多中心共同配送網(wǎng)絡(luò)的物流運營成本。多中心共同配送網(wǎng)絡(luò)優(yōu)化前后總成本的節(jié)約值是多中心間進行收益分配優(yōu)化研究的基礎(chǔ),并為多中心共同配送合作序列選擇和聯(lián)盟構(gòu)建提供了研究切入點,進而有利于基于車輛共享的多中心共同配送合作聯(lián)盟形成。
表1 基于車輛共享的多中心共同配送優(yōu)化前后對比
基于車輛共享的多中心共同配送網(wǎng)絡(luò)優(yōu)化問題的變量定義如表2所示。
表2 變量定義
續(xù)表2
以多中心共同配送物流運營成本W(wǎng)最小化和配送車輛使用數(shù)V最小化為目標,建立基于車輛共享的多中心共同配送雙目標優(yōu)化模型:
minW=W1+W2+W3;
(1)
(2)
其中:W1為配送中心之間的運輸成本和車輛租賃成本,并考慮配送中心間聯(lián)盟的外部收益,
(3)
W2為配送中心服務(wù)客戶的配送成本和車輛租賃成本,
(4)
W3為配送車輛違反客戶時間窗的懲罰成本,
(5)
約束條件:
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(14)
(15)
(16)
(17)
(18)
φi={0,1},i∈I;
(19)
(20)
(21)
(22)
(23)
(24)
(25)
其中:式(6)表示客戶點在服務(wù)周期t內(nèi)僅接受一個配送中心服務(wù);式(7)表示每個客戶僅接受一條配送線路服務(wù);式(8)表示車輛v服務(wù)客戶后必須離開;式(9)和式(10)表示車輛的裝載量不超過車輛容量;式(11)表示客戶在服務(wù)周期t內(nèi)的需求總量不超過配送中心在服務(wù)周期t內(nèi)的最大配送量;式(12)表示配送中心i到h的運輸量等于服務(wù)關(guān)系改變的客戶需求量之和;式(13)表示消除線路上的子回路;式(14)表示服務(wù)周期t內(nèi)車輛v的使用次數(shù)等于其配送線路數(shù)之和;式(15)和式(16)表示車輛v服務(wù)客戶的到達時間;式(17)和式(18)表示車輛v在配送中心的時間窗內(nèi)進行服務(wù);式(19)~式(25)表示決策變量。
本文設(shè)計了基于K-means時空聚類的CW-NGSA-Ⅱ混合算法求解基于車輛共享的多中心共同配送聯(lián)盟優(yōu)化模型?;贙-means的時空聚類算法[12]首先結(jié)合客戶服務(wù)時間窗劃定客戶的多個服務(wù)時間周期;其次,結(jié)合客戶點的地理位置和時間窗進行多個服務(wù)周期的時空聚類操作;然后,應(yīng)用CW節(jié)約算法[13],在客戶點聚類單元內(nèi)生成初始配送線路;最后,應(yīng)用NSGA-Ⅱ算法[14]進行不同聚類單元內(nèi)和聚類單元間的線路調(diào)整和非支配排序優(yōu)化,進而生成多中心共同配送優(yōu)化線路。此外,K-means時空聚類算法和CW-NSGA-Ⅱ算法間的精英迭代交互過程設(shè)計可以有效避免配送中心間服務(wù)客戶點數(shù)目不均的問題?;旌纤惴鞒倘鐖D2所示。
在K-means聚類算法的基礎(chǔ)上,結(jié)合客戶服務(wù)時間窗和地理位置信息構(gòu)建三維時空坐標系,并計算客戶點i與j之間的距離[15],根據(jù)計算結(jié)果將每個客戶點歸屬到不同的聚類中心。如果(x,y)表示地理坐標,[TW1,TW2]表示時間窗,ξ表示距離與時間的轉(zhuǎn)換系數(shù),則客戶點間的距離計算公式如下:
Dij=|xi-xj|+|yi-yj|+ξ|TW1i-TW1j|+
ξ|TW2i-TW2j|,i,j∈J。
(26)
K-means時空聚類算法具體步驟如下:
步驟1導(dǎo)入配送中心位置坐標,客戶點位置坐標、時間窗,距離與時間換算系數(shù)。
步驟2根據(jù)導(dǎo)入的需要聚類的客戶時間窗數(shù)據(jù),結(jié)合時間窗的分布特性確定服務(wù)周期數(shù)和服務(wù)周期區(qū)間。
步驟3在每個服務(wù)周期內(nèi)將數(shù)據(jù)矩陣轉(zhuǎn)換為數(shù)據(jù)向量,計算配送中心及客戶點間的時空距離[9]。
步驟4設(shè)k等于配送中心數(shù)量,在每個服務(wù)周期內(nèi)隨機選擇k個初始聚類中心。
步驟5計算每個客戶點到聚類中心的時空距離,在相應(yīng)服務(wù)周期內(nèi)將客戶點指派到最臨近的聚類中心。
步驟6計算各服務(wù)周期內(nèi)k個聚類單元的中心作為新的聚類中心,并更新各服務(wù)周期內(nèi)的聚類中心。
步驟7重復(fù)步驟5~步驟7,直到聚類中心不再改變。
步驟8計算各聚類中心到各配送中心的距離,指派各聚類單元到最臨近的配送中心。
步驟9輸出聚類結(jié)果。
應(yīng)用基于K-means時空聚類的CW-NSGA-Ⅱ混合算法進行優(yōu)化計算和模型求解,相關(guān)變量定義為:popsize表示種群規(guī)模,genmax表示最大迭代次數(shù),ps,pc和pm分別表示選擇,交叉和變異概率,runmax表示精英迭代次數(shù),NN表示精英染色體個數(shù),Pt與Qt分別表示初始種群和子代種群,gen表示當前算法迭代次數(shù),run表示當前精英迭代次數(shù);混合算法的具體步驟如下:
步驟1設(shè)置參數(shù)包括種群規(guī)模popsize、最大迭代次數(shù)genmax、精英迭代次數(shù)runmax、選擇概率ps、交叉概率pc、變異概率pm。
步驟2應(yīng)用CW節(jié)約算法生成初始種群Pt,設(shè)置gen=1,run=1。
步驟3初始種群Pt由不同聚類單元內(nèi)的染色體共同組成,不同聚類單元內(nèi)的染色體組成了不同的初始優(yōu)化解方案。對聚類單元內(nèi)部和不同聚類單元間的染色體進行選擇,交叉和變異操作生成子代種群Qt。具體的選擇,交叉和變異過程如下述步驟(1)~步驟(3)所示。
(1)選擇性精英保留操作。結(jié)合帕累托優(yōu)化原理設(shè)計適應(yīng)度函數(shù)并計算適應(yīng)度函數(shù)值,根據(jù)聚類單元內(nèi)和聚類單元間染色體的適應(yīng)度大小應(yīng)用輪盤賭方法經(jīng)過多輪選擇確定子代種群,并采用精英保留策略[9],在每次選擇過程中保留一定數(shù)量的精英染色體進入子代。
(2)交叉操作。根據(jù)交叉概率隨機選擇聚類單元內(nèi)和聚類單元間的染色體進行交叉運算,并采用單點交叉法,兩點交叉法和部分映射交叉法生成子代染色體[16],并與父代染色體進行比較選擇子代染色體。
(3)變異操作。根據(jù)變異概率隨機選擇聚類單元內(nèi)和聚類單元間的染色體進行變異運算,并采用部分映射變異和互換操作算子生成子代染色體[15],并與父代染色體比較選擇子代染色體。
步驟4將Pt與Qt合并形成新的種群Rt,評價種群個體的目標函數(shù)值,進行非支配排序和擁擠距離計算,選擇包含NN個精英個體組成的新父代種群Pt+1。
步驟5令run=run+1,判斷是否達到運行次數(shù)runmax,若是則返回聚類算法步驟6進行循環(huán)操作,否則轉(zhuǎn)混合算法步驟6。
步驟6令gen=gen+1,重復(fù)混合算法步驟3進行循環(huán)操作,直到達到最大迭代次數(shù)genmax。
步驟7通過計算染色體對應(yīng)個體雙目標函數(shù)值間的擁擠度距離確定帕累托前沿,并通過帕累托前沿比較計算得到的雙目標解的帕累托優(yōu)化解排序,進而通過排序選取帕累托優(yōu)化解并輸出最優(yōu)解[15-16],結(jié)束算法。
將CW-NSGA-Ⅱ混合算法、多目標遺傳算法(Multi-Objective Genetic Algorithm, MOGA)[17]和多目標粒子群算法(Multi-Objective Particle Swarm Optimization, MOPSO)[18]進行比較,隨機生成20組實例數(shù)據(jù)如表3所示。根據(jù)已有相關(guān)文獻[9,15],算法參數(shù)設(shè)置為:種群規(guī)模popsize=100,最大迭代次數(shù)genmax=500,精英迭代次數(shù)runmax=20,精英染色體個數(shù)NN=30,選擇概率ps=0.7,交叉概率pc=0.8,變異概率pm=0.15,慣性權(quán)重w=0.5。每組實例數(shù)據(jù)計算10次,選取成本最優(yōu)值對應(yīng)的優(yōu)化結(jié)果,如表4所示。
表3 算例數(shù)據(jù)
表4 不同算法的計算結(jié)果比較
續(xù)表4
由表4可知,CW-NSGA-Ⅱ混合算法與MOGA和MOPSO所得結(jié)果有顯著不同。CW-NSGA-Ⅱ混合算法計算的物流成本平均值比MOGA減少3.03%,比MOPSO減少3.07%;求解時間平均值比MOGA減少了12.7 s,比MOPSO減少了14.9 s。結(jié)果表明,所提算法具有更強的全局和局部搜索能力,并能有效求解大規(guī)模問題。
為進一步驗證基于K-Means時空聚類的CW-NSGA-Ⅱ混合算法的有效性,選取10組帶時間窗的多倉庫車輛路徑問題(Multi-Depot Vehicle Routing Problem with Time Windows, MDVRPTW)標準算例數(shù)據(jù)[9]進行所提算法的進一步驗證,參數(shù)選取與上述隨機實例數(shù)據(jù)相同,且每組實例數(shù)據(jù)隨機計算10次,選取成本最優(yōu)值對應(yīng)的優(yōu)化結(jié)果,計算結(jié)果如表5所示。
表5 標準數(shù)據(jù)集計算結(jié)果比較
由表5可知,提出的基于K-Means時空聚類的CW-NSGA-Ⅱ混合算法求解得到的優(yōu)化值與已知最優(yōu)值的平均值差值比例為2.28%,且所提算法在pr01,pr02和pr07四組實例數(shù)據(jù)分別求得了與已知最優(yōu)值相同的結(jié)果,進而說明所提算法具有較好的穩(wěn)定性和可靠性。
以車輛共享的多中心共同配送網(wǎng)絡(luò)優(yōu)化方案為基礎(chǔ),通過與初始物流配送網(wǎng)絡(luò)進行比較計算,研究多中心共同配送的收益分配問題。Shapley值法[19]通常用于研究聯(lián)盟過程中的收益分配問題,結(jié)合表2中的相應(yīng)變量定義,應(yīng)用改進的Shapley值法計算聯(lián)盟成員的利潤分配值,如式(27)所示:
[(1-ψi)×v(S)-v(S-{i})],i∈N。
(27)
由于多中心共同配送前后的物流運營成本節(jié)約值可以看作多中心共同配送聯(lián)盟的收益值,而第三方物流服務(wù)提供商通過聯(lián)盟過程可獲得一定比例收益,聯(lián)盟S的收益可通過式(28)計算得到,而又由于S?N,因此,總聯(lián)盟N的收益也可通過式(28)變換計算得到:
(28)
基于收益分配結(jié)果,可以計算得到每個聯(lián)盟成員進入合作聯(lián)盟時的收益增加比例和已在聯(lián)盟成員的收益增加比例,進而應(yīng)用嚴格單調(diào)路徑選擇原則[20]進行合作聯(lián)盟序列選擇。當?shù)趏個成員加入聯(lián)盟ω時,聯(lián)盟成員i的收益增加百分比如式(29)所示:
(29)
合作聯(lián)盟是實現(xiàn)多中心共同配送的基礎(chǔ),而合作聯(lián)盟穩(wěn)定性是衡量多中心共同配送網(wǎng)絡(luò)魯棒性的重要依據(jù)。根據(jù)雪球理論[21],每種收益分配方法的結(jié)果與核心值間的距離被用作評判多中心合作聯(lián)盟穩(wěn)定性的標準,多中心合作聯(lián)盟的核心值計算如式(30)所示:
(30)
在每個服務(wù)周期內(nèi),應(yīng)用所提混合算法求解多中心共同配送的物流成本和車輛使用數(shù),得到各服務(wù)周期的共享車輛優(yōu)化路徑,如表6所示。
表6 基于車輛共享的多中心共同配送路線
續(xù)表6
5.3.1 多中心共同配送合作序列選擇和聯(lián)盟構(gòu)建
應(yīng)用式(28)計算聯(lián)盟收益增加百分比如圖4所示,應(yīng)用嚴格單調(diào)路徑原則得出最優(yōu)聯(lián)盟合作序列ω1={DC1,DC4,DC5,DC3,DC2}如圖5所示。首先,DC1與DC4合作,收益增加百分比分別為36.6%和39.9%;然后,DC5和DC3依次進入聯(lián)盟,聯(lián)盟成員的收益增加百分比分別為41.3%,41.3%,40.6%和40.2%;最后,DC2進入聯(lián)盟,各成員收益增加百分比分別為47.8%,48.5%,44.3%,46.4%和44.2%。
5.3.2 多中心共同配送合作聯(lián)盟穩(wěn)定性
通過式(30)計算核心值為(1 208,1 032,1 236,1 082,1 053),比較不同收益分配方案與核心值距離(表7),改進Shapley值法均優(yōu)于CGA,MCRS和EPM三種方法所確定的收益分配方案,具有更強的合作聯(lián)盟穩(wěn)定性。
表7 核心距離計算表
不同車輛共享模式包括非共享、內(nèi)部共享和全局共享3種模式,3種模式下的車輛使用數(shù)、共享線路數(shù)和物流運營成本等對比結(jié)果如表8所示。
表8 不同共享模式下多中心共同配送優(yōu)化方案比較
由表8可知,全局共享模式求解的優(yōu)化方案具有最少車輛使用數(shù),最多共享線路數(shù)和最低物流運營總成本(如圖6)。此外,在非共享,內(nèi)部共享和全局共享3種模式下的聯(lián)合優(yōu)化物流運營總成本均高于多中心共同配送的物流運營總成本。為進一步分析和比較不同模式間的聯(lián)盟特性,分別計算得到3種模式下的最優(yōu)合作聯(lián)盟序列(表9)和聯(lián)盟成員收益增加百分比(表10),可知全局共享模式下各聯(lián)盟成員的收益增加百分比均優(yōu)于另外兩種模式,且各聯(lián)盟成員均可獲得較高利潤,有利于提高合作聯(lián)盟的穩(wěn)定性,進而有助于促進合作聯(lián)盟形成。
表9 三種模式下最優(yōu)合作聯(lián)盟序列 %
表10 三種模式下最優(yōu)合作聯(lián)盟成員收益增加百分比 %
本文研究了基于車輛共享的多中心共同配送網(wǎng)絡(luò)聯(lián)盟優(yōu)化問題,考慮到現(xiàn)實物流配送網(wǎng)絡(luò)中車輛共享頻率低和合作聯(lián)盟機制欠缺的問題,將基于車輛共享的合作聯(lián)盟序列構(gòu)建方法融入多中心共同配送網(wǎng)絡(luò)優(yōu)化問題中進行研究。首先,建立了一個考慮物流成本和車輛使用數(shù)的雙目標優(yōu)化模型,提出了基于K-means時空聚類的CW-NSGA-Ⅱ混合算法求解模型,在混合算法過程中設(shè)計了聚類算法和智能算法間的選擇性賦予機制,提高了算法的全局搜索和局部尋優(yōu)能力。其次,應(yīng)用改進的Shapley值法研究了多中心共同配送聯(lián)盟的收益分配,并應(yīng)用嚴格單調(diào)路徑原則選擇了最優(yōu)合作聯(lián)盟序列和研究了聯(lián)盟穩(wěn)定性。最后,比較分析了非共享、配送中心內(nèi)部共享和全局共享3種模式下的多中心合作聯(lián)盟序列選擇和收益增加百分比。研究結(jié)果表明全局共享模式能有效降低物流成本和提高配送車輛使用效率,進而增加多中心共同配送網(wǎng)絡(luò)的聯(lián)盟穩(wěn)定性。本文所提方法有利于多中心共同配送網(wǎng)絡(luò)聯(lián)盟構(gòu)建,并能更好的應(yīng)用到基于資源共享的多級物流配送網(wǎng)絡(luò)優(yōu)化和聯(lián)盟構(gòu)建研究中。