基于客户分流策略的电商促销下车辆路径问题研究

吕俊杰 冯 谦

(北京工商大学商学院 北京 100048)

0 引 言

近年来电子商务在中国迅速崛起，各电商企业为了吸引客户竞相开展促销活动，使客户的需求发生井喷式增长，这对电商的线下物流配送活动提出了巨大的挑战。即使电商物流部门全负荷工作，仍然有很多商品无法按时送到，影响客户的购物体验。物流配送效率直接影响客户对电商促销活动的满意程度，因此如何优化配送路线既能有效控制成本增加又能满足客户的时间要求，已经成为电商促销下物流服务亟需解决的重要问题。

现有国内外文献对电商配送路径优化问题主要从成本或时间这两个角度展开研究。如Prins[1]研究了以最小行驶路径成本为目标的多车型车辆路径问题；Kown等[2]研究了不同车型排放量同类型车辆排放成本的车辆路径问题；马秋卓等[3]以最小化碳排放成本为目标，探讨了市区小范围配送网络内最优车辆路径问题决策；Lin Zhou等[4]以最小化运输成本为目标，研究了最后一公里客户不同收货方式的车辆路径问题；符卓等[5]研究了以成本为目标的客户需求可按商品拆分的车辆路径问题；李妍峰等[6]研究了最小化车辆行驶时间为目标的动态网络车辆路径派送问题；王旭坪等[7]以最小化总时间为目标，研究了拣选与配送联合调度问题。刘家利等[8]以系统车辆总成本为目标，研究了一种具有多个配送中心、存在车辆租赁、有时间窗限制的开环车辆路径问题；王旭坪等[9]以最大客户满意度为目标，研究了模糊时间窗下的车辆路径问题；张源凯等[10]以最小化运输成本为目标研究了一地多仓环境下商品分配和配送联合优化问题；陈萍等[11]以最大化客户时间满意度为目标，研究了一类外卖配送模型。

上述研究可以规划出特定情境下的最佳行驶路径，但综合分析，上述研究不适用于需求井喷情况下的配送路径问题，研究内容仍有局限性。电商配送服务需要满足客户的时间要求，不能以节省自身成本为目标，但同时电商促销时客户的商品需求量急剧增加，配送服务无法满足所有客户的时间要求。因此，针对电商促销时客户时间敏感性不同的特点，本文将客户分为时间敏感型和时间延迟型两类，把集中的配送需求分散化，既能满足敏感型客户对配送时间的要求，又能控制总成本的增加。同时，构建了井喷需求场景的多周期多车程车辆路径优化模型，并通过数值实验与最小成本、最短时间目标路径模型进行对比。

1 问题描述与模型建立

1.1 问题描述

本文问题可以用图G=(N,A)描述，其中N表示节点的集合，i或j表示节点编号，包括1个配送中心和n-1个末端网点，A={(i,j|i∈N,j∈N)} 为弧的集合。用K表示配送中心的车辆集合，在一定周期内配送完Q个商品。在单位周期的工作时间Dk内车辆多次往返配送中心和网点之间，用T表示周期数，h表示车辆配送车次，用sikhT表示在第T个单位周期内车辆k第h次配送过程到达节点i的时间，在第一个单位周期内车辆k第一次从配送中心出发的时间sik11=0；tij表示从网点i到j的行驶时间。车辆不允许超载，最大载量均为q。单位周期内车辆加班时间为tkT，单位时间加班成本为ck，末端网点i的商品单数为Qi，gikhT表示在第T个单位周期内车辆k第h次配送到网点i的商品数量。

决策变量：

xijkhT：第T个周期内车辆k第h次配送从网点i行驶至j时为1，否则为0；

yikhT：第T个周期内点i的商品配送任务由车辆k第h次配送时完成为1，否则为0。

1.2 数学模型

本文提出一种客户分流策略并建立多周期多车程车辆路径优化模型，同时建立以最小成本和最短时间为目标的多周期多车程车辆路径优化模型进行对比，下面展开介绍三种模型的构造过程。

客户分流策略根据客户时间敏感度的不同，将客户分为时间敏感型和时间延迟型。时间敏感型客户对配送时间要求高，电商物流配送服务必须在其期望时间范围内完成商品配送；时间延迟型客户愿意接受超出一定时间范围的延迟配送服务，因此需要对其给予一定程度的补偿。如图1所示，车辆优先配送三个有敏感型客户商品的网点，然后再配送其余只有延迟型客户商品的网点。

