多中心冷链共同配送路径优化及利润分配研究

李丽滢，罗继康，牛莉霞

（辽宁工程技术大学 工商管理学院，葫芦岛 125000）

0 引言

随着生鲜电商的快速发展，人们对于高质量生鲜商品的需求得以满足。生鲜商品由于具有保存不易、易腐等特性，配送难度高于普通货物。若配送路径规划不合理，则会导致配送时间长，使生鲜商品的损耗和配送成本增加[1]。国家下发的《“十四五”冷链物流发展规划》中提出要优化冷链物流网络，健全冷链物流服务体系，聚焦“肉类、水果、蔬菜等生鲜食品以及疫苗等医药产品[2]。科学合理的冷链物流配送体系是冷链物流企业降本增效的必要条件，多中心冷链共同配送是提高冷链配送服务质量的重要手段。研究新鲜度约束下的多中心冷链共同配送及利润分配有助于实现冷链物流企业之间资源的合理配置，提高交付商品的新鲜度，降低企业运营成本，促进冷链物流产业的可持续发展。近年来，众多学者对于多中心冷链共同配送路径优化及利润分配问题进行了一系列的研究。

针对冷链物流配送的车辆路径问题研究中，LI等[3]以生鲜商品配送成本最小化为目标，设计自适应模拟退火变异遗传算法求解，为生鲜物流企业提供了配送方案。赵志学、刘长石、王宁等[4-6]针对考虑生鲜商品新鲜度的冷链物流车辆路径问题，分别利用自适应改进的蚁群算法、改进的蚁群算法和单亲遗传算法进行求解，研究表明冷链物流企业配送时考虑生鲜商品的新鲜度可以有效降低企业成本。赵邦磊[7]等设计改进的ACO算法，解决了多目标优化的冷链配送模型。李军涛等[8]设计自适应灾变遗传算法，有效的解决了模糊时间窗下的冷链物流配送路径优化问题。舒辉、张佳佳、王思洪等[9-11]分别设计自适应遗传算法、粒子群算法、GAMS与遗传算法相结合解决冷链物流配送路径优化问题。王勇等[12]综合考虑客户时间窗和生鲜商品温度控制，建立生鲜商品配送成本最少和生鲜商品价值损失最小的双目标模型，并设计GA-TS混合算法进行求解。DEVAPRIYA等[13]利用进化的启发式算法研究易腐商品运输优化问题，结果表明生鲜商品的配送车辆比普通商品的配送车辆在物流成本、客户满意度、交付生鲜商品新鲜度等方面有更高的要求。由上述文献可知，生鲜商品的配送研究主要集中于单中心配送，并且考虑在新鲜度约束下的生鲜商品配送研究较少。因此考虑新鲜度约束下多中心生鲜配送研究还有待进一步深度拓展。

在多中心共同配送以及合作利润分配的研究中，叶勇等[14]建立了车辆总行驶路径最小的目标模型，设计狼群算法进行求解。葛嘉怡等[15]构建改进模糊Shapley值的收益分配模型对医药冷链收益进行分配。辜勇、FITRIANA等[16,17]针对多中心协同配送下的车辆路径问题，将大规模多配送中心路径问题转换为多个单配送中心路径问题，设计改进蚁群算法求解该模型，证明了该模型的有效性。葛显龙等[18]研究了前置仓独立配送与协作配送的生鲜配送问题，设计改进的遗传算法进行求解。范厚明等[19]在已有的研究基础上，在多中心共同配送问题中考虑客户集货的随机需求，设计预优化和重优化两阶段对路径进行规划，深化了多中心共同配送相关的理论研究。饶卫振等[20]设计贪婪算法和大邻域搜索算法构成的两阶段算法，从理论视角下计算车辆协作与不协作状态下的配送距离和能耗量。BEN ALAIA等[21]研究了封闭式多车辆多中心配集货车辆路径优化问题，利用遗传算法和粒子群算法对该问题进行求解，但是未考虑到利润分配问题。FERNÁNDEZ等[22]研究了共享客户资源的协作车辆问题，通过对基础实例集进行计算，与非共享客户资源模式进行比较，得出独立运营商合作具有潜在效益的结论。王勇等[23]设计混合启发式算法求解网络运营成本最小和车辆使用数最小的双目标模型，运用最小费用剩余节约方法（MCRS）求解多中心共同配送与收集网络联盟的利润分配问题，为可持续的城市物流网络规划和共享物流合作联盟的构建提供决策支持。由上述文献可知，多配送中心共同配送问题方面的研究已取得了一系列的进展，进而对多中心冷链物流共同配送以及共同配送所带来的利润进行分配等方面提供了研究切入。

