半柔性覆盖的多配送中心路线优化问题研究

张晓楠，姜 帅，南婧雯

陕西科技大学 机电工程学院，西安710021

在区域经济一体化和互联网的背景下，电商物流配送迅猛发展[1]。其特点在于：（1）直接面对需求量小、品种丰富、位置分散的众多客户，电商物流系统复杂且成本高[2]；（2）客户需求受季节、天气、节假日、促销手段、产品生命周期等因素影响呈现动态波动，甚至出现突发性暴涨（“双十一”“618”），面对这类扰动，配送网络各站点资源无法准确平衡，易发生产品爆仓、滞缓等现象，风险抵抗力差[3-5]。

在电商物流末端配送决策中，尽管配送需求全年波动，但是对于每一次的配送业务来说，因配送需求由客户网上订单生成，理论上，决策者可每天针对当天需求量规划路线以获得较优的配送方案。然而，现实中，每天重新规划配送路线可能导致管理复杂，司机对新路线不熟悉，客户对司机不熟悉等一系列问题。为简化管理，保证配送司机对服务路线和服务客户的熟悉度，现有物流运营商仍旧采用“行政区域划分”“分区配送”或“定点服务”的配送策略。事实上，“行政区域划分策略”要求配送中心和配送站的服务范围几乎与行政区域划分相一致，可能导致站点/车辆间的服务范围划分不合理，成本浪费严重；“分区配送策略”虽开放了行政区域划分，但仍严格要求每个需求点只隶属于唯一的一个配送站，每个配送站只隶属于唯一的一个配送中心，事实上，某些地区可能同时存在于多个配送中心的服务半径内，存在由多个配送中心为其服务的可能；“定点服务策略”要求配送站为司机划分的服务范围是固定不变的，一个司机总是每天服务固定客户点。上述三种规则模式下配送路线与当天配送量无关，当需求动态波动时，各站点/车辆业务量的不均衡性波动明显，甚至当出现“双十一”“618”的需求爆涨时，覆盖需求频繁度高的配送站容易爆仓，配送车辆供不应求，而覆盖需求频繁度低的配送站资源过剩。为此，在保持一定程度的系统稳定性的基础上，开放这些规则策略，或许可提高配送效率和网络风险抵抗力[6]。

基于此，为应对“双十一”“618”需求突发性爆涨下物流配送网络的爆仓、滞缓等问题，本文尝试在保持配送系统稳定性的基础上提出“半柔性覆盖策略”，研究“半柔性覆盖的多配送中心路线优化问题”（Μulti-depots Vehicle Routing Problem with Semi-flexible Service，ΜVRP-SFS）。即根据地理位置，区分固定需求点和柔性需求点，定义柔性需求点可由多个配送站协同服务，建立半柔性覆盖的多配送中心路线优化模型；设计遗传算法进行求解，使用Μatlab 进行编译；以申通快递在西安北郊地区的5 个配送站点为例进行实例测试，对比“半柔性覆盖策略”的求解结果与原始路线、“全柔性覆盖策略”和“固定分区策略”的求解结果，验证“半柔性覆盖策略”的有效性。

1 国内外相关文献

