基于车辆共享的多中心共同配送联盟优化

王 勇，周 雪，刘 永，许茂增

(重庆交通大学，经济与管理学院，重庆 400074)

0 引言

共享经济的发展为城市物流多中心共同配送网络构建带来了新的机遇，而实现配送车辆在多个中心之间的合理化共享调度，是城市物流配送企业获取最大化市场收益的关键。第三方物流的快速发展，使得物流配送企业可以通过车辆租赁方式实现车辆的使用和共享，进而拓展其物流配送能力。多中心共同配送网络构建涉及稳健的网络联盟构建和合作机制设计，而基于车辆共享的多中心共同配送网络可以实现物流配送效率的有效提升和物流资源的集约化利用。国内外学者在多中心共同配送和车辆共享调度方面进行了一系列研究。

在多中心共同配送问题方面，盛虎宜等[1]设计了一种改进的蚁群算法，研究了多中心联合配送的生鲜品半开放式车辆路径问题。刘明等[2]提出一种混合协同配送模式，并应用改进的启发式搜索算法研究了应急物资的配送问题。范厚明等[3]研究了生鲜商品多中心共同配送问题，并应用蚁群算法求解了冷藏车的配送路径。王勇等[4]提出改进的遗传—粒子群混合优化算法，研究了多中心共同配送的收益分配优化问题。LI等[5]应用一种基于储蓄的变邻域搜索算法，研究了考虑实时转运能力变化的两级多中心共同配送问题。WANG等[6]提出一种基于蚁群与遗传算法的混合算法，研究了两级设施多中心共同配送问题。由上述文献可知，多中心共同配送问题方面的研究已取得了一系列的进展，但在多中心共同配送的合作序列选择以及合作联盟构建等方面还需进一步拓展研究。

在车辆共享调度方面，刘家利等[7]提出了不同配送中心间的车辆共享机制，研究了企业运力不足时车辆租赁和自有车辆的调度决策问题。JIN等[8]研究了纯电动汽车的共享模式，并提出了应用多种定价策略来提高共享车辆的使用率。WANG等[9]在多中心开放式车辆路径问题中引入了车辆共享机制，减少了总运营成本和车辆使用数，但未涉及考虑多中心内部和多中心间闭合式的车辆共享问题以及多中心合作的收益分配问题的研究。Friedrich等[10]探讨了车辆共享系统在多式联运公共交通网络中的优势，提出了有效控制出行需求的建议。上述文献在将车辆共享机制与多中心共同配送联盟相结合方面的研究还有待深入。

本文研究了基于车辆共享的多中心共同配送网络优化问题，首先，建立了包含最小化物流成本和车辆数的双目标优化模型，并提出一种基于K-Means时空聚类的Clarke-Wright-带精英策略的快速非支配排序遗传算法(Clarke-Wright-fast elitist Non-dominated Sorting Genetic Algorithm-Ⅱ，CW-NSGA-Ⅱ)混合算法求解双目标优化模型，在混合算法过程中设计了聚类单元间染色体选择、交叉和变异的精英循环迭代过程，提高了种群多样性，增强了算法的全局和局部搜索能力；然后，应用改进的Shapley值法和严格单调路径原则研究了合作联盟稳定性和最优联盟序列选择；最后，通过实例分析探讨了非共享、配送中心内部共享和全局共享3种模式下的车辆使用数，共享线路数和物流成本的变化，进而为车辆共享模式下的物流配送问题提供新的研究思路。

1 问题描述

在现代的城市物流配送网络中，由于配送中心的建设时序和长期服务契约关系等现象的普遍存在，且物流企业间缺乏有效的资源共享和合作联盟构建，进而导致物流配送过程中存在延迟送达、长距离配送和交错运输等现象。为了有效地提高配送资源的利用率和降低多中心物流配送网络的运营成本，需要进行多中心间配送车辆的合理共享调度和多中心共同配送网络优化的合作联盟构建，进而提高多中心共同配送网络的可靠性和稳定性。

