基于多中心車輛路徑問題的收益分配優(yōu)化研究

王 勇，任音吉，劉 永，許茂增

(1.重慶交通大學(xué)經(jīng)濟與管理學(xué)院，重慶400074；2.電子科技大學(xué)經(jīng)濟與管理學(xué)院，成都611731)

0 引 言

多中心車輛路徑優(yōu)化問題是物流網(wǎng)絡(luò)配送的重要組成部分，而引進物流服務(wù)提供商促成配送中心間形成合作聯(lián)盟并研究其收益分配策略是多中心車輛路徑優(yōu)化問題的關(guān)鍵.國內(nèi)外學(xué)者的相關(guān)研究主要分為多中心車輛路徑優(yōu)化和收益分配機制兩方面.在多中心車輛路徑優(yōu)化問題方面，Tu等[1]應(yīng)用啟發(fā)式算法求解了大規(guī)模的多中心車輛路徑問題，Zhou等[2]提出了混合多種群遺傳算法求解物流配送車輛路徑規(guī)劃問題；在收益分配機制方面，Wang等[3]應(yīng)用改進的Shapley值模型研究了物流企業(yè)間的合作收益分配策略；在物流服務(wù)提供商參與下的物流企業(yè)聯(lián)盟方面，Cruijssen等[4]研究了物流企業(yè)合作過程中物流服務(wù)提供商對于提高企業(yè)盈利能力方面所起的作用.上述文獻以物流服務(wù)提供商作為協(xié)調(diào)者進行聯(lián)盟合作序列及多個聯(lián)盟的形成和存在條件方面的研究涉及較少.

本文針對中心車輛路徑優(yōu)化問題，首先，研究建立了多中心共同配送車輛路徑優(yōu)化模型.其次，運用客戶點聚類與遺傳—粒子群混合算法結(jié)合的方法求解模型，在混合算法中將部分優(yōu)化粒子與非優(yōu)化染色體進行周期性替換和優(yōu)化迭代計算，提高了算法的全局搜索能力.然后，以共同配送優(yōu)化前后成本差值作為聯(lián)盟收益，運用不同收益分配模型研究配送中心收益分配策略.最后，運用嚴格單調(diào)遞增序列研究配送中心聯(lián)盟穩(wěn)定性合作序列，并以物流服務(wù)提供商獲得收益最大化為目標，研究了兩個聯(lián)盟的形式并進行了實例驗證.

1 模型描述

1.1 變量定義

多中心車輛路徑問題的變量定義如表1所示.

1.2 模型建立

本文以成本最小化為優(yōu)化目標，配送中心與客戶點之間的運輸成本C1為

配送中心之間的相互運輸成本C2為

表1 變量定義Table 1 The variable definitions

小車的使用及維護成本C3為

總成本C為

因此，多中心車輛路徑優(yōu)化模型及約束條件為

式(6)保證每個客戶點由1輛車服務(wù)，式(7)保證在1條路線上的客戶需求量不超過車輛裝載量，式(8)保證配送中心之間運輸量等于合作后服務(wù)的客戶改變的需求量，式(9)保證歸屬于配送中心j的客戶需求量不超過其最大存儲量，式(10)保證配送中心之間的運輸量不超過車輛最大裝載量，式(11)保證車輛不重復(fù)進行配送，式(12)保證車輛由1個配送中心出發(fā)開始進行配送，式(13)保證歸屬于配送中心j的客戶i一定被該配送中心服務(wù)，式(14)保證i,j之間的距離不超過最大距離.

基于上述多中心共同配送優(yōu)化模型，設(shè)定合作方案S的收益為

配送中心j所需車輛數(shù)為

合作聯(lián)盟形成的收益增加百分比為

2 多中心車輛路徑優(yōu)化算法

2.1 客戶點聚類

本文采用的聚類算法過程如下：

Step 1計算客戶點i與配送中心j，h之間的運輸距離Lij.如果滿足Lij≤Lih，則客戶點i歸屬于配送中心j；否則，客戶點i歸屬于配送中心h.最終將所有客戶點按照配送中心進行分類.

Step 2由式(18)計算配送中心j所需的車輛數(shù)Nj，將歸屬于配送中心j的客戶點分成Nj條線路.

Step 3在配送中心j的線路ψNj中，配送中心j為線路的起點和終點，將距離配送中心j最近的客戶點i確定為線路ψNj的第2個點，則記ψNj={ j ,i,j}.