综上所知，现有的文献主要集中在将冷链物流、多中心共同配送、联盟利润分配分开进行研究，将冷链物流、多中心共同配送并对联盟利润进行分配结合考虑的研究涉及较少。其次，学者大多研究的是企业共享客户资源和所有车辆。考虑到现实中存在企业之间进行共同配送时，共享客户资源但只共享转运车辆的形式。鉴于此，本文针对生鲜商品的特性，在满足交付商品新鲜度约束的前提下，建立转运车辆和配送车辆的固定成本、运输成本、制冷成本、货损成本以及时间窗惩罚成本之和最小为目标的车辆路径优化模型，设计一种基于K-means聚类的改进混合蚁群算法进行求解。最后通过Shapley值法对冷链物流企业组建联盟所获得的共同利润进行合理分配，通过对比联盟组建前后企业的成本，证明该模型的可行性。本文的研究对丰富和完善当前的冷链配送网络具有重要的现实意义。

1 模型构建

1.1 问题描述

目前大部分冷链物流企业拥有各自的物流中心和若干客户，由于物流中心建设时序、客户契约关系等因素，物流中心之间很少有合作关系，各自独立完成配送服务。如图1中a所示，这种配送方式会出现过远运输、交叉运输和生鲜商品损坏、违反时间窗等问题。如果企业之间建立多中心冷链共同配送联盟，共享客户资源，共享转运车辆，就可以消除以上弊端。如图1中b所示，企业冷链物流中心1、2、3分别将各自两个配送距离较远的客户交由其他两个企业进行配送，使用冷藏卡车在物流中心1、2、3之间转运因客户服务关系转变的生鲜商品，然后各个物流中心使用冷藏货车根据客户的地理位置、时间窗和生鲜商品的新鲜度要求对客户进行服务，以配送成本最小化为目标优化配送路线，实现物流网络中资源的有效利用。最后，不合理的利润分配机制会导致联盟成员的利润分配不均，合作关系不会维持很久。因此，基于优化后的网络，利用合作博弈论中的Shapely值法，将节约成本作为联盟的利润分配值，通过衡量联盟内成员对联盟节约值带来的边际贡献值进行利润分配，保证联盟合作关系的稳定。

图1 多中心冷链共同配送联盟建立前后对比

1.2 符号说明

1）集合

节点集合Z={1,2,...,n,n+1,...,n+m}；

配送客户集合M={1,2,...,m}；

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

L：在物流中心之间转运资源的冷藏卡车集合，l∈L；

K：物流中心进行配送的冷藏货车集合，k∈K

2）参数

f1：冷藏卡车l的固定成本

f2：冷藏货车k的固定成本

c1：冷藏卡车l的单位运输成本

c2：冷藏货车k的单位运输成本

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

dij：客户i到客户j的距离

Tijl：冷藏卡车从物流中心i到物流中心j的时间

Tijk：冷藏货车从客户点i到客户点j行驶时间

b1、b2：冷藏卡车开门时和运输时的单位时间制冷成本

λ1、λ2：冷藏货车开门时和运输时的单位时间制冷成本

[αi,bi]：客户i的时间窗

δ：生鲜商品单位产品价值

α：冷藏货车早于αi到达客户点i的惩罚系数

β：冷藏货车晚于bi到达客户点i的惩罚系数

Qij：物流中心i调配到物流中心j的送货量

Pij：物流中心i调配到物流中心j的取货量

Qt：时间点t时冷藏卡车在物流中心之间调配的实时装载量

qi：配送客户i的需求量

Gl：冷藏卡车l的最大装载量

Gk：冷藏货车k的最大装载量

3）决策变量

Xijk：冷藏货车从客户点i出发到客户点j时为1，否则为0，其中i,j∈M；

Yk：冷藏货车k被使用时为1，否则为0；

