基于多中心车辆路径问题的收益分配优化研究

王 勇，任音吉，刘 永，许茂增

(1.重庆交通大学经济与管理学院，重庆400074；2.电子科技大学经济与管理学院，成都611731)

0 引 言

多中心车辆路径优化问题是物流网络配送的重要组成部分，而引进物流服务提供商促成配送中心间形成合作联盟并研究其收益分配策略是多中心车辆路径优化问题的关键.国内外学者的相关研究主要分为多中心车辆路径优化和收益分配机制两方面.在多中心车辆路径优化问题方面，Tu等[1]应用启发式算法求解了大规模的多中心车辆路径问题，Zhou等[2]提出了混合多种群遗传算法求解物流配送车辆路径规划问题；在收益分配机制方面，Wang等[3]应用改进的Shapley值模型研究了物流企业间的合作收益分配策略；在物流服务提供商参与下的物流企业联盟方面，Cruijssen等[4]研究了物流企业合作过程中物流服务提供商对于提高企业盈利能力方面所起的作用.上述文献以物流服务提供商作为协调者进行联盟合作序列及多个联盟的形成和存在条件方面的研究涉及较少.

本文针对中心车辆路径优化问题，首先，研究建立了多中心共同配送车辆路径优化模型.其次，运用客户点聚类与遗传—粒子群混合算法结合的方法求解模型，在混合算法中将部分优化粒子与非优化染色体进行周期性替换和优化迭代计算，提高了算法的全局搜索能力.然后，以共同配送优化前后成本差值作为联盟收益，运用不同收益分配模型研究配送中心收益分配策略.最后，运用严格单调递增序列研究配送中心联盟稳定性合作序列，并以物流服务提供商获得收益最大化为目标，研究了两个联盟的形式并进行了实例验证.

1 模型描述

1.1 变量定义

多中心车辆路径问题的变量定义如表1所示.

1.2 模型建立

本文以成本最小化为优化目标，配送中心与客户点之间的运输成本C1为

配送中心之间的相互运输成本C2为

表1 变量定义Table 1 The variable definitions

小车的使用及维护成本C3为

总成本C为

因此，多中心车辆路径优化模型及约束条件为

式(6)保证每个客户点由1辆车服务，式(7)保证在1条路线上的客户需求量不超过车辆装载量，式(8)保证配送中心之间运输量等于合作后服务的客户改变的需求量，式(9)保证归属于配送中心j的客户需求量不超过其最大存储量，式(10)保证配送中心之间的运输量不超过车辆最大装载量，式(11)保证车辆不重复进行配送，式(12)保证车辆由1个配送中心出发开始进行配送，式(13)保证归属于配送中心j的客户i一定被该配送中心服务，式(14)保证i,j之间的距离不超过最大距离.

基于上述多中心共同配送优化模型，设定合作方案S的收益为

配送中心j所需车辆数为

合作联盟形成的收益增加百分比为

2 多中心车辆路径优化算法

2.1 客户点聚类

本文采用的聚类算法过程如下：

Step 1计算客户点i与配送中心j，h之间的运输距离Lij.如果满足Lij≤Lih，则客户点i归属于配送中心j；否则，客户点i归属于配送中心h.最终将所有客户点按照配送中心进行分类.

Step 2由式(18)计算配送中心j所需的车辆数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重复Step4，并检查线路中客户点的装载量，直到所有归属于配送中心j的客户点被分配到该中心所有线路中为止.

根据上述客户点聚类步骤，得到初始的配送中心车辆行驶线路.

2.2 遗传—粒子群混合算法(GA-PSO)

2.2.1 种群编码

本文采用不重复的实数进行编码：1,2,3,…,i，编码中不同数值表示不同的客户点.遗传—粒子群算法变量定义为：mT1中m表示正整数，T1为常量；Nnum表示遗传算法初始染色体数，Nn′um表示进行粒子群算法的粒子个数；gn表示混合算法当前迭代次数，gnmax表示混合算法最大迭代次数；N1表示选择替换遗传算法个体的粒子群算法个体数.

2.2.2 混合算法步骤

针对多中心车辆路径优化模型，采用遗传—粒子群混合算法求解，算法流程如图1所示.

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

2.2.3 算法检验