不同于多配送中心考虑multi-trip的车辆路径规划问题[11]，基于车辆共享的多中心共同配送网络优化问题需要考虑客户服务关系变化而在多个配送中心之间进行集中运输调度，且车辆可以在配送中心内部和配送中心之间实现资源共享，进而减少车辆使用数和降低物流运营成本。本文结合调研数据绘制了基于车辆共享的多中心共同配送网络优化前后对比图(如图1)，由于未考虑客户需求的异质性，图1中未考虑车辆在客户处的服务时间。图1a表示多中心共同配送网络优化前，配送中心服务客户配送线路的各时间窗存在时间交错和重叠等现象，且配送线路存在大量交错运输和长距离运输的情况，且存在违反时间窗的客户点，而多中心共同配送网络优化后(如图1b)，客户被分配到临近的配送中心接受物流服务，配送中心间进行合作产生配送需求变化的集中运输。此外，配送中心服务客户配送线路的各时间窗以及实现车辆共享的各配送线路不存在时间窗交错和重叠的现象，进而实现了配送中心内部以及配送中心之间有效的车辆共享，并消除了违反时间窗的客户点。如：配送车辆SV2在配送中心DC2中[1,8]和[18,26]两个时间域及配送中心DC5中[9,17]时间域内的三条配送线路的车辆共享。由于优化线路间存在部分线路通行时间交叉的现象，优化后的多中心共同配送网络存在非共享和共享车辆行驶路线共存的情况。

图1中线路上的数值表示车辆的行程时间，且以配送中心时间窗开始时间为车辆的出发时间。假设单位时间的运输成本为80元，单位时间的配送成本为50元，违反时间窗的单位时间惩罚成本为30元，运输车辆的租赁成本为150元/辆·次，配送车辆的租赁成本为100元/辆·次，联盟后的外部收益为450元。如表1所示为基于车辆共享的多中心共同配送优化前后服务时间、车辆使用数和物流成本等指标的比较。结果表明，基于车辆共享的多中心共同配送网络降低了配送服务时间，消除了违反时间窗的客户点，并减少了配送车辆使用数，进而降低了多中心共同配送网络的物流运营成本。多中心共同配送网络优化前后总成本的节约值是多中心间进行收益分配优化研究的基础，并为多中心共同配送合作序列选择和联盟构建提供了研究切入点，进而有利于基于车辆共享的多中心共同配送合作联盟形成。

表1 基于车辆共享的多中心共同配送优化前后对比

2 模型建立

2.1 符号定义

基于车辆共享的多中心共同配送网络优化问题的变量定义如表2所示。

表2 变量定义

续表2

2.2 模型构建

以多中心共同配送物流运营成本W最小化和配送车辆使用数V最小化为目标，建立基于车辆共享的多中心共同配送双目标优化模型：

minW=W1+W2+W3;

(1)

(2)

其中：W1为配送中心之间的运输成本和车辆租赁成本，并考虑配送中心间联盟的外部收益，

(3)

W2为配送中心服务客户的配送成本和车辆租赁成本，

(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)表示客户点在服务周期t内仅接受一个配送中心服务；式(7)表示每个客户仅接受一条配送线路服务；式(8)表示车辆v服务客户后必须离开；式(9)和式(10)表示车辆的装载量不超过车辆容量；式(11)表示客户在服务周期t内的需求总量不超过配送中心在服务周期t内的最大配送量；式(12)表示配送中心i到h的运输量等于服务关系改变的客户需求量之和；式(13)表示消除线路上的子回路；式(14)表示服务周期t内车辆v的使用次数等于其配送线路数之和；式(15)和式(16)表示车辆v服务客户的到达时间；式(17)和式(18)表示车辆v在配送中心的时间窗内进行服务；式(19)～式(25)表示决策变量。

3 基于K-Means时空聚类的CW-NSGA-Ⅱ混合算法

