基于联合配送与资源共享的多中心车辆路径优化研究

石永强 黄韵怡 张智勇

（华南理工大学电子商务系，广东 广州 510006）

一、引言

中国快递物流行业市场规模随着产业的优化调整而不断扩大，全国快递业务量从2016年的312.8亿件增长到2020年的833.6亿件，年均复合增长率高达27.8%。随着快件量爆炸式增长，快递物流公司往往在一个城市内租用多个配送中心，以争取更高的配送效率。现实中，以运输业务为主的公司由于配送中心重型设备功能和分拣流程的差异，同一公司管理下的不同配送中心只能中转、分拨不同类别的产品，但下游客户可能同时需要几种产品。许多企业出于管理方便的考虑，各配送中心单独组织配送，互不共享资源，只追求局部最优而非全局最优。在这种情况下，如何打破多个配送中心间的资源壁垒，盘活公司运输和客户资源，允许货车合并订单、中途到其他配送中心取货，是帮助公司减少资源浪费的同时降低运输成本的关键。

上述问题属于多中心车辆路径问题（MDVRP， Multi-depot Vehicle Routing Problem）的引申，国内外学者对MDVRP进行了研究。郎茂祥[1]较早研究了MDVRP，采用最近距离分配法将多配送中心问题分解单配送中心问题。Yang[2]利用混合遗传算法研究了带时间窗的多种环境车辆类型的多目标VRP。Li[3]等研究了封闭式多中心的同时取送货问题。杨翔[4]设计了虚拟配送中心的编码方法辅助求解MDVRP。范厚明[5]构建了两阶段优化模型，求解了多中心联合配送模式下集货需求随机的VRP。另外，一些公司实际上并不关心车辆是否必须全部回到原配送中心，尤其是当物流活动外包给第三方车辆配送时。这类问题属于半开放式的车辆路径问题，Bae[6]、Jian Li[7]、刘家利[8]、马冰山[9]等对相关问题进行了研究，论证了非封闭式的方案能节省车辆运输成本和使用成本。

多配送中心车辆路径问题的相关讨论已非常广泛，但现阶段极少文献对多配送中心联合配送下，车辆行驶中途到其他配送中心取货、合并客户需求订单这方面有研究，因此本文针对该情况下的联合配送问题进行研究。

二、问题描述

本文研究的是，多个配送中心可共享车辆、车场及客户资源，使用多车型的异质车辆完成配送的联合配送模式。本文还考虑配送中心的功能限制，各中心所处理产品类型不同，允许车辆中途取货以合并配送订单。因此，本文要解决的是半开放式、带时间窗、考虑配送中心资源共享的多中心车辆路径 问 题（MDVRPSDR，Multi-depot VRP under Shared Depot Resources）。

图1是简化的问题示意图，假设原方案由2个配送中心（A、B）和6个客户组成，配送中心配备有成本结构不同的自有车和外租车，各配送中心（下称“DC”）独立配送。三角形表示配送中心，其中A只提供A’产品，B只提供B’产品。圆为客户，圆内左边数字是客户对A’的需求，右边数字是客户对B’的需求。原方案中，一共使用了3辆自有车（1、3、4）和1辆外租车（2），货车配送完毕后需回到起始DC。

图1 优化前后对比图

当配送方案从独立模式优化为共享模式时：①路径2和3优化为路径6，车从A携带6单位A’出发，到达B处后取9单位B’，再依次向b、c配送，由此减少启用一台车。②路径4优化为路径7，由封闭性优化为开放性。③DC开放车场供任意车辆停靠，路径1优化为路径5，车辆从a直接回到更近的B，减少行驶距离。④优化各路径所使用的车辆性质，使得运输成本更低。

三、模型建立

设某公司有DC，各DC只存储一种产品，且产品互异，所有DC要服务一群客户，满足以下假设：

①一个客户可能只需要一种产品，或同时需要多种产品。②每个客户最多只能被一辆车访问。③每个客户的某种产品需求只由一辆车服务。④车辆的最大容量与车型有关，由于城区配送路程有限，不考虑车辆最大行驶距离的限制。⑤客户处对可容纳的车型有限制，车型过大时会造成卸货拥堵，产生超限惩罚成本。⑥自有车在结束配送后必须回到任一DC停靠，外租车则直接离开，不需要考虑返程。

