多中心联合取送货车辆路径优化与利润分配

王新杰，陈淮莉

上海海事大学 物流科学与工程研究院，上海 201306

近年来，电子商务蓬勃发展，产品更新换代速度不断加快，根据《中国电子商务报告2020》显示，该年全国网上零售额突破117 601亿元，同比增长10.9%[1]，随着直播带货等销售形式的产生，以及电商7天无理由退货等政策的推广，消费者由于利益驱动、冲动消费、信息不对称以及产品缺陷等因素造成的网络购物退货的现象越来越多[2]。例如，阿里巴巴集团在2016年至2020年间筹划的“双十一”活动中，商品退货率处于25%至40%之间，而研究表明电商零售产品的平均退货成本普遍比传统零售产品高[3]。因此，科学合理的组织电子商务逆向物流，有助于物流企业减少退货时间，降低运输成本，提高客户满意度，打通“第五利润源”。共享经济背景下，共享物流模式成为新发展趋势，不少物流企业通建立横、纵向合作，通过共享物流资源实施协同运输，从而降低成本，车辆路径问题（vehicle routing problem，VRP）是其核心问题。

国内外学者对共享物流模式下车辆路径优化问题已做出系列探索。起初，学者基于车辆资源共享情景，将协同运输模式引入到城市物流中进行研究，Liu等[4]基于多配送中心问题，以空车移动距离最小化为目标，提出两阶段贪婪算法对大规模算例进行求解。Wang等[5]提出协同的两级物流联合配送网络，建立以总成本最小为目标的线性优化模型，并运用一种蚁群算法和遗传算法相结合的混合启发式算法进行求解，有效减少城市货物运输系统的交叉运输现象。接着，学者针对纵向共享模式展开研究，Zhang等[6]基于二级物流网络，提出了一种通过承运方与仓库之间的协作来缩短运输距离的路径优化模型，并设计基于邻域搜索的EVNS算法，证明了模型的有效性。He等[7]研究了由制造商和零售商组成的双渠道电子商务供应链中的物流服务共享及其竞争问题，分别在有、无纵向物流服务共享的情景下，探索公司利润的变化，为纵向物流服务共享模式下车辆路径问题的研究奠定了基础。

随着研究深入，学者发现若物流企业之间开展横向合作，共享车辆、物流中心、客户订单等资源，则可以较大程度地避免过远运输、交叉运输和迂回运输的现象，从而降低成本。Li等[8]基于配送中心共享的带时间窗开放式多中心车辆路径问题，提出自适应局部搜索混合遗传算法进行求解，证明了解的质量优势。刘家利等[9]基于车辆租赁和车辆共享，提出了带时间窗的多配送中心开环车辆路径问题，并结合扫描算法和C-W节约算法设计混合遗传算法求解，通过实例证明算法具有良好的性能。葛显龙等[10]面向跨区域多中心多车型开放式联合配送车辆路径问题，引入时间轴概念，建立“多对多”动态车辆路径优化模型，并利用云遗传算法进行求解，开辟了动态多中心联合配送的车辆路径优化问题研究。付朝晖等[11]首次考虑客户服务关系变化与客户需求的异质性情况，在共享客户需求、配送车辆以及物流中心的情境下，设计多中心横向共享物流模式，并建立以总成本最小为目标的共同配送车辆路径优化模型，通过改进的蚁群算法进行求解，证明物流企业之间通过共同配送，可以大幅度降低物流成本，但是未考虑客户时间窗约束，有一定局限性。范厚明等[12]在已有研究的基础上，融合随机需求理论，研究集货需求随机情况下，多中心联合的同时取送货车辆路径问题，并设计自适应变邻域文化基因算法进行求解，但是未考虑多中心联合后的利润分配问题。Yong等[13]将共同配送理论应用到冷链物流领域中，提出物流设施共享的多中心协同车辆路径问题，以成本与冷藏车数量最小为目标，建立双目标整数规划模型，并利用k-means算法和禁忌搜索非支配排序遗传算法求解，丰富了冷链物流车辆路径优化的研究。