Wijl：冷藏卡车l是从物流中心i出发到物流中心j为1，否则为0，其中i,j∈N

Yl：冷藏卡车l被使用时为1，否则为0。

Erij：客户r的服务关系从物流中心i转移到物流中心j时为1，否则为0，r∈M，i,j∈N

1.3 模型构建

1.3.1 新鲜度约束

生鲜商品具有易损性，配送时间和配送距离会影响生鲜商品的新鲜度，在运输过程中会产生货损成本，生鲜商品的新鲜度衰减函数表达如式(1)：

其中，θ(t)为生鲜商品t时刻的新鲜度，θ0为生鲜商品的初始新鲜度，为新鲜度衰减系数，要求θ(ti)≥Gb，ti为到达客户点i的时间，Gb为商品交付时要满足客户的最低新鲜度。

1.3.2 成本模型

本文所研究的新鲜度限制约束下多中心冷链共同配送模型问题以车辆固定成本、运输成本、制冷成本、货损成本和时间窗惩罚成本之和最小化建立模型：

1）C1为冷藏卡车和冷藏货车的固定成本

固定成本主要包括驾驶员工资、车辆的固定费用等，与车辆使用数成正比。

2）C2冷藏卡车和冷藏货车的运输成本

运输成本主要包括冷藏卡车和冷藏货车的保养维修、油费等。

3）C3为冷藏卡车和冷藏货车的制冷成本

制冷成本主要包括冷藏卡车和冷藏货车运输时为了保持车厢温度恒定所产生的费用以及防止卸货时车门敞开导致车厢温度上升所产生的预冷费用。

4）C4为生鲜商品的货损成本

由于装卸时间相较于运输时间较短，因此货损成本只包括物流中心之间运输生鲜商品和物流中心配送商品过程中产生的货损成本。

5）C5为时间窗惩罚成本

惩罚成本指生鲜商品无法在顾客规定的时间窗内送达产生的成本。

1.4 约束条件

式(8)表示所有的客户只被冷藏货车服务一次；式(9)表示车辆k将货物送到客户点i时产品新鲜度必须大于等于产品保质的最低标准；式(10)表示车辆k从物流中心O出发，完成客户点服务后返回物流中心O；式(11)表示冷藏卡车l只在物流中心之间调配货物；式(12)表示冷藏货车k只用来服务客户；式(13)表示冷藏卡车l调配货物时的载重量不超过其最大载重量；式(14)表示冷藏货车k服务客户i时的载重量不超过其最大载重量；式(15)表示到达客户点j的时间等于冷藏卡车到达物流中心i的时间与冷藏货车到达客户点j的时间之和；式(16)表示冷藏卡车从物流中心i调配到物流中心j的送货量；式(17)表示冷藏卡车从物流中心j调配到物流中心i的集货量；式(18)表示消除子回路。

2 基于K-means聚类的混合蚁群算法

针对多中心冷链共同配送车辆路径优化模型，设计基于K-means聚类的混合蚁群算法来求解该模型。根据客户的地理位置，通过K-means聚类算法计算客户点距离物流中心的欧氏距离，并将其分配到离该客户距离最近的物流中心。应用节约算法形成各聚类单元初始路线。然后设计改进混合的蚁群算法对各聚类单元之间的路径进行优化，其中将局部搜索算法的局部寻优能力应用于容易陷入局部最优的蚁群算法，通过不断迭代，最终得到最优配送路线。

2.1 K-means聚类算法

本文使用的K-means聚类算法是在聚类点坐标已知的前提下，计算各个客户点到聚类点的欧式距离，根据计算结果将客户点分配到距离最近的聚类点，确定客户和物流中心的服务关系。假设物流中心i的坐标为(xi,yi)，客户点j的坐标为(xj,yj)，则客户与物流中心的计算公式为：

2.1.1 改进的混合蚁群算法