目前，已有研究大多是结合电子商务环境下物流配送业务特征展开研究，如刘必争等[7]认为传统选址模型中假设“物流设施到客户的配送是放射线状”已经不适用于B2C 物流配送模式，必须考虑车辆的巡回访问特性，并建立带软时间窗的选址-路线集成模型（Location Routing Problem with Soft Time Windows，LRPSTW），结合遗传算法和退火算法求解；段凤华等[8]针对电商配送客户多、分布广、品种多、批量小的特点，以及配送业务的车辆巡回访问特性，建立了物流配送的基本VRP（Vehicle Routing Problem）模型，设计了禁忌搜索算法求解；付朝晖等[9]针对生鲜电商配送的“最后一公里”难题，开放车辆必须返回配送中心的规则，研究生鲜电商配送的开放式时变车辆路径问题；李琳等[10]考虑订单的配送时间和时效性要求，建立订单配送路线优化模型，设计改进禁忌搜索算法进行求解，之后，李琳等[11]又在2011年提出充分利用订单未来信息，改进了订单配送路线优化模型，并设计两阶段启发式算法求解；Du等[12]考虑客户需求的动态波动特征，研究了动态需求的车辆动态调度问题，并设计了一个模拟系统来仿真该过程；Zhang 等[13]考虑订单的紧急度等特征，集成订单处理和配送车辆调度问题，建立订单处理和车辆调度集成模型，并比较了多种算法的求解结果；Naccache 等[14]提出供应商直配模式，研究了供应商直接为电商客户配送的drop-ship配送路线问题，并以最小化运出成本为目标函数建立优化模型。此外，韩珣[15]、辜勇[16]、贺韵竹[17]等针对常规环境下的配送路线优化问题提出了合作覆盖和协同配送策略。然而，韩珣等[15]研究考虑合作覆盖的多级自提点选址问题，其协同体现在客户可前往任意自提点取货；辜勇等[16]研究带时间窗的多中心半开放式车辆路径问题，其协同配送体现在要求车辆完成任务后从客户处返回任意配送中心；贺韵竹等[17]研究自营货车与公交车协同快件配送优化问题，其协同体现在自营车和公交车的协同换乘上。

与本文关注点不同，本文考虑现实中某些地区可能同时存在于多个配送站的服务半径内，存在由多个配送中心为其服务的可能，通过借鉴这一可能来平衡站点资源，提高系统应对需求暴增的风险抵抗力。

2 半柔性覆盖的多配送中心路线优化模型

2.1 问题描述

半柔性覆盖的多配送中心路线优化问题（ΜVRPSFS）可以描述为：配送网络中存在多个配送中心为多个客户进行服务，配送站集合为D={p|p=1,2,…,P}，客户集合为S={r|r=1,2,…,R}，其中S=S1⋃S2,S1为柔性需求点客户，S2为固定需求点客户，所有点集合U=D ⋃S，车辆集合为V={k|k=1,2,…,M}。对于每个配送站p 而言，其固定客户集合为S2(p),柔性客户集合为S1(p),S2={S2(p)|p=1,2,…,P},S1={S1(1)⋃S1(2)⋃…⋃S1(P)}。目的是在每天开展配送任务时，根据当天任务，以配送成本最小为目标，规划出一条合适的配送方案，以满足所有客户点需求。与常规配送优化问题（VRP）不同的是：因将客户区分为固定需求点和柔性需求点，柔性客户在优化过程中可由其覆盖的多个协同配送中心的任意配送中心进行服务，而固定客户只能由按“固定分区策略”规划的所属配送站进行服务。图1 是问题示意图，图中两个矩形框代表不同配送期，灰色填充点为柔性需求点。在“半柔性覆盖策略”下，可以兼顾系统稳定性和配送效率，同时平衡多配送站剩余资源。

图1 半柔性覆盖的多配送中心路线优化问题示意图

其余变量如下：Dp为配送中心p 的存储量；dr为客户r 的需求量；Qk是车辆k 的容量；cij是点i 至点j的行驶距离；Fk是车辆k 的使用成本；Fu是单位距离行驶成本。

决策变量为：

2.2 模型建立

为建立模型，做了如下假设：

（1）配送中心与客户点地理位置均已知；

（2）存在多个配送中心且其服务能力满足客户需求；

（3）从配送中心到客户以及客户之间的距离均已知；

（4）车辆统一，且容量已知，并且在配送过程中不得超过其额定载重量；

（5）每个客户有且仅有一辆车为其服务；

（6）客户对货物的需求量或者同一子路径上的所有客户需求量之和不超过车辆的容量。建立模型如下：

式（1）为目标函数，表示总成本最小；式（2）表示每个配送中心容量大于客户的总需求量；式（3）表示每个客户由一个配送中心配送；式（4）表示每个配送中心服务的需求量之和不大于运力；式（5）表示客户的需求量小于车容量；式（6）表示每辆车路线上客户需求量之和小于车容量；式（7）表示每个配送中心有可支配车辆；式（8）表示每个客户仅被服务一次；式（9）表示进入某节点的车须从该节点离开；式（10）表示每辆车分配给一个配送中心；式（11）表示分配给配送中心的固定客户不变；式（12）表示灵活分配的客户可由多个配送中心配送。