综上所述，国内外学者对横、纵向共享物流模式下车辆路径问题的研究已取得丰富成果。电子商务逆向物流由于其需求规模大、分布广泛、单一需求量小、具有时间窗约束等特点，更适于横向共享物流模式。然而，目前将共享物流模式运用于电子商务逆向物流的研究并不多，同时考虑到现实中的物流企业若建立横向联盟，需要科学的共同利润分配机制作为支撑，而很少学者关注到联盟参与者之间的利润分配问题。鉴于此，本文提出多中心联合取送货的车辆路径优化与利润分配问题，在共享车辆与客户订单的条件下，考虑客户时间窗约束，以变动运输成本、固定运输成本和惩罚成本之和最小为目标，建立MJVRPSDPTW模型，并根据模型特征设计基于大邻域搜索的混合遗传算法进行求解，最后利用Shapley值法对物流企业联盟后的共同利润进行分配，并通过对比联盟前后的物流成本，验证模型有效性。

1 多中心联合取送货模型

1.1 问题描述

在区域内有若干家物流企业，每个物流企业拥有一个物流中心和若干客户点。物流企业联盟前与联盟后的网络差异如图1所示，观察可知，联盟之前四个物流中心相互独立，各自服务对应的客户，从而存在大量交叉运输的现象。然而，当物流企业建立横向联盟后，通过共享车辆、物流中心与客户订单等资源，可以实现开放式联合取送货的运作方式。该模式下各物流中心服务邻近客户，通过集成运输实现物流中心与客户订单共享，从而减少交叉运输、过远运输等现象，最终对联盟共同利润进行合理分配，以保证联盟稳定性。相比联盟前，该模式减少车辆空驶里程，降低网络的总物流成本，同时有利于缓解交通拥堵和减轻碳排放。

图1 联盟前后对比Fig.1 Comparison before and after alliance

在实际中，联盟的组织者可以是该物流网络中的一家物流企业，也可以是第三方物流平台，本研究设定联盟组织者为其中一家物流企业[14]。为了模型更贴合实际，现在做出如下假设：

（1）各物流中心的货源不限，车辆数不限。

（2）客户点具有时间窗约束和同时取送货需求。

（3）每个客户点的需求信息和位置信息已知，必须且仅被服务一次。

（4）各物流中心通过厢式货车对各客户点进行取货和送货服务，且物流中心之间通过半挂式卡车进行调配货物。

（5）客户服务关系改变时，需对应货物从原物流中心调配至新物流中心。

（6）用于运输的车辆具有容量约束且是同类型的。

（7）车辆从物流中心出发，完成服务后返回最近的物流中心。

此外，为简化模型计算，将车辆行驶速度、单位运价、车辆固定成本、车辆载重量等参数设为整数。

1.2 符号说明

（1）集合

N：各节点集合，N={1,2,…,n,n+1,…,n+m}，包含n个客户点和m个物流中心；

C：各客户点集合，C={1,2,…,n}；

D：各物流中心集合，D={n+1,…,n+m}；

K：厢式货车集合，k∈K；

T：半挂式卡车集合，t∈T；

（2）参数

pi：客户点i的取货需求量，i∈C；

di：客户点i的送货需求量，i∈C；

si：厢式货车在客户点i的服务时间，i∈C；

[ai,bi]：客户点i的服务时间窗；

α：厢式货车早于ai到达客户点时的惩罚系数；

β：厢式货车晚于bi到达客户点时的惩罚系数；

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

Dij：物流中心i调配至物流中心j的送货量；

lij：i和j两节点之间的距离，i,j∈N；

c1：厢式货车单位变动运输成本；

c2：半挂式卡车单位变动运输成本；

f1：厢式货车固定运输成本；

f2：半挂式卡车固定运输成本；

Qk：厢式货车最大载重；

Qt：半挂式卡车最大载重；

v：厢式货车平均速度；

M：无穷大的正数；

（3）变量

xijk：厢式货车k从客户点i出发到客户点j时为1，否则为0，其中i,j∈C；

tik：厢式货车k到达客户点i的时间，其中i∈C；