多中心冷链物流车辆路径优化模型属于VRP的拓展问题，它是在经典VRP的基础上考虑多中心、客户时间窗、新鲜度等因素，属于NP-hard问题。蚁群算法属于启发式算法，可以依靠其较强的鲁棒性和搜索较优解等优点，有效的解决路径优化问题。但是蚁群算法收敛速度慢并且容易陷入局部最优。通过设计动态信息素挥发因子更新机制和信息素增量奖励机制来帮助算法跳出局部最优。另外，局部搜索算法可通过插入、互换、2-opt操作提高算法的局部搜索能力，进而提高算法的全局搜索能力。因此，本文旨在将蚁群算法的全局寻优能力和局部搜索算法的局部优化能力相结合，从而快速求得最优解。算法流程如图2所示。

图2 改进的混合蚁群算法流程

2.1.2 构建路径

在蚁群算法中，蚂蚁在刚开始搜索时具有盲目性，所以采用文献[24]中节约矩阵原理形成初始路线。路径上信息素浓度的高低和启发函数重要程度因子的大小决定蚂蚁选择下一路径的概率。为了形成最优路径，避免陷入局部最优，设计确定性选择和随机性选择相结合的策略，并且在转移概率公式内引入车辆等待时间与时间窗宽度启发式因子，利用轮盘赌去选择下一个要转移的点。转移概率如式(20)所示：

其中：Tabuk记录蚂蚁已经走过的路径，τij(t)为t时刻路径i、j上的信息素，为t时刻路径i、j的可见度，width=bj-αj为时间窗宽度，α、β、γ、λ分别为信息素因子、启发式因子、时间窗宽度因子、等待时间因子，Pc为转移规则的参数，Pc=[0，1]。

2.1.3 自适应信息素因子更新机制

蚂蚁从客户点i到下一个客户点j会分泌一种叫“信息素”的化学物质，蚂蚁会根据路径上信息素浓度的高低选择下一个要走的路径。同时信息素也会挥发，当蚂蚁经过所有客户点后，需要对全局路径上的信息素进行更新，通过不断迭代最终蚂蚁找到最优路径。信息素更新公式为：

信息素挥发系数ρ的取值影响着蚁群算法的全局搜索能力和收敛速度，ρ值过大，算法容易陷入局部最优，ρ值过小算法收敛速度过快。为了快速准确的得到最优路径，设计一种动态信息素挥发系数更新机制，如式(23)所示：

其中：N为当前迭代次数，N_max为最大迭代次数，ρmin为信息素挥发因子最小值。

式(22)中Δτij(t)表示本次迭代中路径i，j上信息素的增量，表示蚂蚁k在路径i，j上留下的信息素。为了进一步增强算法的全局寻优能力和加快收敛速度，设计一种信息素奖励机制：记录当前最优路径为Route_best，计算每次迭代蚂蚁的路径长度为Route_iter，若Route_iter＜Route_best，则对该蚂蚁走过的路径进行信息素奖励，采用式(24)，若Route_iter≥Route_best，则采用正常信息素更新方式，采用式(25)。

2.1.4 局部搜索算法

蚁群算法容易陷入“早熟”，得到的解不一定是全局最优解。为了弥补这一缺陷，增大解的空间性，在每次迭代的最优解的基础上，引入“插入”、“互换”、“2-opt”局部搜索操作，对路径内进行搜索。若操作后的成本小于操作前的成本则保留该路径。若操作后的成本大于操作前的成本，则保留操作前的路径。操作方式如下：

1）插入操

在路径上随机选择两个客户点i、j，将客户点j从路径中删除，然后将客户点j插入到客户点i的后面，如图3所示。

图3 插入

2）互换操

在路径上随机选择两个客户点i、j，将客户点i的位置和客户点j的位置进行互换，如图4所示。

图4 互换

3）2-opt

在路径上随机选择两个客户点i、j，客户点i保持不变，倒序排列客户点i、j间的客户，如图5所示。

图5 2-opt

2.2 算法检验

为了验证改进的混合蚁群算法的有效性，将该算法与改进的蚁群算法[25]、遗传算法进行对比分析。选取Cordeau的数据集（http://iescm.com/vrp/instances/P5MDVRPTW.asp）中pr01-pr04作为验证算例基础，数据集中物流中心数为4，客户规模分别为48、96、144、192，并附加客户需求量、客户关系、客户服务时间，对比结果如表1。其次选取文献[25]中的多中心配送问题实例进行检验，该算例包括4个物流中心和48个客户点坐标、需求、时间窗以及服务时间，对比结果如表2所示。其中TL为行驶路径，TC为总成本，AVG/%为平均值改进幅度。