图1 客户分流策略下单位周期内车辆k配送示意图

其中将所有节点集合N分为0、N+和N-三个部分，0代表配送中心，N+代表网点(敏感型客户)，N-代表网点(延迟型客户)，车辆单位距离运输成本为cij，延迟配送商品的单位补偿成本为b，末端网点i需要的商品商品数为Qi。

根据以上问题的描述和界定，客户分流策略的车辆路径优化模型建立如下：

(1)

(2)

式(2)表示单位周期T内配送中心单次出发车辆数至多有K辆。

(3)

式(3)表示车辆不允许超载。

(4)

式(4)表示车辆每次从配送中心出发并返回配送中心。

(5)

式(5)表示所有网点商品都被配送。

∀k∈K,T=1,2，…

(6)

式(6)表示某一车辆驶出点必是该车辆驶入点。

(7)

式(7)表示单位周期T内车辆k第h次和第h-1次配送行驶时间的连续性。

(8)

式(8)表示单位周期T内车辆第h次配送到末端网点j的时间。

先说学术权力行政化。我国社会的“官本位”意识浓厚，这种“官本位”观念也渗透到了高校的学术管理中，影响到了学术管理中的行政权力的正当行使。在学术管理中，许多行政人员唯官是从，习惯于按照官的指示办事，而很少考虑学术发展的客观规律。随之而来的是服务意识淡薄，行政人员自身定位不准，对学术管理中学术人员应有的主体地位和学术权力的主导地位认识有限，服务不到位。各种委员会的设置缺乏明确的章程，任务不明，职责不清，这说明我国许多高校的学术机构在人员构成上具有明显的行政化倾向。

s0khT+UkM≤Dk∀h∈H,∀k∈K,T=1,2,…

(9)

(10)

式(9)和式(10)表示车辆k单位周期工作时间限制，若第h+1次配送时间超出工作时间限制，则第h次配送回到配送中心后停止工作。

∀i∈N+,∀h∈H,∀k∈K

(11)

式(11)表示时间敏感型客户的商品要求在一定时间内送至末端网点。

sjkhT≤sikhT∀i∈N-,∀j∈N+,∀h∈H,∀k∈K

(12)

式(12)表示时间敏感型客户商品配送结束后开始送延迟型客户的商品。

为了对比客户分流策略下配送时效性，本文构建常规配送方式下以最小成本为目标的车辆路径模型，如图2所示该车辆路径模型选择的是路径成本最低的配送方案，网点间的配送顺序没有优先级。

图2 最小成本策略下单位周期内车辆k配送示意图

故最小成本目标的车辆路径模型目标函数为：

(13)

式(13)计算了所有周期内全部车辆的运输成本之和，该模型的约束条件取式(2)-式(10)。

图3 最短时间策略下单位周期内车辆k配送示意图

Tdeadline为所有客户允许的最晚收货周期，在Tdeadline结束前电商物流部门必须将商品全部送达，最短时间目标的车辆路径优化模型目标函数为：

(14)

该模型约束条件取式(2)-式(8)，并在此基础上增加如下约束：

s0khT+UkM≤Dk+tkT∀h∈H,∀k∈K,T=1,2,…

(15)

(16)

∀j∈N,∀h∈H,∀k∈K

(17)

式(14)为模型的成本目标函数，计算了所有周期内所有车辆运输成本和加班成本的和；式(15)和式(16)表示每天车辆工作时间限制, 当车辆k第h+1次配送时间超出当天工作时间，则在第h次配送结束回到配送中心后停止工作；式(17)表示最后一个回到配送中心的车辆所花费的所有时间不超过Tdeadline与单位周期内总的工作时间Dk+tkT的积。

2 改进的遗传算法

根据上文可知，该问题是多车程的车辆路径优化问题，属于NP难问题，适合使用启发式算法求解。在各类启发式算法中，遗传算法的优点是有很强的鲁棒性和全局搜索能力，适合求解复杂多极值优化和组合问题。

目前遗传算法主要有基于行驶路径编码方式和基于需求点编码方式两种，这两种编码方式只适合单次车程的车辆路径优化。根据研究问题中车辆多次从配送中心出发并返回的特点，而且存在时间敏感型客户商品和时间延迟型客户商品的区分，本文提出一种新的染色体表示方式——基于车辆和需求点分类的混合编码方式。

