基于客户分类的即时配送路径优化研究

于江霞，杜红亚，罗太波

(西安电子科技大学经济与管理学院，西安710126)

0 引 言

即时配送是按照客户随时提出的配送需求，即刻在城市内进行取送服务的物流活动.《2019年第1季度中国即时配送市场研究报告》指出，65.4%的即时配送用户会关注送达是否超时[1]，由此可见，配送的准时性已成为影响客户网购决策的关键因素.如何提高配送准时性是各企业共同面临的难题，而对客户进行精细化管理成为解决该问题的方法之一.因此，本文将客户分类考虑到配送路径优化中，以期用最小的成本提高配送准时性，为企业赢得更多潜在效益.

即时配送路径优化问题是面对电子商务同城配送业务而提出的一类时效性和准时性更强的带时间窗车辆路径问题(VRPTW)，是对车辆路径问题(VRP)的扩展.目前，VRPTW问题可以分为如下几类：软时间窗[2]、硬时间窗[3]、模糊时间窗[4]、混合时间窗[5]的车辆路径问题.由于VRP带有很多的不确定性因素，很多学者对随机需求[6]、动态需求[7]、需求可拆分[8]以及考虑交通路况[9]等的VRPTW 问题进行了研究并取得了很好的成果.近几年，在即时配送领域，有关生鲜[10]、外卖[11]和“同日达”[12-13]的配送问题受到很多学者的关注，但大多是围绕客户满意度和服务客户数的角度进行研究.综上，这些研究往往忽视了客户价值因素，事实上，为不同价值客户提供同样的配送服务很有可能会造成优质客户的流失.为了提高配送的准时性并得到优质客户的发展和维护，本文结合客户的消费特征构建出基于客户分类的即时配送路径优化模型，以总成本最小为目标对即时配送车辆路径问题进行研究.

1 客户分类及惩罚函数设定

传统的VRP模型认为客户价值是相同的，在设定惩罚函数时也是同等处理，这显然违背了优质客户想要得到更精准配送服务的心理愿景，更是违背了商家想要维护和发展优质客户的初衷.本文以RFM模型[14]即消费近度R(最近一次购买时间)、消费频次F和平均消费额M为分类依据，对某即时配送平台510位客户的32 475条消费数据进行挖掘分析，对数据进行归一化处理后通过python3.6 平台使用DBSCAN算法进行聚类，得到四组数据，结果显示噪声比为0.39%，轮廓系数为0.706，聚类效果良好.由于客户消费近度R差别不大，本文主要根据消费频次F与消费金额M来刻画客户特征，具体结果如图1所示.

第1组共80位客户，其消费频次和金额都高于平均值，约占总消费频次和金额的50%左右，一旦失去此类客户会对商家造成极大损失，故将其归为核心客户.因该类客户对配送准时性要求较高，为避免失去此类客户必须在预计时间内服务，所以惩罚成本为一个较大的数，其惩罚函数看似简单却极为严格，具体为

式中：F1为核心客户的惩罚函数；ti为客户i的实际送达时间；Ti为客户i的预计送达时间.

图1 分类结果Fig.1 Classification results

第2组和第3组共280位客户，或是消费频次或是消费金额高于平均值，约占总消费频次和金额的40%～45%，是商家重点挖掘价值并发展为核心客户的对象，本文将其归为一类称为潜力客户.设定此类客户在超时10 min内的惩罚成本与超时时间呈线性增长，当超时10 min后为避免因超时过长导致客户产生负面情绪甚至流失，设定惩罚成本呈指数增长，具体为

式中：F2为潜力客户的惩罚函数；Cp为单位超时惩罚成本.

第4组共150位客户，其消费频次与金额都低于平均值，约占总消费频次和金额的5%～10%，对企业的价值最低，将其称为边缘客户.因其价值较低不宜投入过多成本来维护，本文设定此类客户在超时10 min内和10 min以外的惩罚成本均为固定值，具体为

式中：F3为边缘客户惩罚函数；P1为超时10 min内的惩罚成本；P2为超时20 min内的惩罚成本.