将混合算法与遗传算法(GA)[2]、粒子群(PSO)[3]和自适应粒子群算法(APSO)[1]进行比较，随机生成4个配送中心与71个客户点，其中配送中心坐标分别为：(6,15.5)，(18,17.5)，(33,13)，(16,7).设定相同的迭代次数T=500，4种算法计算10次，结果如表2所示.

表2 4种算法计算结果Table 2 The calculation results of four algorithms

由表2可知，本文所提算法10次计算的平均值比GA减少14.1%，比PSO减少19.23%，比APSO减少5.4%，且本文所提混合算法多次达到和接近优化解，结果表明该混合算法具有更优的计算能力.

3 收益分配模型

3.1 MCRS法

MCRS是一种合作博弈模型[5]，该模型要求联盟参与者首先获得一部分收益(最小收益)，然后根据各参与者所能获得的最大与最小收益的差值分配剩余收益.其模型为

式中：πjmax,πjmin可由式(21)～式(23)线性规划求得.

3.2 物流服务提供商(LSP)

在多中心联盟形成的过程中，物流服务提供商可以通过谈判促使合作联盟形成.在联盟形成并获得收益后，收取比例φ的服务报酬.假设物流服务提供商获得的收益为

3.3 联盟稳定性

根据式(22)和式(23)确定该收益分配模型的核心区域，并得到核心区域边界的函数方程，将边界按比例压缩计算核心区域中心.根据“雪球”理论[5]，采用欧式距离计算各收益分配方案与中心的半径，若该分配策略的半径越大，则表示稳定性越差；反之，则表示稳定性越好.

4 算例分析

4.1 相关数据

某城市配送网络是由5个配送中心和80个客户点组成，如图2所示，客户点需求量由表3所示.多中心共同配送以前，客户点形成的初始线路如表4所示.设置参数：

图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 车辆路径优化方案

通过上述混合算法计算的总运输成本是58 413.06，优化后的配送路线如表5所示.

表5 配送优化车辆线路Table 5 Optimal distribution vehicle routes

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

计算所有联盟形式的总成本和收益，其中，物流服务提供商抽取比例φ=0.15的联盟收益，由式(24)可计算5个配送中心形成联盟后，物流服务提供商获得收益为6 372.03，通过式(17)得到各参与者联盟的收益，如表6所示.

通过MCRS模型计算最终联盟的收益分配策略为(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分配模型得到的收益分配策略具有更好的联盟稳定性.

4.4 联盟成员合作序列

物流服务提供商在促进多个配送中心形成联盟的过程中，需要考虑配送中心进入联盟的合作序列，通过式(20)计算得到配送中心联盟收益分配方案如表8所示.

表6 参与者联盟收益分配Table 6 Profit allocation of participant alliances

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

本文采用严格单调序列方法(SMP)[3]，在各配送中心形成一个联盟的过程中，通过式(19)计算得到各配送中心的收益增加百分比，所有可能的联盟合作序列中没有符合SMP的联盟形式.因此，考虑联盟拆分策略，将多个配送中心形成两个联盟，但要求配送中心j只属于其中一个联盟，符合SMP法则的合作序列分别是：

(1)DC1和DC3形成联盟，DC2，DC4和DC5形成联盟，总收益35 822.75，物流服务商获得收益6 321.66.

(2)DC2和DC4形成联盟，DC1，DC3和DC5形成联盟，总收益35 486.3，物流服务商获得收益6 262.29.

两种合作序列的成员最终收益增加百分比如图3所示.在物流服务商追求最大收益的情况下，{DC3,DC1}和{DC2,DC5,DC4}的联盟形式将最终被选取.

表8 联盟收益分配Table 8 Profit allocation of alliance

图3 联盟成员最终收益增加百分比Fig.3 Final revenue increase percentage of all alliance members

5 结论

本文针对多中心共同配送网络，研究了多中心共同配送车辆路径优化问题，并以多配送中心总运输成本最小为目标建立了数学模型.提出了首先通过客户点聚类方法生成初始线路，然后应用GA-PSO混合算法优化线路，在混合算法优化过程中设计了遗传算法和粒子群算法间的周期性替换和迭代操作，提高了算法的寻优能力；其次，研究了多配送中心合作联盟的收益分配问题；最后，研究了多配送中心的联盟合作序列问题，探讨了满足严格单调递增条件下的联盟形成过程和联盟拆分策略，进而为后续研究提供相应借鉴.

[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.