2.1 染色体编码和种群初始化

将所有节点编为一条大的TSP路径进行编码，在网点编码后加入配送中心编码，然后在所有节点编码后加入车辆编码，用于切割大TSP路径。用配送中心编码、末端网点编码和车辆编码三部分构成每条染色体。其中客户分流策略中，编码构成为配送中心编码+网点(敏感型客户)编码+网点(延迟型客户)编码+配送中心编码+车辆编码，表示为：(1) 网点(敏感型客户)编码1，2，…，N1；网点(延迟型客户)编码N1+1,N1+2,…，N；配送中心编码为0。(2) 车辆编码N+1，N+2，…，N+K。旅行商路径切割流程如下：

步骤1：按节点编码顺序从左到右累计网点编码，直到超过车辆负载q的前一个编码，将这些网点加入到第一辆车辆行驶计划中，依次类推直到所有车辆都有任务。

步骤2：若有剩余末端网点没有分配到车辆行驶计划中，则重复步骤1，直到所有末端网点编码都有对应的车辆编码。

2.2 适应度函数和选择操作

适应度用于评价每个配送方案的优劣程度，每个配送方案可以用一个染色体来表示，染色体适应度越大，该方案被选择的几率也越大。

令目标函数倒数为适应度函数，zi表示第i条染色体对应的目标函数，该染色体的适应度为fi=1/zi。判断染色体是否满足约束条件，满足则保留，反之则舍弃；将适应度fi≥favg的染色体保留到子代；对全部染色体进行交叉和变异操作，按适应度大小再选出N-L条染色体，与保留的L条染色体组合构成下一代种群。

2.3 交叉和变异操作

每代种群个体以交叉概率交叉重组，pc表示染色体个体i1和i2的交叉概率，pavg表示基础概率，pmax表示适应度值大于平均值的染色体个体交叉概率，f表示i1和i2中适应度值大的个体适应度值，favg表示平均适应度值，fmax表示最大适应度值。交叉概率公示为：

采用两点交叉算法，随机在染色体个体编码串中设置了两个交叉点，两点之间区域为匹配区域，并在[0，1]之间产生一个随机数r，若pc≥r，则进行交换部分基因，否则不交叉。其中，客户分流配送策略编码的两条染色体在交叉区域的基因位对应可能存在下列三种情形(见图4)，分别为：对应基因位为“网点(敏感型客户)编码-网点(延迟型客户)编码”，如交叉区域[A,E]、[D,B],此时不进行交叉；对应基因位为“网点(敏感型客户)编码/网点(延迟型客户)编码-车辆编码”，如交叉区域[A,F]、[B,F]、[D,C]、[E,C],此时也不能进行交叉；对应基因位为“网点(敏感型客户)编码-网点(敏感型客户)编码”、“网点(延迟型客户)编码-网点(延迟型客户)编码”、“车辆编码-车辆编码”，如交叉区域[A,D]、[B,E]、[C,F],此时采用部分匹配交叉的方式进行交叉。

图4 交叉区域基因位对应情形图

变异概率是染色体中某些基因改变的概率，pm表示染色体个体的变异概率，pmavg表示基础变异概率，pmmax表示适应度值大于平均值个体所采用的变异概率，fm表示个体i1的适应度值，fmavg表示平均适应度值，fmmax表示染色体个体中最大适应度值。变异概率的公式为：

在[0，1]之间产生一个随机数e，若pm

最后检查交叉和变异产生的染色体是否满足约束条件，不满足则舍弃，反之则保留。

2.4 控制参数以及确定循环终止条件

控制参数的选取不同，遗传算法的收敛性就会有所改变，这些控制参数主要有种群的大小、终止代数、变异概率、交叉概率等。判断是否达到停止进化条件，如达到代数要求，则停止迭代，否则继续迭代。 本文设置最大进化代数作为判断算法终止条件，当算法迭代到MAX代时计算终止，此时选择适应度值最大的染色体对应的路径集合作为最优解。

2.5 算法性能分析

为了验证本文改进的遗传算法的有效性和优越性，针对Solomn算例库中RC110算例分别采用基本遗传算法和改进的遗传算法模拟仿真求解10次进行比较，10次运算的平均结果如表1所示。

表1 算法运行性能比较

由表1可以看出，针对求解多车程多周期车辆路径问题，改进遗传算法在收敛最优解次数和计算时间方面均优于基本遗传算法，显示出良好的稳定性和寻优性能，同时在计算效率方面也有所提升。