qijk：厢式货车k从客户点i出发到客户点j时的负载，其中i,j∈C；

yk：厢式货车k投入使用时为1，否则为0；

Xijt：半挂式卡车t从物流中心i出发至物流中心j时为1，否则为0，其中i,j∈D；

rijt：半挂式卡车t从物流中心i出发至物流中心j时负载，其中i,j∈D；

Zhij：客户h的服务关系由物流中心i转移至物流中心j时为1，否则为0，其中h∈C且i,j∈D；

Yt：半挂式卡车t投入使用时为1，否则为0。

1.3 模型建立

该MJVRPSDPTW模型的总成本包括：固定运输成本、变动运输成本以及惩罚成本。其中固定运输成本是指厢式货车和半挂式卡车的启动成本，不随运输距离而变化；变动运输成本是指厢式货车和半挂式卡车的保养和燃料等费用，与运输距离成正比；惩罚成本是指厢式货车超出时间窗对客户进行服务造成的损失，模型具体数学表达如下。

1.3.1 目标函数

厢式货车的变动运输成本与固定运输成本：

半挂式卡车的变动运输成本与固定运输成本：

厢式货车超出时间窗服务的惩罚成本：

总运输成本为三者之和，则目标函数表示为总成本最小，如式（4）所示：

1.3.2约束条件

该模型满足的约束条件如下：

约束（5）表示任意客户只能被一辆厢式货车服务一次，约束（6）表示厢式货车不能从一个物流中心直接到另一个物流中心，约束（7）表示半挂式卡车只能在物流中心之间调配货物，不能对客户点进行服务，约束（8）和（9）保证决策变量的一致性，约束（10）表示厢式货车从物流中心出发，完成任务后返回任一个物流中心，约束（11）和约束（12）分别为厢式货车和半挂式卡车的容量约束，约束（13）表示厢式货车的载重变化，约束（14）表示半挂式卡车从物流中心i调配至j的送货量，约束（15）表示半挂式卡车从物流中心j调配返回物流中心i的集货量，约束（16）表示厢式货车服务时间的连续性，约束（17）用于消除子回路。

2 基于大邻域搜索的混合遗传算法

在处理多中心车辆路径问题过程中，大多学者通过客户划分的方式将其转化为多个单一中心问题处理，这种方式使各中心之间相互独立，不能从整体上对物流网络进行优化，得到的结果往往较差，故本文采用整体法，提出虚拟中心概念。假设所有厢式货车均从虚拟中心出发，先到达实际物流中心再到达客户点进行服务，服务完成后要求先回到实际物流中心，最后返回虚拟中心[15]。其中，虚拟中心并不实际存在，其与实际中心之间的距离、运费等参数均为0。

文本提出的MJVRPSDPTW是VRP的变体，属于NP难问题。此外，该问题基于开放式车辆路径且考虑时间窗约束，计算难度远大于传统VRP问题，很难得到精确解。因此，采用启发式算法求其近似最优解，遗传算法（GA）具有良好的鲁棒性和并行性，但传统的遗传算法易陷入局部最优，从而过早收敛[16]。大邻域搜索算法（LNS）可通过“破坏”和“修复”算子，对现有解动态优化的局部搜索算法，具有良好的深度搜索能力。因此，本文设计了一种基于大邻域搜索的混合遗传算法进行求解，旨在将遗传算法良好的全局寻优能力与大邻域搜索算法局部寻优能力相结合，从而快速找到最优解，算法总体设计思路如下：

（1）设置虚拟中心，对多中心网络进行整体优化。

（2）遗传算法的选择算子采用精英保留与轮盘赌相结合的策略；交叉算子采用OX交叉方式；变异算子采用两点交换的方式。

（3）将大邻域搜索算法的“破坏”与“修复”思想用于遗传算法的局部搜索过程中。

算法的具体步骤如下：

步骤1编码

本文采用自然数编码的方式，数字0表示虚拟中心，基因序列为客户服务的顺序。

步骤2参数设置