本文设计了基于K-means时空聚类的CW-NGSA-Ⅱ混合算法求解基于车辆共享的多中心共同配送联盟优化模型。基于K-means的时空聚类算法[12]首先结合客户服务时间窗划定客户的多个服务时间周期；其次，结合客户点的地理位置和时间窗进行多个服务周期的时空聚类操作；然后，应用CW节约算法[13]，在客户点聚类单元内生成初始配送线路；最后，应用NSGA-Ⅱ算法[14]进行不同聚类单元内和聚类单元间的线路调整和非支配排序优化，进而生成多中心共同配送优化线路。此外，K-means时空聚类算法和CW-NSGA-Ⅱ算法间的精英迭代交互过程设计可以有效避免配送中心间服务客户点数目不均的问题。混合算法流程如图2所示。

3.1 基于K-means的时空聚类

在K-means聚类算法的基础上，结合客户服务时间窗和地理位置信息构建三维时空坐标系，并计算客户点i与j之间的距离[15]，根据计算结果将每个客户点归属到不同的聚类中心。如果(x,y)表示地理坐标，[TW1,TW2]表示时间窗，ξ表示距离与时间的转换系数，则客户点间的距离计算公式如下：

Dij=|xi-xj|+|yi-yj|+ξ|TW1i-TW1j|+

ξ|TW2i-TW2j|,i,j∈J。

(26)

K-means时空聚类算法具体步骤如下：

步骤1导入配送中心位置坐标，客户点位置坐标、时间窗，距离与时间换算系数。

步骤2根据导入的需要聚类的客户时间窗数据，结合时间窗的分布特性确定服务周期数和服务周期区间。

步骤3在每个服务周期内将数据矩阵转换为数据向量，计算配送中心及客户点间的时空距离[9]。

步骤4设k等于配送中心数量，在每个服务周期内随机选择k个初始聚类中心。

步骤5计算每个客户点到聚类中心的时空距离，在相应服务周期内将客户点指派到最临近的聚类中心。

步骤6计算各服务周期内k个聚类单元的中心作为新的聚类中心，并更新各服务周期内的聚类中心。

步骤7重复步骤5～步骤7，直到聚类中心不再改变。

步骤8计算各聚类中心到各配送中心的距离，指派各聚类单元到最临近的配送中心。

步骤9输出聚类结果。

3.2 基于K-means时空聚类的CW-NSGA-Ⅱ混合算法实现过程

应用基于K-means时空聚类的CW-NSGA-Ⅱ混合算法进行优化计算和模型求解，相关变量定义为：popsize表示种群规模，genmax表示最大迭代次数，ps，pc和pm分别表示选择，交叉和变异概率，runmax表示精英迭代次数，NN表示精英染色体个数，Pt与Qt分别表示初始种群和子代种群，gen表示当前算法迭代次数，run表示当前精英迭代次数；混合算法的具体步骤如下：

步骤1设置参数包括种群规模popsize、最大迭代次数genmax、精英迭代次数runmax、选择概率ps、交叉概率pc、变异概率pm。

步骤2应用CW节约算法生成初始种群Pt，设置gen=1，run=1。

步骤3初始种群Pt由不同聚类单元内的染色体共同组成，不同聚类单元内的染色体组成了不同的初始优化解方案。对聚类单元内部和不同聚类单元间的染色体进行选择，交叉和变异操作生成子代种群Qt。具体的选择，交叉和变异过程如下述步骤(1)～步骤(3)所示。

(1)选择性精英保留操作。结合帕累托优化原理设计适应度函数并计算适应度函数值，根据聚类单元内和聚类单元间染色体的适应度大小应用轮盘赌方法经过多轮选择确定子代种群，并采用精英保留策略[9]，在每次选择过程中保留一定数量的精英染色体进入子代。

(2)交叉操作。根据交叉概率随机选择聚类单元内和聚类单元间的染色体进行交叉运算，并采用单点交叉法，两点交叉法和部分映射交叉法生成子代染色体[16]，并与父代染色体进行比较选择子代染色体。