本文设计的改进遗传算法与基本遗传算法的迭代收敛情况比较如图5所示，图中虚线显示了基本遗传算法求解过程的收敛情况，实线显示了改进遗传算法求解过程的收敛情况。由图5可知，改进遗传算法具有更好的收敛性。

图5 两种遗传算法的迭代收敛图

3 实验结果与分析

本文以Solomn算例库中20个算例数据为基础进行扩建，构建1个配送中心与100个网点的电商促销下商品配送的算例并进行仿真实验，最后比较三种策略在成本和配送时效性方面的优化结果。

3.1 算例构建

配送中心有待处理商品60 000单，拥有10辆车载能力为500单的货车，单位距离运输成本1元，单位周期是1天，车辆单位周期工作时间为12 h。最短时间目标下车辆加班时间为6 h，加班成本为25元/h，要求48小时内配送完商品。客户分流策略下随机选取时间敏感型客户商品16 413单，延迟型客户商品43 587单，延迟型客户商品每单补偿0.1元。

本文实验数据中设置1个配送中心(用坐标源点表示配送中心，序号为0)和100个末端网点，本文限于篇幅，仅展示100个网点中前20个网点的数据，如表2所示，其中X、Y表示网点坐标，R表示各网点商品的总需求量。

表2 测试算例相关数据信息

3.2 实验结果

结合算例规模，设定算法参数如下：种群规模为100，迭代次数为200次，交叉概率Px=0.7，变异概率Pm=0.05。使用MATLABR2014a运行遗传算法。

实验结果显示，以最小成本为目标的常规配送模式总成本为36 038.66元。该实验数据包括10辆车4天内的行驶路径，限于篇幅本文展示其中部分车辆的路径情况(下文模型路径结果也只进行部分展示)，如表3所示。

表3 最小成本配送策略的部分车辆路径安排

以最短时间为目标的常规配送模式总成本为46 523.39元，部分车辆路径安排情况如表4所示。

表4 最短时间配送策略下部分车辆路径安排

客户分流配送策略下总成本为41 550.23元。该策略下部分车辆路径安排情况如表5所示。其中车辆在第四天完成所有配送任务，超出最晚配送周期2天，但车辆在敏感型客户允许的最晚配送周期前完成对其的配送任务，如车辆1在第2天完成所有敏感型客户商品的配送任务，车辆2在第一天完成所有敏感型客户商品的配送任务。

表5 客户分流策略下部分车辆路径安排

为了分析三种配送模型在成本与时效性方面的优劣性，本文比较了它们的最优解，结果如表6和表7所示。

表6 实验结果对比分析

表7 三种策略成本对比分析

从表6中可以看出，客户分流策略总成本比最短时间配送模式总成本减少4 973.16元，减少约10.7%，但满足时效性的商品比例与最短时间配送模式相同为100%。客户分流策略总成本比最小成本目标总成本增加5 511.57元，增加了约15.3%，但满足时效性的商品比例比最小成本配送模式增加了36.7%。

由表7可知，客户分流策略与最短时间配送模式相比，运输成本减少量约占总成本减少量的84.5%；客户分流策略与最小成本配送模式相比，运输成本增加量约占总成本增加量的50.5%；客户分流策略的补偿成本与最短时间配送模式的加班成本相比减少约22%。

可以看出，与最短时间配送模式相比，客户分流策略按照客户商品优先级配送，把集中的配送需求分散化，减少了单位周期内车辆的工作时间和配送车次，从而减少运输成本，节约加班成本。并且，客户分流策略可以根据节省的加班成本给予时间偿延迟型客户一定程度的补偿，这样既能使敏感型客户商品的时效满足率达到100%，同时也尽可能地减少延迟型客户的抱怨，降低退货的概率。与最小成本配送模式相比，客户分流策略提高了满足时效性的商品比例，并有效控制了成本的增幅。

4 结 语

本文考虑成本和客户时间敏感度对配送过程的影响，基于客户分流配送策略，建立了更加符合大规模需求场景的多周期多车程车辆路径优化模型，通过算例验证了三种配送方式的优缺点。未来,在本文的基础上，可以进一步深化研究的方向有需求井喷场景下多车场多车型的配送问题，还可以通过加入不同货物交付方式，结合配送中心到网点的配送环节进行联合优化。