Step 4將與當前線路ψNj中所有點總配送距離和最短的客戶點e確定為線路ψNj的第3個點，即Lje+Lie最小，則記ψNj={ j ,i,e,j}.

Step 5重復(fù)Step4，并檢查線路中客戶點的裝載量，直到所有歸屬于配送中心j的客戶點被分配到該中心所有線路中為止.

根據(jù)上述客戶點聚類步驟，得到初始的配送中心車輛行駛線路.

2.2 遺傳—粒子群混合算法(GA-PSO)

2.2.1 種群編碼

本文采用不重復(fù)的實數(shù)進行編碼：1,2,3,…,i，編碼中不同數(shù)值表示不同的客戶點.遺傳—粒子群算法變量定義為：mT1中m表示正整數(shù)，T1為常量；Nnum表示遺傳算法初始染色體數(shù)，Nn′um表示進行粒子群算法的粒子個數(shù)；gn表示混合算法當前迭代次數(shù)，gnmax表示混合算法最大迭代次數(shù)；N1表示選擇替換遺傳算法個體的粒子群算法個體數(shù).

2.2.2 混合算法步驟

針對多中心車輛路徑優(yōu)化模型，采用遺傳—粒子群混合算法求解，算法流程如圖1所示.

圖1 GA-PSO算法流程圖Fig.1 The flow chart of GA-PSO

2.2.3 算法檢驗

將混合算法與遺傳算法(GA)[2]、粒子群(PSO)[3]和自適應(yīng)粒子群算法(APSO)[1]進行比較，隨機生成4個配送中心與71個客戶點，其中配送中心坐標分別為：(6,15.5)，(18,17.5)，(33,13)，(16,7).設(shè)定相同的迭代次數(shù)T=500，4種算法計算10次，結(jié)果如表2所示.

表2 4種算法計算結(jié)果Table 2 The calculation results of four algorithms

由表2可知，本文所提算法10次計算的平均值比GA減少14.1%，比PSO減少19.23%，比APSO減少5.4%，且本文所提混合算法多次達到和接近優(yōu)化解，結(jié)果表明該混合算法具有更優(yōu)的計算能力.

3 收益分配模型

3.1 MCRS法

MCRS是一種合作博弈模型[5]，該模型要求聯(lián)盟參與者首先獲得一部分收益(最小收益)，然后根據(jù)各參與者所能獲得的最大與最小收益的差值分配剩余收益.其模型為

式中：πjmax,πjmin可由式(21)～式(23)線性規(guī)劃求得.

3.2 物流服務(wù)提供商(LSP)

在多中心聯(lián)盟形成的過程中，物流服務(wù)提供商可以通過談判促使合作聯(lián)盟形成.在聯(lián)盟形成并獲得收益后，收取比例φ的服務(wù)報酬.假設(shè)物流服務(wù)提供商獲得的收益為

3.3 聯(lián)盟穩(wěn)定性

根據(jù)式(22)和式(23)確定該收益分配模型的核心區(qū)域，并得到核心區(qū)域邊界的函數(shù)方程，將邊界按比例壓縮計算核心區(qū)域中心.根據(jù)“雪球”理論[5]，采用歐式距離計算各收益分配方案與中心的半徑，若該分配策略的半徑越大，則表示穩(wěn)定性越差；反之，則表示穩(wěn)定性越好.

4 算例分析

4.1 相關(guān)數(shù)據(jù)

某城市配送網(wǎng)絡(luò)是由5個配送中心和80個客戶點組成，如圖2所示，客戶點需求量由表3所示.多中心共同配送以前，客戶點形成的初始線路如表4所示.設(shè)置參數(shù)：

圖2 配送中心與客戶點分布圖Fig.2 Spatial distribution of DCs and customers

表3 客戶點需求量Table 3 Demand of customers

表4 客戶點初始車輛線路Table 4 Initial vehicle routes for five DCs

4.2 車輛路徑優(yōu)化方案

通過上述混合算法計算的總運輸成本是58 413.06，優(yōu)化后的配送路線如表5所示.

表5 配送優(yōu)化車輛線路Table 5 Optimal distribution vehicle routes

4.3 多配送中心收益分配方案