3 遗传算法设计

本文采用改进遗传算法求解ΜVRP-SFS模型。

（1）染色体编码

本文包含两个决策：一是决定客户服务顺序；二是决定柔性需求点的配送站分配。基于此，本文采用两行整数编码对服务顺序和所属配送站进行并行编码。令顺序编码为X ，配送站分配编码为Y 。需要说明的是，固定需求点配送站分配总是固定不变。解码方法结合编码和最大车容量划分车辆服务对象以生成配送路径。

图2 是包含3 个配送站和10 个客户的并行编码例子，3个配送站编号为1～3，10个客户编号为4～13。第一行表示客户服务顺序X ：7-8-6-5-10-4-11-9-12-13；第二行对应给出每个客户的所属配送站Y ：1-2-3-3-2-1-3-3-1-2。

图2 并行编码例子

具体解码方式为：

步骤1 根据编码得到各配送站服务对象，如配送站1 服务客户7、4、12，配送站2 服务客户8、10、13，配送站3服务客户6、5、11、9。

步骤2 结合最大车容量安排配送路径，举个例子，若配送站1 安排车辆依次服务客户7、4、9，若服务完客户4后不能服务客户12，则服务路径为1-7-4-1-12-1。

（2）初始化种群

随机选择几个未接受服务的客户点，达到某辆车的最大容载量，然后不断地重复以上步骤，直到所有的客户点都被服务，得到几个染色体。将得到的染色体分别代入模型的各个约束中，检测该染色体的可行性，如果不可行，则删除该染色体。直到所有的染色体的可行性检测完毕，所有的染色体都被生成，得到初始种群。

（3）适应度函数

适应度函数是评价每个个体的优劣与否的指标，将适应度高的个体保留下来，传到下一代，淘汰适应度低的个体。因此种群的进化程度是根据个体的适应度值来决定的。

适应度函数一般情况下是根据目标函数来决定的，并且适应度值要求是非负的。

表1 配送站坐标

本文优化目标是成本最小化，因此设置适应度函数为：

其中，Zi为染色体i 的目标函数值，n 为种群大小，目标函数值越大则适应度函数的值就越小，该个体的适应度就越小。

（4）选择算子

选择算子是将上一代个体中的适应度值较大的个体选择出来，然后对选择出来的个体进行交叉和变异。本文采用的是遗传算法中常用的方法轮盘赌来选择算子。轮盘赌选择算子就是将种群中的染色体根据其适应度值按比例分配到轮上的各个区域（对应的区域与个体的适应度值成正比），转动轮盘，轮盘停止时指针所指的个体就是要选择的个体。因此个体i 被遗传到下一代的概率为：

需要说明的是，在本文的选择算子中，将对顺序编码X（图2 中第一行）和所属站点编码Y（图2 中第二行）都分别进行选择，得到父代XSel 和YSel。

（5）交叉算子

对父代XSel 和YSel 分别采用两点交叉生成子代XSel1 和YSel1。具体为：在上一代的个体中，随机确定两个基因交叉的位置，然后将两个上一代个体的基因位进行交换，产生新的基因组。两点交叉能够保证一定会产生新的个体，保证了种群的多样性。

例如：若父代为“7-8-6-5-10-4-11-9-12-13”和“13-12-10-5-8-6-9-7-11-4”，随机产生两个数r1=4 和r2=7，则两个交叉片段为“5-10-4-11”和“5-8-6-9”，将两个交叉片段进行交换，然后根据交叉片段的映射关系合法化染色体得到两个新的个体“7-10-4-5-8-6-9-11-12-13”和“13-12-8-5-10-4-11-7-6-9”。

（6）变异算子

设计交换操作分别对子代XSel1 和YSel1 进行变异，例如，对于种群中的一个染色体XSel1“7-8-6-5-10-4-11-9-12-13”，随机选择两个变异点4和7，则将变异点的基因交换生成新的个体“7-8-6-11-10-4-5-9-12-13”。

（7）逆转进化