表1 MDVRPTW标准算例对比

表2 MDVRPTW实例对比

编程采用MatlabR2021a进行开发，操作系统为Windows10，电脑内存为8G，CPU为Intel i5-11260H，主频为2.6GHz。关键参数设置如下：蚂蚁数量m=客户数×1.5，最大迭代次数inter_max=100，选择概率Pc=0.7，交叉概率Pm=0.8。

对四组规模不同的算例的计算结果如表1所示，本文所提出的改进的混合蚁群算法在总行驶路径和总成本方面均优于改进的蚁群算法和遗传算法。在平均行驶路径方面，改进混合蚁群算法计算得到的平均行驶距离比改进的蚁群算法减少了6.8%，比遗传算法减少了11.5%。在平均总成本方面，改进的混合蚁群算法的计算结果比改进的蚁群算法节约了8.1%，比遗传算法节约了11.7%。

对文献[25]的实例数据计算5次结果如表2所示，本文所提出的改进蚁群算法所求平均行驶路径和平均总成本分别是1278.8元、27804.3千米，比改进蚁群算法减少12.6%、18.5%，比遗传算法降低了17.8%、23.2%。其中表3为最优车辆行驶路线。

表3 改进的混合蚁群算法最优路径

根据上述对比结果可知，改进的混合蚁群算法在求解质量上比其他算法有更大的优势。其主要原因在于设计的动态信息素衰减系数、信息素奖励机制和局部搜索操作提高了算法的全局寻优能力，避免了算法陷入局部最优。证明了改进的混合蚁群算法在求解MDVRPTW问题的有效性。

3 基于Shapley值的利润分配模型

多家冷链物流企业成立联盟，共享客户资源和转运车辆，最大的收益是成本的降低。联盟将这部分成本节约值作为利润进行分配，并将利润合理、准确分配给参与联盟的物流企业来保证联盟的稳定运行。合作博弈论理论中Shapley值法是Shapley LS（1953）[26]所提出的求解多人合作的利润分配方法，本文选用该方法进行利润分配。

3.1 联盟可分配利润

假设联盟的参与者有N个成员，则能够形成2N-1个联盟子集，其中T=(1,2,3…,t)为N的任意一个子集，V(T)为定义在N上的一个实数值函数，即V(T)是联盟T可分配的利润，C(T)为联盟T的总成本，C(i)为成员i独立运营成本。每个联盟的成本节约值为该联盟的利润分配值，计算方法如式(26)所示：

3.2 联盟成员利润分配值

Shapley值模型的核心是根据每个成员对联盟所做的贡献程度进行分配利润。根据式(27)计算结果可知联盟的可分配利润值，根据式(28)计算每个成员i在联盟中可分得利润。

其中：Ti为包含成员i的联盟，|T|为联盟中成员个数，w(|T|)为加权因子，V(T)为联盟总收益，V(T/i)为除去成员i获得的收益，[V(T)-V(T/i)]为成员i在联盟中所产生的边际贡献，为联盟成员所分得收益值。

4 算例分析

本文所提出的模型为带时间窗的多中心车辆配送问题，选取MDVRPTW标准算例（https//github.com/PariseC/Algorithms_for_solving_VRP/tree/master/data/MDVRPTW）来验证模型的可行性，随机选取该算例的50个客户，算例有3个物流中心，客户服务关系是[1,3]的随机整数。

算例参数设置如下：冷藏卡车的载重Gl=20t，冷藏货车的载重为Gk=10t，冷藏卡车单位固定成本f1=800元/辆，冷藏卡车单位运输成本c1=16元/km，冷藏货车车单位固定成本f2=400元/辆，冷藏货车单位运输成本c2=9元/km，车辆平均行驶速度为V=60km/h，冷藏卡车开门时和运输过程中单位时间制冷成本分别为λ1=50元/h，λ2=0.8元/km，冷藏货车开门时和运输过程中单位时间制冷成本分别为b1=20元/h，b1=0.3元/km，生鲜商品的单位价值δ=5元，生鲜商品的腐败率δ=0.002，时间窗早到等待因子=30元/h，时间窗晚到惩罚因子β=50元/h，产品最低新鲜度要求Gb=0.75。算法参数设置：蚂蚁数量m=50，最大迭代次数inter_max=100，信息素重要程度因子α=1，启发函数重要程度因子β=3，等待时间重要程度因子λ=2，时间窗跨度重要因子γ=3，更新信息素浓度常数Q=5，信息素奖励系数μ=1.5，选择概率Pc=0.7，交叉概率Pm=0.8。

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