输入客户点、物流中心坐标、客户取送货需求量、时间窗、单位距离运费、车辆最大容量等模型参数。令种群规模为pop，最大迭代次数为max，交叉概率为pc，变异概率为pm，当前迭代次数为ξ，当前总成本为costξ。

步骤3种群初始化

采用载重约束与时间窗约束[17]生成初始种群。

步骤4解码

计算适应度函数值前要对个体进行解码，即实现虚拟中心到实际中心的转换。此处定义算子，输入虚拟中心的邻近客户点以及各节点之间的距离矩阵，从而得到距离最近的实际物流中心。具体示意如图2所示，其中49至52代表四个实际物流中心。

图2 解码Fig.2 Decoding

步骤5适应度函数

以总成本的倒数作为适应度函数，总成本越小则染色体的适应度值越大，具体如式（18）所示：

步骤6选择操作

此处采用精英保留策略与轮盘赌相结合的方式，将适应度值最高的个体保留至下一代，用于替换下一代初始适应度值最低的个体，同时对所有个体通过轮盘赌的方式进行选择和复制。

步骤7交叉操作

当满足概率pc时，发生交叉操作。此处采用OX交叉[20]方式，具体如图3所示。

图3 OX交叉Fig.3 OX crossover operator

步骤8变异操作

当满足一个较小概率pm时，染色体发生变异，从而保证多样性。此处采用随机交换两个客户基因位的方式，进行变异操作。

步骤9破坏算子

该算子旨在减少车辆数，从当前解A中移除λ个客户，剩余部分解用A′表示，移除的客户组成集合L，则具体步骤如下：首先，从短路径中随机选择一个客户移除。其次，在A′中选择与上一个被移除客户之间相关性最高的客户移除，不断重复直至移除λ-1个客户，其相关性计算如式（19）所示[18]：

其中，为i和j间标准化后的距离；Vij为0-1变量，当i和j在同一条路径上时Vij取0，否则为1。

步骤10修复算子

将L中的客户依此选择最优的位置插回A′中，得到改进后的解A″。在此过程中，要满足客户时间窗约束和车辆容量约束，同时使新个体的适应度值更高。具体如下：（1）随机选取L中的一个客户Li，在A′中找到满足时间窗和车辆容量约束的所有插入点；若无合适插入点，则在末尾插入新路径，并将Li作为新路径的首个客户。（2）计算客户在各可能插入点的插入成本，并选择最小成本对应的插入点进行插入。（3）返回（1）循环，直至将L中所有客户均插入A′，从而得到新解A″，当新解适应度值大于解A的适应度值时，保留新解A″。

步骤11更新迭代

更新当前最优适应度值，用精英个体代替种群中适应度值最低的个体，并返回步骤4，记ξ=ξ+1。

步骤12结束

当迭代次数ξ达到最大迭代次数max时，结束算法并输出当前最优解。

该算法流程如图4所示。

图4 混合遗传算法流程Fig.4 Hybrid genetic algorithm steps

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

3.1 可分配利润计算

当多个物流企业建立联盟U后，开展联合取送货服务，大大降低了运营成本。接着基于优化后的网络，计算共同利润，即总成本的节约值C(U)，以及可分配共同利润M(U)。通常联盟的组织者会将一定比例的共同利润作为其组织联盟的报酬，并将剩余利润按照科学合理的方法分配给各联盟参与者[19]，具体如式（20）和（21）所示：

其中，v0(ξ)表示成员ξ未参与联盟时的成本。v(U)为联盟U的总运营成本；ρ表示联盟组织者提取利润的比例，且0≤ρ≤1。

3.2 条件假设与利润分配

Shapley值法是由Shapley[20]提出的多人合作博弈利润分配问题的一种求解方法，应满足行为理性假设与收益理性假设。在此处，行为理性假设指任意物流企业ξ在参与联盟后的最终成本v(ξ)不大于独立运营的成本v0(ξ)，具体如式（22）和（23）所示，其中，η(ξ)为成员参与联盟后的初始成本；φ(ξ)为成员参与联盟后得到的利润分配值。

收益理性假设是指，任意两个子联盟U1与U2合作后的总成本不大于其独立运营的成本之和，数学表达如式（24）所示：