这里的“进化”是指逆转算子的单方向性，即只有经逆转后，适应度值有提高的才接受下来，否则逆转无效。

具体为：产生两个随机整数r1和r2，确定两个位置，将其对换位置，如r1=4 和r2=7，则“7-8-6-5-10-4-11-9-12-13”逆转后为“7-8-6-11-4-10-5-9-12-13”。

（8）算法终止条件

采用的终止条件是达到预先设定的迭代次数。

4 实例测试

4.1 实例描述

本文以申通快递在陕西省西安北郊地区的5 个配送站点为例，包括北郊一（未央区龙岗大道十八号谭家村对面）、北郊二（未央区石化大道东18 号华运停车场院内）、北郊三（未央区玄武路大明宫派出所对面）、北郊六（莲湖区自强西路217 号干鲜果批发市场）以及草滩分部。整个配送网络共计5个配送站，209个客户点，站点位置和经纬度如表1 所示，客户点位置、经纬度和需求量如表2 所示，图3 是服务区域示意图。定义位于图中的交叉区域的需求点为柔性需求点，可由其交叉的任意站点服务。

表2 客户点坐标和需求信息

图3 配送中心位置及配送范围示意

通过实地调研、公众号查询与电话咨询等方式，可获知5 个站点均采取“分区配送策略”，表3 和图4 以北郊一为例展示了服务客户-路径服务关系。另外，西安草滩分部中包含两个学校区域，这两个区域属于客户自提，这里将其剔除不考量。其他参数设置为：配送车辆选择电动三轮车，最大容载量为300，运输成本为6，发车成本为150，车辆使用成本Fk=150，行驶距离cij直接采用经纬度带入式（15）计算并四舍五入得到。

图4 西安北郊一线路1的实际路线

为展示本文所提出的“半柔性覆盖策略”的特性，以两天的不同需求任务量为数据，代入对应两天配送方案（表2 中的“任务一”和“任务二”）。采用Μatlab 2016a编程，操作系统为Windows 10，电脑内存为8 GB，CPU为Intel i7-6700，主频3.40 GHz。经过实验，初始条件设置为：交叉概率0.8，变异概率0.2，种群大小100，迭代次数5 000。

4.2 求解结果

图5是本文算法的求解迭代图，可见算法搜索约在4 000 次时趋于平稳，寻找到最优值为5 406，说明该算法能稳定收敛，合理有效。

图5 进化迭代图

表4是“任务一”下“半柔性覆盖策略”的5个站点的配送路线，共计19 辆车，其中车辆1～4 属于配送站I，和现状车辆数相同；车辆5～9属于配送站II，相对于现状少了1 辆车；车辆10～13 属于配送站III，和现状车辆数相同；车辆14～16属于配送站IV，和现状车辆数相同；车辆17～19 属于配送站V，相较于现状少了1 辆车。表中边框标注改变配送站的柔性需求点，下划线标注未改变服务站的柔性需求点。表5 给出了边框柔性需求点的服务站变更详情。图6对应5个站点优化后的配送路线。

表3 申通陕西西安北郊一负责客户点概况

表4 需求任务一的求解结果

表5 柔性需求点的配送站服务改变情况

表6是“任务二”下“半柔性覆盖策略”的5个站点的配送路线，同样，表中边框标注改变配送站的柔性需求点，下划线标注未改变服务站的柔性需求点。表7进一步给出了边框柔性需求点的服务站变更详情。与表3和表4对比，可知本文所提出的“半柔性覆盖策略”是在每次配送到来时，保持“固定需求点”的服务站点不变，多配送站点协同对“柔性需求点”确定合适的服务站点，并最终求解得到符合当前配送任务的配送线路。

4.3 与其他算法的结果对比

为突出本文算法的有效性，表8 给出了“基本遗传算法”“就近分配+本文算法”和“本文算法”的求解结果对比。基本遗传算法不采用本文所设计的交换变异和逆转进化操作，而采用常规单点变异，不添加逆转进化。“就近分配+本文算法”采用就近分配将柔性需求点分配到最近配送站，采用本文算法对配送服务顺序进行优化。结果显示：本文算法求解结果优于基本遗传算法，算法改进有效；对柔性客户点的分配决策进行优化有利于提高配送效率和平衡站点资源。图7 是两种对比方法的收敛图。