計算所有聯(lián)盟形式的總成本和收益，其中，物流服務(wù)提供商抽取比例φ=0.15的聯(lián)盟收益，由式(24)可計算5個配送中心形成聯(lián)盟后，物流服務(wù)提供商獲得收益為6 372.03，通過式(17)得到各參與者聯(lián)盟的收益，如表6所示.

通過MCRS模型計算最終聯(lián)盟的收益分配策略為(4 349.78,8 973.58,7 699.09,10 798.37,4 287.35)，將MCRS法與Shapley法、比例最小核心法、弱最小核心法、最小核心法進行計算比較[5]，其中，中心位置為(4 367.39,8 985.11,7 718.25,11 375.99,3 661.43)，如表7所示.因此，采用MCRS分配模型得到的收益分配策略具有更好的聯(lián)盟穩(wěn)定性.

4.4 聯(lián)盟成員合作序列

物流服務(wù)提供商在促進多個配送中心形成聯(lián)盟的過程中，需要考慮配送中心進入聯(lián)盟的合作序列，通過式(20)計算得到配送中心聯(lián)盟收益分配方案如表8所示.

表6 參與者聯(lián)盟收益分配Table 6 Profit allocation of participant alliances

表7 收益分配策略比較Table 7 Comparison of profit allocation strategies

本文采用嚴格單調(diào)序列方法(SMP)[3]，在各配送中心形成一個聯(lián)盟的過程中，通過式(19)計算得到各配送中心的收益增加百分比，所有可能的聯(lián)盟合作序列中沒有符合SMP的聯(lián)盟形式.因此，考慮聯(lián)盟拆分策略，將多個配送中心形成兩個聯(lián)盟，但要求配送中心j只屬于其中一個聯(lián)盟，符合SMP法則的合作序列分別是：

(1)DC1和DC3形成聯(lián)盟，DC2，DC4和DC5形成聯(lián)盟，總收益35 822.75，物流服務(wù)商獲得收益6 321.66.

(2)DC2和DC4形成聯(lián)盟，DC1，DC3和DC5形成聯(lián)盟，總收益35 486.3，物流服務(wù)商獲得收益6 262.29.

兩種合作序列的成員最終收益增加百分比如圖3所示.在物流服務(wù)商追求最大收益的情況下，{DC3,DC1}和{DC2,DC5,DC4}的聯(lián)盟形式將最終被選取.

表8 聯(lián)盟收益分配Table 8 Profit allocation of alliance

圖3 聯(lián)盟成員最終收益增加百分比Fig.3 Final revenue increase percentage of all alliance members

5 結(jié)論

本文針對多中心共同配送網(wǎng)絡(luò)，研究了多中心共同配送車輛路徑優(yōu)化問題，并以多配送中心總運輸成本最小為目標建立了數(shù)學(xué)模型.提出了首先通過客戶點聚類方法生成初始線路，然后應(yīng)用GA-PSO混合算法優(yōu)化線路，在混合算法優(yōu)化過程中設(shè)計了遺傳算法和粒子群算法間的周期性替換和迭代操作，提高了算法的尋優(yōu)能力；其次，研究了多配送中心合作聯(lián)盟的收益分配問題；最后，研究了多配送中心的聯(lián)盟合作序列問題，探討了滿足嚴格單調(diào)遞增條件下的聯(lián)盟形成過程和聯(lián)盟拆分策略，進而為后續(xù)研究提供相應(yīng)借鑒.

[1]TU W,FANG Z,LI Q,et al.A bi-level Voronoi diagram-based metaheuristic for a large-scale multidepot vehicle routing problem[J]. Transportation Research Part E：Logistics&Transportation Review,2014,61(1)：84-97.

[2]ZHOU L,BALDACCI R,VIGO D,et al.A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution[J].European Journal of Operational Research,2018(265)：765-778.

[3]WANG Y,MA X,LIU M,et al.Cooperation and profit allocation in two-echelon logistics joint distribution network optimization[J].Applied Soft Computing,2017(56)：143-157.

[4]CRUIJSSEN F,COOLS M,DULLAERT W.Horizontal cooperation in logistics： Opportunities and impediments[J]. Transportation Research Part E：Logistics&Transportation Review,2007,43(2)：129-142.

[5]LOZANO S,MORENO P,ADENSO-DíAZ B,et al.Cooperative game theory approach to allocating benefits ofhorizontalcooperation[J].European Journalof Operational Research,2013,229(2)：444-452.