根据Shapley值相关理论[21]可知，成员ξ的利润分配值φ(ξ)如式（25）所示，且最终联盟成本v(ξ)如式（26）所示。其中，Dξ表示大联盟D中包含成员ξ的所有子集形成的集合，|U|表示子联盟U的成员个数，v(U{ξ})表示子联盟U去掉成员ξ之后的成本。

4 算例分析

4.1 算例设置

由于目前没有共享物流模式下，多中心联合取送货问题的标准数据集，故以MDVRPTW数据集（http：//neumann.hec.ca/chairedistributique/data/mdvrp/new）为基础，附加客户服务关系与客户取货需求量，作为本文的测试数据。其中，各数据集的物流中心数为4，各客户的服务关系为[1，4]之间的随机整数，分别对应4个物流中心。此外，各数据集的客户数目最小为48，最大为192。设厢式货车最大载重量Qk=100，平均行驶速度v=60，固定运输成本f1=200，单位变动运输成本c1=1；半挂式卡车最大载重量Qt=200，固定运输成本f2=300，单位变动运输成本c2=2，时间窗惩罚系数α=0且β=10。

算法在Windows10（64 bit，16 GB）环境下，采用MATLAB R2020a进行开发，其参数设置如下：种群规模pop=200，最大迭代次数max=100，交叉概率pc=0.9，变异概率pm=0.4。

4.2 结果分析

4.2.1 联合取送货路径优化结果分析

在修改后的MDVRPTW数据集中，采用pr01至pr14进行实验，其中数据集pr01至pr04分别与数据集pr11至pr14拥有相同的节点坐标、客户取送货需求与服务时长，仅客户服务时间窗不同。为验证所提出的基于大邻域搜索混合遗传算法的有效性，本文分别与基于客户划分的两阶段规划法及经典遗传算法进行对比，结果如表1所示。其中，IN为数据集名称，ND为物流中心数量，NC为客户数目，NV、NT分别为厢式货车与半挂式卡车的数量，TC为总成本，NTW为超出时间窗进行服务的客户数。

表1 不同算法的多中心联合取送货路径优化结果Table 1 Optimization results of multi-center joint pick-up and delivery path with different algorithms

观察表1可知：（1）根据TC值，基于大邻域搜索的混合遗传算法在每个算例中得到的总成本均最低。相比两阶段规划法，总成本平均节约15.93%，相比经典遗传算法平均节约50.42%。（2）根据NV和NT值，基于大邻域搜索的混合遗传算法在各算例中使用的厢式货车数与半挂式卡车数均为最小，证明该算法拥有更高的车辆使用效率。其首要原因在于，整体法能够对“多对多”式网络进行整体优化，打破两阶段规划法各中心相互独立的限制，增强各物流中心之间的协作，实现车辆资源的有效共享。其次，该算法在经典遗传算法的基础上引进“破坏”与“修复”算子，增强了局部搜索能力，在保证客户服务水平的条件下降低车辆使用数目。（3）在客户数、中心数以及客户取送货需求相同的条件下，不同的服务时间窗会对配送方案及总成本造成较大的差异，面对大规模数据集，基于大邻域搜索的混合遗传算法会通过适当违反客户时间窗的方式灵活调整配送方案，从而减少车辆数及行驶路程，确保总成本最低。

4.2.2 不同模式下路径优化结果分析

此处以pr03数据为例，分别在多中心联合取送货模式与独立运营模式下进行对比实验，路径优化结果对比如表2所示，分析可知：（1）独立运营模式下，4个物流中心只对各自的客户进行服务，不涉及资源共享，故物流中心之间不存在集中调配，而联合取送货模式下，物流中心之间通过半挂式卡车进行货物调配，实现客户订单共享；（2）独立运营模式下，厢式货车总行驶里程为10 798.36 km，而联合取送货模式下，厢式货车总行驶里程为3 424.78 km，由于存在大量交叉运输等现象，独立运营模式的厢式货车总里程比联合取送货模式高出15.5%；（3）独立运营模式下的总成本为17 020.79，联合取送货模式下的总成本为14 733.84，联合取送货模式通过资源共享，使车辆运行更加有序，故总成本相比独立运营模式减少了13.44%。