4.4 与现有配送线路对比

表9 以“任务一”下的求解结果方案与现有实际配送方案对比。可见，在“任务一”下，现有实际配送成本为6 048元，需要21辆车，而本文策略优化后仅需5 406元，所需车辆减少为19 辆，成本降低10.62%，车辆数减少2辆。

4.5 与“固定分区策略”和“全柔性覆盖策略”对比

为进一步说明表9 中的成本降低是来自于路线优化还是“半柔性覆盖策略”，同时为进一步展示“半柔性覆盖策略”的特性，这里继续将需求任务一下“半柔性覆盖策略”的求解结果与“固定分区策略”（可看作“非柔性覆盖策略”）和“全柔性覆盖策略”的求解结果进行对比。“固定分区策略”指的是固定客户和服务配送站的对应关系，所有客户点仍由原属配送站进行配送，侧重于优化每个配送站的配送路线；“全柔性覆盖策略”指的是不固定客户和配送站的对应关系，客户可由任意配送站的任意配送员服务，该问题转化为传统的多中心VRP优化问题。对比结果如表10所示。

图6 5个站点的配送路线

表6 需求任务二的求解结果

表7 柔性需求点的配送站服务改变情况

表8 与其他方法的结果对比

图7 两种对比方法的收敛图

表9 与现有实际配送方案的结果对比

表10 三种策略的结果对比表

从表10中可知，在“固定分区策略”下，路径优化结果为5 580 元，车辆数为21 辆，成本较现有实际情况优化了7.74%，配送司机对服务路线和服务客户的熟悉度较高，客户服务稳定性100%；在“全柔性覆盖策略”下，路径优化结果为5 376 元，车辆数为19 辆，成本较现有实际情况优化了11.11%，但是配送司机对服务路线和服务客户的熟悉度较低，客户服务稳定性0%，可能导致管理复杂，司机对新路线不熟悉，客户对司机不熟悉等一系列问题；在“半柔性覆盖策略”下，路径优化结果为5 406元，车辆数为19辆，成本较现有实际情况优化了10.62%，客户服务稳定性80%。

综上可见，若完全看重系统稳定性（即采用“固定分区策略”），系统稳定性较好，但成本降低会损失约3.37%；若完全看重成本降低（即采用“全柔性覆盖策略”），配送效率较高，但客户稳定性将可能牺牲较大；在“半柔性覆盖策略”下，其配送效率近似“全柔性覆盖策略”的配送效率（全柔性覆盖下成本降低为11.11%，和“半柔性覆盖策略”下的成本降低的差值仅0.49 个百分点），且同时能保持80%的客户服务稳定性，综合效用较高。另外，将表9 与表8 中的“就近分配+本文算法”对比，可以看出，在“半柔性覆盖策略”下，即使仅采用最为简单的就近分配来分配这些柔性需求点，其决策效果仍旧优于“固定分区策略”的决策效果（5 538<5 580）。综上，“半柔性覆盖策略”是一种兼顾系统稳定性和成本优化的较好策略。

5 结论

本文通过区分固定需求点和柔性需求点，定义柔性需求点可由多个配送站协同服务，提出“半柔性覆盖策略”；以总成本最小为目标，建立了基于半柔性覆盖的多配送中心路线优化模型，设计了遗传算法求解，Μatlab编译；结果测试以申通快递在西安北郊地区的5个配送站点为例验证了模型、算法和“半柔性覆盖策略”的有效性。研究结果如下：（1）本文建立的模型合理有效，能够求解出半柔性覆盖的多配送中心路线优化问题的方案；（2）本文对基本遗传算法的改进合理有效；（3）本文提出的“半柔性覆盖策略”的配送效率近似“全柔性覆盖策略”的配送效率，且同时能保持80%的客户服务稳定性，综合效用较高；（4）在“半柔性覆盖策略”下，即使采用最为简单的就近分配来分配这些柔性需求点，其决策效果仍旧优于“固定分区策略”的决策效果。