(3)变异操作。根据变异概率随机选择聚类单元内和聚类单元间的染色体进行变异运算，并采用部分映射变异和互换操作算子生成子代染色体[15]，并与父代染色体比较选择子代染色体。

步骤4将Pt与Qt合并形成新的种群Rt，评价种群个体的目标函数值，进行非支配排序和拥挤距离计算，选择包含NN个精英个体组成的新父代种群Pt+1。

步骤5令run=run+1，判断是否达到运行次数runmax，若是则返回聚类算法步骤6进行循环操作，否则转混合算法步骤6。

步骤6令gen=gen+1，重复混合算法步骤3进行循环操作，直到达到最大迭代次数genmax。

步骤7通过计算染色体对应个体双目标函数值间的拥挤度距离确定帕累托前沿，并通过帕累托前沿比较计算得到的双目标解的帕累托优化解排序，进而通过排序选取帕累托优化解并输出最优解[15-16]，结束算法。

3.3 算法检验

将CW-NSGA-Ⅱ混合算法、多目标遗传算法(Multi-Objective Genetic Algorithm, MOGA)[17]和多目标粒子群算法(Multi-Objective Particle Swarm Optimization, MOPSO)[18]进行比较，随机生成20组实例数据如表3所示。根据已有相关文献[9,15]，算法参数设置为：种群规模popsize=100，最大迭代次数genmax=500，精英迭代次数runmax=20，精英染色体个数NN=30，选择概率ps=0.7，交叉概率pc=0.8，变异概率pm=0.15，惯性权重w=0.5。每组实例数据计算10次，选取成本最优值对应的优化结果，如表4所示。

表3 算例数据

表4 不同算法的计算结果比较

续表4

由表4可知，CW-NSGA-Ⅱ混合算法与MOGA和MOPSO所得结果有显著不同。CW-NSGA-Ⅱ混合算法计算的物流成本平均值比MOGA减少3.03%，比MOPSO减少3.07%；求解时间平均值比MOGA减少了12.7 s，比MOPSO减少了14.9 s。结果表明，所提算法具有更强的全局和局部搜索能力，并能有效求解大规模问题。

为进一步验证基于K-Means时空聚类的CW-NSGA-Ⅱ混合算法的有效性，选取10组带时间窗的多仓库车辆路径问题(Multi-Depot Vehicle Routing Problem with Time Windows, MDVRPTW)标准算例数据[9]进行所提算法的进一步验证，参数选取与上述随机实例数据相同，且每组实例数据随机计算10次，选取成本最优值对应的优化结果，计算结果如表5所示。

表5 标准数据集计算结果比较

由表5可知，提出的基于K-Means时空聚类的CW-NSGA-Ⅱ混合算法求解得到的优化值与已知最优值的平均值差值比例为2.28%，且所提算法在pr01，pr02和pr07四组实例数据分别求得了与已知最优值相同的结果，进而说明所提算法具有较好的稳定性和可靠性。

4 基于改进的Shapley值法的合作联盟构建

4.1 基于改进的Shapley值法的合作联盟序列选择

以车辆共享的多中心共同配送网络优化方案为基础，通过与初始物流配送网络进行比较计算，研究多中心共同配送的收益分配问题。Shapley值法[19]通常用于研究联盟过程中的收益分配问题，结合表2中的相应变量定义，应用改进的Shapley值法计算联盟成员的利润分配值，如式(27)所示:

[(1-ψi)×v(S)-v(S-{i})],i∈N。

(27)

由于多中心共同配送前后的物流运营成本节约值可以看作多中心共同配送联盟的收益值，而第三方物流服务提供商通过联盟过程可获得一定比例收益，联盟S的收益可通过式(28)计算得到，而又由于S⊆N，因此，总联盟N的收益也可通过式(28)变换计算得到:

(28)

基于收益分配结果，可以计算得到每个联盟成员进入合作联盟时的收益增加比例和已在联盟成员的收益增加比例，进而应用严格单调路径选择原则[20]进行合作联盟序列选择。当第o个成员加入联盟ω时，联盟成员i的收益增加百分比如式(29)所示:

(29)

4.2 合作联盟的核心值计算

合作联盟是实现多中心共同配送的基础，而合作联盟稳定性是衡量多中心共同配送网络鲁棒性的重要依据。根据雪球理论[21]，每种收益分配方法的结果与核心值间的距离被用作评判多中心合作联盟稳定性的标准，多中心合作联盟的核心值计算如式(30)所示:

(30)

5 算例及结果分析

5.1 算例相关数据

5.2 基于车辆共享的多中心共同配送优化方案

在每个服务周期内，应用所提混合算法求解多中心共同配送的物流成本和车辆使用数，得到各服务周期的共享车辆优化路径，如表6所示。

表6 基于车辆共享的多中心共同配送路线

续表6

5.3 基于车辆共享的多中心共同配送联盟

5.3.1 多中心共同配送合作序列选择和联盟构建

应用式(28)计算联盟收益增加百分比如图4所示，应用严格单调路径原则得出最优联盟合作序列ω1={DC1,DC4,DC5,DC3,DC2}如图5所示。首先，DC1与DC4合作，收益增加百分比分别为36.6%和39.9%；然后，DC5和DC3依次进入联盟，联盟成员的收益增加百分比分别为41.3%，41.3%，40.6%和40.2%；最后，DC2进入联盟，各成员收益增加百分比分别为47.8%，48.5%，44.3%，46.4%和44.2%。

5.3.2 多中心共同配送合作联盟稳定性

通过式(30)计算核心值为(1 208,1 032,1 236,1 082,1 053)，比较不同收益分配方案与核心值距离(表7)，改进Shapley值法均优于CGA，MCRS和EPM三种方法所确定的收益分配方案，具有更强的合作联盟稳定性。

表7 核心距离计算表

6.4 不同车辆共享模式的多中心共同配送合作联盟

不同车辆共享模式包括非共享、内部共享和全局共享3种模式，3种模式下的车辆使用数、共享线路数和物流运营成本等对比结果如表8所示。

表8 不同共享模式下多中心共同配送优化方案比较

由表8可知，全局共享模式求解的优化方案具有最少车辆使用数，最多共享线路数和最低物流运营总成本(如图6)。此外，在非共享，内部共享和全局共享3种模式下的联合优化物流运营总成本均高于多中心共同配送的物流运营总成本。为进一步分析和比较不同模式间的联盟特性，分别计算得到3种模式下的最优合作联盟序列(表9)和联盟成员收益增加百分比(表10)，可知全局共享模式下各联盟成员的收益增加百分比均优于另外两种模式，且各联盟成员均可获得较高利润，有利于提高合作联盟的稳定性，进而有助于促进合作联盟形成。

表9 三种模式下最优合作联盟序列 %

表10 三种模式下最优合作联盟成员收益增加百分比 %

6 结束语

本文研究了基于车辆共享的多中心共同配送网络联盟优化问题，考虑到现实物流配送网络中车辆共享频率低和合作联盟机制欠缺的问题，将基于车辆共享的合作联盟序列构建方法融入多中心共同配送网络优化问题中进行研究。首先，建立了一个考虑物流成本和车辆使用数的双目标优化模型，提出了基于K-means时空聚类的CW-NSGA-Ⅱ混合算法求解模型，在混合算法过程中设计了聚类算法和智能算法间的选择性赋予机制，提高了算法的全局搜索和局部寻优能力。其次，应用改进的Shapley值法研究了多中心共同配送联盟的收益分配，并应用严格单调路径原则选择了最优合作联盟序列和研究了联盟稳定性。最后，比较分析了非共享、配送中心内部共享和全局共享3种模式下的多中心合作联盟序列选择和收益增加百分比。研究结果表明全局共享模式能有效降低物流成本和提高配送车辆使用效率，进而增加多中心共同配送网络的联盟稳定性。本文所提方法有利于多中心共同配送网络联盟构建，并能更好的应用到基于资源共享的多级物流配送网络优化和联盟构建研究中。