表2 不同模式下路径优化结果Table 2 Optimization results of different mode

联合取送货与独立运营两种不同模式下，pr03算例路径优化图如图5所示，其中4个矩形代表物流中心，144个圆形代表客户点，物流中心之间加粗线代表半挂式卡车的货物调配路径，细线代表厢式货车的路径。观察可知：（1）图5（a）通过多中心联合取送货，整个网络较为有序，各物流中心主要为邻近客户点进行服务，有效减少了不合理运输的现象。但是，图5（b）采用各中心独立运营模式，物流中心只服务对应的客户，整体上存在大量交叉运输、过远运输与迂回运输的现象。（2）图5（a）中，4个物流中心之间存在路径连接，说明半挂式卡车在物流中心进行货物调配，实现客户订单共享，而图5（b）的4个物流中心之间不存在资源共享。（3）图5（a）中，部分厢式货车从一个物流中心出发，而到另一个物流中心终止服务，说明开放式网络实现车辆与物流中心共享，从而提高车辆满载率，减少空驶里程。然而，图5（b）的各厢式货车从一个物流中心出发，最终必须返回同一个物流中心，存在空驶里程，车辆有效利用率较低。（4）图5（a）中，部分厢式货车为降低总成本，通过违反少量软时间窗约束，避免迂回运输，从而减少总里程。图5（b）中，由于每辆厢式货车服务的客户数较少，很少存在违反时间窗的现象，但总成本较高。

图5 不同模式下pr03优化结果对比Fig.5 Optimization results of pr03 of different mode

4.2.3 不同联盟下成本对比分析

在实际中，联盟的成员数不同，其总成本的节约值也不同。以pr01数据集的路径规划结果为基础，利用Shapley值法对各物流中心在不同合作联盟下产生的利润进行分配，结果如表3所示。

表3 优化后网络的各联盟利润分配Table 3 Profit distribution of each alliance after optimization

其中，v0(U)是指在优化后的网络中，各成员未合作情况下的成本之和，v(U)指成员合作情况下的联盟总成本，φ(U)指联盟合作后产生的共同利润。观察可知，在不同的联盟情况下，当联盟内企业数为2时，产生的平均共同利润为2 219.3；当联盟内企业数为3时，平均共同利润为3 904；当联盟内企业数为4时，平均共同利润为6 589，即大联盟产生的共同利润最大。此外，在优化后的网络中，各中心在联盟前的利润分别为313、432、997和1 298，而在大联盟D中，各物流中心的利润分别为1 760、1 494、1 776和1 559，对比可知大联盟中各物流中心的利润分配值最高，即大联盟的稳定性最高。综上所述，在一定程度下，参与联盟的企业数越多，产生的共同利润越大。

5 结束语

共享模式下的电子商务逆向物流，可以降低企业运输成本，提高客户满意度，打通“第五利润源”，而科学的车辆路径规划与合理的联盟利润分配是关键。本文针对多中心联合取送货的车辆路径优化与利润分配问题进行研究，结论如下：

（1）在共享车辆与客户订单的条件下，考虑客户同时取送货情景与时间窗约束，建立MJVRPSDPTW模型，对共享物流与VRPSDP问题做进一步延伸。

（2）设计一种基于大邻域搜索的混合遗传算法进行求解。首先，该算法基于虚拟中心，从整体上优化网络。其次，将“破坏”与“修复”算子融入遗传算法的邻域搜索环节，增强了算法的局部寻优能力。通过多组算例对比实验，证明本文算法优于两阶段规划法与经典遗传算法，验证了模型及算法的有效性。

（3）基于优化后的网络，利用Shapley值法对不同联盟情况下的各物流企业进行利润分配，结果证明大联盟的共同利润最大且联盟最为稳定。

最后，本研究对多个物流企业开展共享物流模式具有一定的参考价值。但是，本文未考虑网络的动态变化及客户需求的不确定性。因此，时变交通网络及客户需求的不确定性是未来继续研究的方向。