2 即时配送路径优化模型

2.1 问题描述

本文研究的即时配送车辆路径问题如下：某即时配送平台接到n位客户的订单，要求在客户预计送达时间内完成配送.其中，配送中心可支配的车辆数为m辆，配送车辆的最大容积为Q，若未能在客户的预计时间内送达则会产生相应惩罚，不同类别的客户所对应的惩罚成本不同.因此，需要在满足客户需求的前提下，安排合适经济的配送方案.

针对该问题，本文做出如下假设：

(1)车辆从配送中心出发，沿着一条路线将货物送达指定客户，最终回到原点；

(2)配送中心可使用车辆充足且型号和容量相同；

(3)每辆车可以服务多个客户，但每个客户仅能被一辆车服务一次；

(4)不考虑车流量及路况限制，车辆采用平均行驶速度.

2.2 模型构建

本文所研究模型的变量和参数如下：

N——客户点集合，N={i|i=0,1,2,…,n}，其中0为配送中心；

K——车辆集合，K={k|k=1,2,3,…,m} ；

Q——车辆的容积限制；

V——车辆行驶速度；

Ct——单位运输成本；

tij——车辆从客户i到客户j的行驶时间；

ts——客户的服务时间；

qi——客户i的需求量；

Ck——车辆k的固定成本；

xkl——若车辆k在l位置上服务了客户，则xkl=1，否则为0；

——若车辆k在l位置上服务的客户为i，则否则为0；

——车辆k从i驶向j则为1，否则为0；

hk——车辆k被启用则为1，否则为0；

ai——若客户i属于核心客户则为1，否则为0；

bi——若客户i属于潜力客户则为1，否则为0；

ci——若客户i属于边缘客户则为1，否则为0.

根据以上描述，构建基于客户分类的即时配送路径优化模型，具体表示为

式(4)为模型的目标函数，使得固定成本、运输成本和超时惩罚成本之和最小；式(5)表示每辆车最多为n个客户服务，一次只能服务一个客户；式(6)表示每个客户仅能被一辆车服务一次；式(7)保证和xkl的值一致；式(8)表示每辆车承载货物总体积不能超过车辆可携带的最大容积Q；式(9)表示车辆是否被派出；式(10)表示车辆k到达客户j处的时间tj与到达上一客户i处的时间ti的关系；式(11)表示客户i仅有一种类别属性.

3 遗传算法设计

由于本文是对车辆数和车辆路径的同时寻优，常见的遗传算法是以自然数编码方式形成车辆路径后再以插0规则形成子路径，遗传算子部分只能对代表车辆路径的自然数进行操作，容易陷入局部最优.本文提出了车辆数与车辆路径对应排列编码的遗传算法，通过对车辆数与车辆路径的共同操作扩大搜索面积并提高产生新有效基因的能力，从而克服早熟现象.算法流程图如图2所示，具体设计思想如下.

(1)编码.本文编码分为两步：第一步，前n列随机生成代表车辆数的0-1 实数，1代表车辆终止配送，0代表继续配送；第二步，后n列随机生成代表车辆路径的1-n序数，2n列基因码共同构成一条染色体.例如有9个客户点，染色体编码为001010011241536978，此基因序列表示共4辆车，配送路径分别为2-4-1，5-3，6-9-7，8.

图2 算法流程图Fig.2 Algorithm flowchart

(2)初始种群和适应度函数.首先由上述编码方式随机生成一组路径方案，即一个V2n⋅N的二维矩阵(N为种群数)，然后进行约束条件的逐条检验，若违反了某个约束条件，则给予一定惩罚使其适应度降低从而将其淘汰.本文选取目标函数的倒数为适应度函数，即

(3)选择.为提高遗传算法性能，本文在轮盘赌的基础上采用精英保留策略[15]，避免优秀染色体被破坏，提高求解效率.