应用K-means聚类算法确定客户的服务关系，表4为聚类前服务关系归属表，表5为聚类后服务关系归属表。应用改进的混合蚁群算法计算不同配送模式下总行驶距离和成本，表6为独立运营模式和共同配送模式下对比结果。由对比结果可知：

表4 聚类前服务关系归属表

表5 聚类后服务关系归属表

表6 不同模式下优化结果

1）独立运营模式下各个企业冷链物流中心之间的客户资源未共享，各个物流中心之间不存在资源的集中调配，总行驶距离为1752.13千米，车辆行驶路径图如图6所示。在共同配送模式下，共享客户资源减少了大量的过远运输、交叉运输等，总行驶距离为947.42千米，比独立配送减少了45.9%，车辆行驶路径图如图7所示。

图6 物流中心独立运营模式下路径优化结果

图7 物流中心共同配送模式下路径优化结果

2）独立运营模式总成本为19994.83元，而共同配送模式下总成本为14627.59元，减少了行驶距离和车辆使用数，使配送顺序和车辆调配更合理，故使成本下降26.8%。

4.2 不同联盟模式下利润分配分析

联盟规模的大小会影响联盟最后的利润。假设上述算例中DC1、DC2、DC3分别为三家冷链物流企业A、B、C的物流中心，利用Shapley值法计算每个企业在不同联盟中的利润。如果三个企业未组建联盟，各自单独配送，各自从联盟获利0元。若企业A和企业B组建联盟，可产生共同利润2275.68元，企业A和企业C组建联盟，可产生共同利润533.53元，企业B和企业C组建联盟，可产生共同利润574.63元。如果企业A、B和企业C达成共识组建联盟，可产生共同利润4792.24元。

利用Shapley值利益分配模型（式(27)、式(28)）计算建立联盟后企业A、B、C的利润分配值。结果如表7所示，当企业A与企业B建立联盟时可分得的利润均为1137.84元，当企业A与企业C建立联盟时可分得的利润均为266.665元，当企业B和企业C建立联盟时可分的利润均为287.315元，但当企业A、B、C共同组建联盟时可分的利润分别为2874.07元、1894.63元、1023.54元。通过对比不同联盟组合下的利润分配值发现，组建成大联盟之后，联盟的整体运营成本比小联盟运营成本降低更多，各成员比独立配送和两两组建联盟所获得的利润值更明显。

表7 不同联盟体下的利润分配表

5 结语

冷链物流企业之间建立联盟有助于优化当前物流网络，可以大幅降低企业成本，而科学合理规划车辆路径和建立联盟利润分配机制是关键。本文对于多中心共同配送及利润分配进行了研究，得到了以下的结论：

1）本文提出的多中心冷链共同配送车辆路径优化问题，可以解决物流中心独立配送中过远运输、交叉运输、生鲜商品交付时新鲜度低的弊端。

2）运用K-means聚类算法对客户进行分类，引入节约算法提高了初始解的质量，通过改进蚁群算法概率转移规则、设计动态更新信息素衰减系数和信息素奖励机制，提高了算法的全局搜索能力，最后结合局部搜索算法提高了算法的局部搜索能力。通过选取标准算例和实例分别进行计算，证明本文算法的求解质量优于改进蚁群算法和经典遗传算法，证明了本文算法的有效性。

3）根据算例计算结果证明，多中心冷链配送联盟能够有效的减少冷链企业车辆配送距离、车辆使用数量进而提高了企业的利润，并且联盟规模越大企业可获得的利润越多。

本文的研究能够为多个企业建立多中心冷链共同配送联盟提供较好的解决方案，但是本文未考虑不同温度下的生鲜商品和客户的动态需求。因此，在多中心共同配送联盟的研究中考虑不同温度下的生鲜商品和客户动态需求是下一步研究的方向。