若以配送总成本最小为目标函数，基于以上假设和定义，可建立以下数学模型：

上述函数式中，（1）式为目标函数，即车辆启用成本、可变运输成本、违反时间窗惩罚成本、超限成本之和最小。（2）表示一个客户只被访问一次。（3）表示车辆在一次运输中可以配送一种或多种产品。（4）表示车辆进出平衡。（5）规定两个DC之间最多可以直接互通一次。（6）表示载重约束和客户处可容纳车型的限制。（7）表示每个客户的每种产品只由一辆车提供服务。（8）指满足客户的所有需求。（9）为初始载重量。（10）确保没有子回路。（11）表示自有车可从任意DC出发，空车回到任意DC。（12）为早到等待时间。（13）表明车辆按顺序访问路径中的点。（14）表明变量之间的关系。（15）为超限惩罚成本。（16）～（19）为决策变量。

四、算法设计

本文选择模拟退火算法与遗传算法混合使用，SA有局部搜索能力强的优点，但全局搜索能力差，容易受参数的影响，而GA能有效跳出局部最优的优点，缺点是受初始解影响较大。因此本文结合海明距离过滤机制，设计混合模拟退火-改进自适应遗传算法（SA-AGA），以SA的最优解为AGA的初始解，并设计自适应算子与过滤机制，避免AGA陷入局部最优，解决算法的缺陷问题。

1.编解码方式及初始化种群

染色体采用连续自然数编码，利用虚拟DC编码方式来决定路径。从1开始，取n+m-1个连续不重复的自然数作为编码的表示，1～n为客户编号，n+1～n+m-1为虚拟DC的编号，虚拟DC之间的距离为0。解码分为三个阶段：一阶段将个体解码为子路径；二阶段根据就近原则和客户需求将DC插入到子路径的首、尾、中途；三阶段为子路径选定用车方案。

在初始化种群方面，以随机法生成SA的初始解，再利用SA生成最优解，将其复制NIND次作为AGA的初代种群。SA具体步骤为：种群初始化；能量值计算；同一温度层内随机扰动MaxInIter次；按Metropolis准则接受新解；依照冷却因子α来更新温度Tn，继续下一个温度层的随机扰动，直到完成降温次数MaxOutIter次。

为便于理解，假设有3个DC（A， B， C）和10个客户（1，2，...，10），用11、12、13表示虚拟DC，表示最多使用4台车，共有3种产品A’、B’、C’，分别存放在配送中心A、B、C。

（1）第一阶段解码

以虚拟DC为分割点划分路径，若虚拟DC的编码位置相邻，则它们之间无路径。例如编码为{7， 2， 13， 3， 6， 1， 5， 9，4， 12， 11， 8， 10}时，解出3条路径{7， 2}，{3， 6， 1， 5， 9，4}，{8， 10}。

（2）第二阶段解码

对一阶段解码得出的子路径的配送方案进行“匹配首尾DC、中间插入DC”的操作。以上述第一阶段的第二个路径{3， 6，1， 5， 9， 4}的解码过程为例，为便于理解，各客户的需求用0和1表示，如图2所示。先判断结尾客户4离C最近，则选定C为终点，接着决定起点和中途取货的DC。根据路径上客户对的需求种类不同，有以下三种可能。

一是路径中的客户共有一种需求。无需中途取货，计算子路径的需求量总和，派出1辆容量大于等于需求量总和且限载尽可能小的车完成运输，起点为存放该种需求产品的配送中心。

二是路径中的客户共有两种需求。先计算需要多大容量的车，再分析如何中途取货。如图2，客户对A’、B’产品有需求，因此A、B均可为起点，选定起点后再中途插入其他DC。若选A作起点，对非起点DC对应的需求找到首个“需求非0位置”，即客户7前的位置，把B插入到7前的任意位置。最后对比所有插入方案的路径长度，择更短者为解码结果。

图2 两种需求时的二阶段解码示意图

三是路径中的客户共有三种需求。选择车辆容量和插入DC的思路与（1）和（2）相似。

（3）第三阶段解码

处理第二阶段的解码结果，决策各子路径使用自有车还是外租车。根据车辆成本信息，以当前路径的运输成本最低为原则来抉择车辆性质。

2.适应度函数

利用目标函数式（1）构建适应度函数，如下式。

3.选择操作