(4)交叉.对前n列0-1 数和后n列自然数共同进行交叉操作.首先，使相邻个体进行两两配对，避免重复交叉.其次，在前n列0-1数中随机选取交叉点i，取位置i的左边部分进行交换.在后n列自然数中随机选中两个基因点进行交换交叉.通过对前n列与后n列的交叉操作产生新染色体，具体运算原理如图3所示.

(5)变异.对前n列0-1 数和后n列自然数共同进行变异操作.在前n列中随机选取变异点进行0-1 互换变异.对于后n列，随机选取两个位置的基因进行交换变异.通过上述对前n列和后n列的变异操作，得到新的子代染色体，具体运算原理如图4所示.

图3 交叉操作示意图Fig.3 Cross operation diagram

图4 变异操作示意图Fig.4 Mutation operation diagram

4 案例分析

本文采用西安市某即时配送公司提供的数据，该公司是一家专业的即时配送服务公司，为客户提供餐饮外卖、商超便利等配送服务.对该平台进行数据采集，以某时刻的业务场景为例，为36个客户点提供服务，通过规划出合理的配送方案以满足客户需求并保证总成本最低.模型参数如表1所示，其中，固定成本的设定综合考虑了购买车辆的费用、配送员的平均薪资、车辆的维修费和折旧费以及车辆的使用寿命和出车次数而设定，因配送车辆大多为电动车，运输成本根据电池续航能力和充电费用而设定，惩罚成本是调研和参考企业目前的惩罚成本并结合本文的相关分析而设定的.以上述聚类结果为基础，采用贝叶斯算法训练数据得到分类模型以判定36个客户的所属类别，客户需求信息及类别判定结果如表2所示.

表1 相关参数取值Table1 Related parameter values

以上述客户类别判定结果为基础，通过MATLAB R2016a平台求解配送方案，设置交叉概率pc和pc1分别为0.9和0.92，变异概率pm和pm1分别为0.08和0.05，终止迭代次数G为600.得到基于客户分类的配送方案如表3所示，其算法的种群进化趋势如图5所示.

表2 客户需求信息及所属类别Table2 Customer demand information and category

表3 本文方案Table3 Scheme of this article

图5 种群进化趋势图Fig.5 Trend of population evolution

从图5可以看出，该算法具有收敛性，种群最终向优秀发展.为了验证算法的有效性，将传统遗传算法与本文算法随机试验6次得到的方案进行对比，结果显示本文算法寻优能力更强，具体如表4所示.A为传统遗传算法，B为本文算法.

将本文方案与企业当前没有采取客户分类的配送方案进行对比分析来验证模型的合理有效性.其中，企业当前配送方案如表5所示，两个方案的对比分析如表6所示.

由表6可以看出，本文方案中一类和二类客户的配送延时较企业配送方案有明显降低，提前到达率达到了99.48%，一类客户和二类客户的配送时效性也分别提高了56.05%和19.23%.另外，总的配送用时和超时时间也有相应改善，分别减少了15.73%、85.95%.虽然从短期看企业需要付出一定成本，但是通过客户分类企业可以使其资源得到合理分配，通过准时性的提高来建立良好口碑从 而吸引和发展优质客户，赢得更多长期潜在效益.

表5 企业配送方案Table5 Distribution scheme of enterprise

表6 两种方案对比分析Table6 Comparative analysis of two schemes

为了验证模型的适用性，本文增设了两个案例进行分析.其中，采用本文客户分类得到的方案为a、c，企业不进行客户分类的方案为b、d，具体如表7所示.

表7 其他案例的对比分析Table7 Comparative analysis of other cases

综上所述，本文方法虽然支付了一定的额外成本，但从长期的战略角度看，有利于发展维持优质客户并吸引新客户，扩大企业影响力并促进企业的可持续发展.

5 结 论

为提高配送准时性并得到优质客户的发展和维护，从战略角度为企业寻求更多潜在效益，本文对客户消费数据进行挖掘分析，将客户分为三类，根据每类客户的特点设置了超时惩罚函数，构建了基于客户分类的即时配送路径优化模型，同时设计了合适的遗传算法求解算法.实验结果验证了模型的合理性和算法的有效性.