结合最佳精英选择法和轮盘赌法，先将适应度最大的前20%的精英个体直接复制到子代，其余个体按轮盘赌方法进行选择。

4.交叉和变异

对被选中的染色体以概率pc进行OX交叉操作，再以概率pm将该染色体上随机两个位置的基因对换。安海[10]在线性自适应遗传算子和非线性自适应遗传算子的基础上，使用了曲线底部比余弦函数更平滑的sigmoid函数来构造遗传算子。该文献经算例分析，证明提出的算子在求解时有收敛速度更快、结果更准确的优点，因此本文使用该遗传算子，如式（21）～（22）所示。fmax为当前种群的适应度最大值；favg为当前种群的适应度平均值；fb为要进行交叉的个体中适应度更大一方的适应度值；fm为要变异个体的适应度值；pmmax、pmmin为最大、最小变异概率，pcmax、pcmin为最大、最小交叉概率；经作者论证，A为9.903438。

5.海明距离过滤机制

本文设置海明距离（指两个个体的基因排列差异位数）过滤机制，从第二代开始执行该机制，直到最大迭代次数。目的是在选择操作前，滤掉相似度过高的个体，以保证个体多样性。设置适应度差值门槛D和海明距离阈值Ham_dis：D用于判断个体间的适应度值差异大小，Ham_dis用于判断个体间编码相似程度。对每一代执行过滤机制的具体步骤如下：

图3 海明距离过滤机制流程图

6.终止机制

进化代数达到最大代数限制Maxgen时，算法终止。

五、实例分析

本文以广州市某专注于快递业务的A公司为例，使用调研样本数据进行算例分析，通过对比各配送中心独立配送和多中心联合配送两种模式，评价联合模式下资源共享方案的有效性。

1.算例描述

已知广州市某A公司有3个一级配送中心（J、H、L），三者中转的产品各不相同，分别为函件类普通包裹、电商快递包裹、高时效要求的标准快件（以下用P、D、B指代三种包裹）。全市配送网共有88个客户，各客户的位置用经纬度表示。88个客户的日均需求量如表1所示。由于各客户的卸货场地大小不同，均有最大可入车型的限制Ti（3t、5t、8t）。车辆相关信息如下：车辆的日均运输成本包括固定启用成本和变动成本（如燃油、保养维护等）；单次卸货时间与车辆吨位大小成正相关，3t、5t、8t货车分别对应20min、30min、40min；所有车辆的行驶平均速度Vk=30km/h；车辆满载时按每吨500件计算，装载率=（本车配送件数/本车满载件数）×100%。

表1 客户信息（部分）

A公司原有配送方案是3个DC独立安排配送，起点、终点为同一个DC，无中途取货。部分客户会被重复访问，客户需要腾出多次接货时间，车辆平均装载率不高。因此，基于同样的需求和车辆，A公司可组织联合配送，本文用SA-AGA求解联合配送下的优化方案。

2.结果分析

图4 最优路径图

求解结果显示：独立配送方案启用了6辆3t车、7辆5t车、13辆8t车，其中外租车15辆；联合配送方案启用了20辆3t车、4辆5t车、2辆8t车，其中外租车17辆。使用相同算法对独立配送模式求解，将其与联合配送模式对比。优化后的部分路径安排如表2所示，优化前后的配送方案效果对比如表3所示。

表2 联合配送下的路径安排（部分）

表3 优化前后的成本与装载率对比

由表2、表3可知，当在联合配送模式下，整体所启用的车辆总数减少，配送总里程从1769.9千米降至1615.4千米，下降了8.7%，平均装载率从84.9%上升到87.8%，违反时间窗与限重的总次数更少。因此，多中心共享运输资源和客户资源、允许中途取货的联合配送模式，比独立配送模式有更好的效果与效益。

六、结语

本文建立了多配送中心资源共享、多产品、半开放式、异质车辆的车辆路径优化模型，并设计混合模拟退火-改进自适应遗传算法，使用了三阶段解码法和过滤机制克服经典算法的缺点。通过A公司的实例分析验证了多中心联合配送的可行性，为三个配送中心确定了要使用的车辆和要服务的下游需求点，并将其与各中心独立配送的模式作对比，结果表明：允许中途取货、合并需求的联合配送模式和独立配送模式相比，前者使用的车辆总数更少，车辆平均装载率更高，总配送成本更低。