客户分级优先的即时配送路径规划方法

吴晓东; 王正鑫; 刘川平

doi:10.16503/j.cnki.2095-9931.2024.04.007

交通运输研究 >

2024 , Vol. 10 >Issue 4: 68 - 79

DOI: https://doi.org/10.16503/j.cnki.2095-9931.2024.04.007

服务转型升级

客户分级优先的即时配送路径规划方法

吴晓东 ^,¹ ,
王正鑫 ^,¹^,^* ,
刘川平 ²

展开

¹ 东北林业大学土木与交通学院，黑龙江哈尔滨 150040
² 沈阳师范大学数学与系统科学学院，辽宁沈阳 110034

^* 王正鑫（1999—），男，黑龙江哈尔滨人，硕士，研究方向为大数据与智慧物流。E-mail:1913589474@qq.com

吴晓东（1968—），男，黑龙江哈尔滨人，博士，副教授，研究方向为交通运输规划。E-mail:1092006376@qq.com

收稿日期: 2024-04-28

网络出版日期: 2024-10-15

基金资助

国家重点研发计划项目(2017YFC0803901-2)

收起

A Real-Time Delivery Path Planning Method with Customer Classification Priority

WU Xiaodong ^,¹ ,
WANG Zhengxin ^,¹^,^* ,
LIU Chuanping ²

Expand

¹ College of Civil Engineering and Transport, Northeast Forestry University, Harbin 150040, China
² College of Mathematics and Systems Science, Shenyang Normal University, Shengyang 110034, China

Received date: 2024-04-28

Online published: 2024-10-15

Fold

摘要

为了使即时配送企业能以较低的成本提高配送准时性，从而维护并发展高价值客户，首先，针对即时配送客户的特点改进RFM模型，基于已有数据使用DBSCAN算法进行客户聚类，根据聚类结果使用GBDT算法构建客户分级预测模型对即时配送客户进行分级预测。在此基础上，以即时配送的固定成本、变动成本及客户超时点种类、数量为优化目标，构建基于客户分级优先的即时配送路径优化模型，再设计遗传算法对该模型进行求解。最后，以沈阳市某一站式冷链即时配送企业为对象进行实例分析。结果显示，相比该企业原配送方案，应用客户分级优先的即时配送路径规划方法规划后的方案在配送总成本仅提高4.8%的情况下，高价值、潜在高价值客户超时点数量由6减少为2，且超时点均为边缘客户，同时配送总时间减少了7.3%，验证了该方法的有效性。采用该配送路径规划方法，企业的配送成本虽然会小幅增加，但因配送准时性提升，可以更好地维护高价值客户，同时发展潜在高价值客户向高价值客户转变，进而保持或提高长期收益。

关键词： 路径规划; 即时配送; 时间窗约束; 聚类分析; 遗传算法; 客户分级

本文引用格式

吴晓东 , 王正鑫 , 刘川平 . 客户分级优先的即时配送路径规划方法[J]. 交通运输研究, 2024 , 10(4) : 68 -79 . DOI: 10.16503/j.cnki.2095-9931.2024.04.007

Abstract

In order to enable real-time delivery enterprises to improve delivery punctuality at lower costs, meanwhile maintain and develop high-value customers, firstly, the RFM model was improved based on the characteristics of real-time delivery customers, and customer clustering based on existing data was realized using the DBSCAN algorithm. Using the GBDT algorithm, a customer grading prediction model based on the clustering results was constructed to predict the grading of customers. On this basis, with the fixed and variable costs of instant delivery, as well as the types and quantities of customer timeout points as optimization objectives, a real-time delivery path optimization model based on customer classification was constructed, and a genetic algorithm was designed to solve the model. Finally, a case study was conducted on a one-stop cold chain real-time delivery enterprise in Shenyang. The results showed that compared to the original delivery plan of the enterprise, the plan planned using real-time delivery path planning method with the customer classification priority only increased the total delivery cost by 4.8%. Meanwhile the number of high-value and potential high-value customer timeout points decreased from 6 to 2, and the timeout points were all edge customers. At the same time, the total delivery time decreased by 7.3%, verifying the effectiveness of the planning method. By adopting this delivery path planning method, although the delivery cost of the enterprise may slightly increase, the improvement of delivery punctuality can better maintain high-value customers, while developing potential high-value customers and transforming them into high-value customers, thereby maintaining or improving long-term profits.

Key words： path planning; real-time delivery; time window constraint; clustering analysis; genetic algorithm; customer grading

0 引言

国际咨询公司Frost & Sullivan发布的《2023年中国即时配送行业趋势白皮书》显示，2023年中国即时配送服务行业订单量达408.8亿单，较上一年度增长22.8%，预计到2028年，中国即时配送订单规模将达到813.1亿单^[1]。2024年1月22日，国务院常务会议审议通过《关于促进即时配送行业高质量发展的指导意见》，指出近年来即时配送行业快速兴起，要求进一步营造良好营商环境，提升行业发展水平和支撑带动能力^[2]。当前即时配送企业间的竞争激烈，如何在降低配送成本的同时提升服务质量是即时配送行业发展中的一个难题。针对不同客户分配服务资源，优化即时配送路径规划，实现对不同客户群的差异化服务是解决这一问题的方法之一。

即时配送路径规划是车辆路径规划问题（Vehicle Routing Problem, VRP）的变形，即考虑软时间窗约束、成本及容量约束的车辆路径优化问题（Capacitated Vehicle Routing Problem with Soft Time Windows and Costs, CTWVRP）^[3]。许多学者对交通状况实时信息^[4]、动态需求^[5]、碳排放^[6]等带有软时间窗的VRP问题进行了研究，为附带条件的VRP问题研究提供了思路。近年来，电子商务的快速发展极大地增加了即时配送服务需求，越来越多的学者开始关注即时配送路径规划问题，大多集中在提高客户满意度、降低配送成本方面，如：户佐安等^[7]以配送服务时间是否准确衡量客户满意度，从而对配送路径进行优化；杜琛等^[8]以配送准时性为衡量指标，用模糊预约时间的隶属度函数^[9]对客户满意度进行量化。上述研究虽然较为准确地衡量了客户对配送服务的满意程度，但并未根据客户价值的不同给出相应的配送策略。也有学者考虑客户分类进而优化配送路径，如杨静等^[10]采用熵值法对客户分类指标体系中5个指标赋予权重，再利用Spssau进行客户分类，针对客户类型的不同提供差异化服务，以提升客户对服务的满意度。但大多数研究主要围绕客户对配送时间的敏感度^[11]、客户消费频率和金额^[12]以及是否购买准时理赔产品^[13]展开，未针对即时配送客户的特点设置分类指标，容易造成分类错误，流失高价值客户。

综上所述，既有研究未考虑根据客户价值提供相应的配送策略，也未针对即时配送客户的特点设置分类指标。针对这两个问题，本文将在既有研究基础上，优先考虑客户分级，再进行即时配送路径规划，以期实现针对不同客户群体的差异化服务。首先，本文将从即时配送企业的角度对客户群体进行细分，根据客户特点对RFM（Recency, Frequency, Monetary）模型进行改进，设定分级指标，再基于已产生的消费数据使用DBSCAN算法进行客户聚类，然后根据聚类结果采用GBDT算法构建客户分级预测模型对配送客户进行分级预测，并对不同等级客户设定相应的超时惩罚成本，再使用遗传算法对配送路径进行规划，力求在合理的成本内提升配送时效，维护和发掘高价值客户，保持或提高企业长期收益。

1 问题描述与分级预测模型构建

1.1 问题描述

某即时冷链配送公司同时收到n位客户的订单，需按客户预定时间完成配送。该公司拥有m辆最大载重量相同的配送车辆。若不能在客户预定时间内完成配送，将会根据客户分级的不同产生相应的超时惩罚成本。因此，本文要解决的问题就是在满足所有客户需求的前提下，快速识别客户级别，根据客户级别对配送路径进行规划，在考虑客户分级优先的同时，提供提升客户满意度、降低配送成本的配送路径方案。以下为研究假设：

1）车辆从配送中心出发，沿着指定路线逐个客户进行配送，最后返回；

2）配送中心有足够数量且型号和容量相同的车辆可供使用；

3）车辆途中可以配送多个客户，但每个客户只能被一辆车配送一次；

4）车辆以平均速度行驶，不考虑在路上的实际行驶速度和交通状况；

5）配送中心供货量充足，所有待出发车辆均处于已完成装货状态。

1.2 相关算法

采用DBSCAN算法进行客户聚类。它是一种基于密度的空间聚类算法，可将高密度区域的数据点划分为簇，并能在噪点中识别出任意形状的空间聚类，受噪点影响较小^[14]。即时配送客户的消费数据中噪点较多，且预先设定聚类数会影响即时配送客户分级的准确性。DBSCAN聚类算法不同于k-means聚类算法，它通过参数自动确定聚类数，无需预先设定客户群数量，可以更自然地根据数据本身的特性进行客户聚类。

在采用梯度提升决策树（Gradient Boosting Decision Tree, GBDT）算法建立客户分级时，通过串行训练多个决策树来提高预测性能。GBDT通过迭代训练决策树模型，每一棵树都在前一棵树的残差基础上进行训练，从而逐步减小预测误差^[15]。GBDT能够处理包括连续型、离散型等多样性特征数据，适用于客户分级预测模型可能涉及的各种特征类型，同时对于聚类结果中的噪点和异常值具有一定的鲁棒性，能够有效处理数据中的异常情况，保证模型的稳定性，提高模型预测的准确性。

1.3 对RFM模型的改进

RFM模型是一种用于分析客户价值和对客户分群的工具，广泛应用于营销和客户关系管理（Customer Relationship Management, CRM）领域^[16]。该模型基于3个关键维度，包括最近一次购买时间（Recency）、购买频率（Frequency）和购买金额（Monetary）。

即时配送客户的特点是其购买行为更多地受当下需求和便利程度的影响，而最近一次购买时间（Recency）无法准确刻画即时配送用户的消费行为特征，所以本文主要关注客户的购买频率（Frequency）和购买金额（Monetary），在此基础上引入客户注册时长（Tenure）指标。客户注册时长是指从客户首次在商家注册账号或首次购买日到统计当日的时长，通过该指标可以清晰地区分新老用户。最终，本文将RFM模型改进，去除最近一次购买时间（Recency）指标，引入客户注册时长（Tenure）指标，从而更加准确地刻画即时配送客户的特征。

1.4 客户分级预测模型构建

1.4.1 基于改进RFM与DBSCAN的客户分级

本文以购买频率F、购买金额M、客户注册时长T作为客户分级的依据，在符合隐私保护相关法规的基础上，以沈阳市某一站式即时冷链配送公司为例，对其523名客户的23 147条消费数据进行收集、清洗、分类、汇总、编号，利用Max-Min标准化方法^[17]进行处理，得到标准化数据。数据处理过程如图1所示。在Python3.12平台上，使用DBSCAN聚类算法对标准化数据进行聚类，设定参数值邻域半径Eps=0.1205，最小样本数Minsamples=5，输出聚类结果，如图2所示。部分输出的聚类结果如表1所示，其中等级列为-1的分类数据为噪点，将其剔除。数据的噪点比为1.9%，轮廓系数为0.53，显示聚类效果良好。

显示原图|下载原图ZIP|生成PPT

图1 数据处理流程

显示原图|下载原图ZIP|生成PPT

图2 客户聚类结果

表1 部分聚类结果

序号	F	M	T	类
0	0.336 538 5	0.203 530 3	0.192 307 7	0
1	0.884 615 4	0.663 469 7	0.346 153 8	1
2	0.355 769 2	0.069 810 1	0.269 230 8	0
3	0.221 153 8	0.741 118 8	0.923 076 9	2
4	0.730 769 2	0.845 747 4	0.346 153 8	1
5	0.346 153 8	0.788 326	0.730 769 2	2
6	0.288 461 5	0.703 468	0.961 538 5	2
7	0.307 692 3	0.645 361	0.615 384 6	2
8	0.375 0000	0.818 961 8	0.769 230 8	2
9	0.846 153 8	0.693 329 9	0.846 153 8	3
10	0.240 384 6	0.731 610 9	0.538 461 5	2

1.4.2 聚类结果分析

通过聚类结果可以看出，DBSCAN算法将客户分为0, 1, 2, 3, 4，共5个类，购买频率F、购买金额M、注册时长T的平均值分别为0.425, 0.646, 0.652。

根据聚类结果，1类、3类客户占比为30.06%，虽然1类客户注册时长T低于平均值，3类客户注册时长T高于平均值，但是二者购买频率F、购买金额M均高于平均值。说明上述客户无论注册时间长短，都是高价值客户，失去此类客户，将对企业造成极大的损失。

2类、4类客户占比为65.13%，二者注册时长T均高于平均值，购买金额M与平均值接近，购买频率F低于平均值。说明此类客户存在多个可供选择商家或者不需要经常进行采购，但此类客户的数量占比非常高，是潜在高价值客户，提升配送服务质量后，此类客户可能会转变成高价值客户，反之则可能成为边缘客户，需要企业给予高度关注。

0类客户占比为4.81%，其购买频率F、购买金额M、注册时长F均低于平均值。说明此类客户是企业的边缘用户，维护成本不宜过高。

综上，本文将该企业的客户分为3级，分别为高价值客户、潜在高价值客户、边缘客户。

1.4.3 模型测试及评估

本文从剔除噪点后的499组分级数据中按各组所占比例，随机选出101组数据作为测试集，其余398组数据作为训练集，通过Python3.12平台，使用GBDT算法对训练集进行训练得到分类预测模型。树的深度与准确率的关系如图3所示。不同学习率下错误偏差提升率随迭代次数变化情况如图4所示。

显示原图|下载原图ZIP|生成PPT

图3 准确率随树的深度变化趋势

显示原图|下载原图ZIP|生成PPT

图4 不同学习率下错误偏差提升率随迭代次数变化趋势

由图3、图4可以看出，当树的深度为2时准确率最高，当迭代次数为5 000、学习率为0.05时错误偏差提升率最低且趋于稳定。利用此模型对测试集进行分类预测，重复5次，利用混淆矩阵对预测结果进行评估，预测准确率分别为98.02%, 99.05%, 99.01%, 98.95%, 99.24%，方差为0.23，说明该模型的预测效果好，可以用于客户分级预测。分级预测模型的构建流程如图5所示。

显示原图|下载原图ZIP|生成PPT

图5 分级预测模型构建流程

2 客户分级优先的即时配送路径优化模型

2.1 参数定义

本文构建的函数及模型所涉及的参数定义如表2所示。

表2 参数定义

参数	定义
$g k$	0-1变量，如果车辆k被使用，则值为1，否则值为0
$x i j k$	0-1变量，如果车辆k从客户i直接前往客户j，则值为1，否则值为0
$x i h k$	0-1变量，如果车辆k从客户i直接前往客户h，则值为1，否则值为0
$a i, b i, c i$	分别表示客户i的超时惩罚成本等级界定，超时为1，否则为0
$P 1, P 2, P 3$	分别对应不同的客户分级的超时惩罚成本
$i, j$	表示客户点集合 $1, 2, ⋯, n$ 中的第i，j个客户
$k$	表示配送中心车辆集合K={1, 2,⋯, m}中的第k辆
$t i$	表示配送车辆实际到达客户i的时间
$t i j k$	表示车辆k从客户i到客户j所需的行驶时间，可以通过距离除以车辆的平均速度得出
$t j$	表示车辆到达客户j的时间
$S i$	表示客户i的服务时间，即车辆在客户i处停留的时间
$[E t i, L t i]$	客户预约送达的时间区间，最早时间为 $E t i$ ，最晚时间为 $L t i$
$C k$	车辆固定成本
$C s$	单位行驶里程运输成本
$C m$	第一级客户较大的固定超时惩罚成本
$C t$	第二级客户基础超时惩罚成本
$C f$	第三级客户较小固定超时惩罚成本
$f 1$	运输过程中单位时间制冷成本
$f 2$	卸货过程中单位时间制冷成本
$α$	第二级客户超时惩罚成本的指数系数
$d i j$	从客户i到客户j的距离，包括从配送中心出发和返回配送中心的距离
$q i$	客户i的需求量
$D$	每辆车的最大载重量
$H$	无限大的数

2.2 惩罚函数构建

本文中的配送超时是指配送车辆到达客户i的实际时间不在客户预计的送达时间内，包括以下3种情况。

1）提前送达。此时又可分为两种情况。第一种情况是在到达客户点之后立即进行货物交接，配送车辆的运输成本会降低，但需要考虑客户是否方便收货。第二种情况是配送车辆在客户点等待至约定的时间进行货物交接。本文假设配送车辆提前送达时都是第二种情况，即等到时间窗到达才进行货物交接，在设置惩罚函数时，当车辆出现提前送达的情况时，超时惩罚成本为无限大，即H。

2）准时送达。此时可立即进行货物交接，惩罚成本为0。

3）延迟送达。到达后产生惩罚成本。

根据1.4.2节聚类结果分析，针对三级客户设计不同的超时惩罚成本函数如下。

第一级客户是企业的高价值客户。这类客户无论是新老用户，都表现出较强的购买力和对企业的依赖性，他们的购买金额和购买频率都较高，是企业稳定发展的关键。因此对该级别客户的配送服务设定严格的超时惩罚机制，确保在客户预定时间内送达。对于这类客户的服务，超时惩罚成本固定且较高，不受超时时长影响，具体如式（1）所示：

（1）

P 1 = 0 E t i ≤ t i ≤ L t i H t i E t i C m t i L t i

第二级客户是企业的潜在高价值客户。该类客户可能有多种消费选择，具备成为高价值客户的潜力。他们对服务质量的感受可能直接影响他们的忠诚度和购买决策，因此需要注意服务时间窗口。对于该类客户，企业应该采取较严格的超时惩罚机制，使超时惩罚成本随着超时时间的增加增长得更快，以督促超时的车辆在较短的时间内送达。本文中，对于这类客户的服务，超出预定时间窗口外的惩罚成本将呈指数级增长，具体如式（2）所示：

（2）

P 2 = 0 E t i ≤ t i ≤ L t i H t i E t i C t α t i - L t i t i L t i

第三级客户无论使用时间长短，其购买频率和购买金额都较小，是企业的边缘客户。对于边缘客户，当出现配送超时情况时，不作优先考虑。对于这类客户的服务，在设定惩罚函数时，优先考虑企业的配送成本和总体配送效率，将超时惩罚成本设置为一个较小值，具体如式（3）所示：

（3）

P 3 = 0 E t i ≤ t i ≤ L t i H t i E t i C f t i L t i

2.3 即时配送路径规划模型构建

根据1.1节的问题描述和2.1节的参数定义，构建客户分级优先的即时配送路径规划模型，目标函数如式（4）所示，模型约束表示为式（5）~式（11）。

（4）

m i n C = ∑ k = 1 m C k g k + C s ∑ i = 0 n ∑ j = 0, j ≠ i n ∑ k = 1 m d i j x i j k + ∑ i = 0 n ∑ j = 1 n ∑ k = 1 m x i j k f 1 t i j k + f 2 S i + ∑ i = 1 n (a i P 1 + b i P 2 + c i P 3)

（5）

∑ j = 1 n x 0 j k = 1, ∑ i = 1 n x i 0 k = 1 k ∈ K

（6）

∑ i = 0 n ∑ j = 1 n x i j k ≤ n k ∈ K

（7）

∑ i = 0, i ≠ j n x i j k - ∑ h = 0, h ≠ j n x j h k = 0 k ∈ K; j = 0, 1, ⋯, n

（8）

∑ i = 1 n ∑ j = 0, j ≠ i n q i x i j k ≤ D k ∈ K

（9）

∑ i = 0 n ∑ j = 0, j ≠ i n x i j k ≤ n g k k ∈ K

（10）

t j ≥ t i + t i j k + S i - H (1 - x i j k) k ∈ K; i = 0, 1, ⋯, n; j = 1, ⋯, n; i ≠ j

（11）

a i + b i + c i = 1 i = 1, ⋯, n

式（4）旨在使包括固定成本、变动成本（包括运输成本、制冷成本，而制冷成本又包括车辆运输过程单位时间制冷成本和卸货制冷成本）、超时惩罚成本在内的综合成本最低。

式（5）表示车辆从配送中心出发，最终返回。

式（6）表示车辆途中可以配送多个客户，但每个客户只能由一辆车配送一次。

式（7）为车辆使用连续性约束，确保车辆从一个客户出发后必须到达另一个客户（包括配送中心），直至配送结束。

式（8）为车辆容量约束，表示配送车辆所承载货物重量不能超过车辆的最大载重量。

式（9）为车辆使用标志约束。

式（10）表示车辆k服务客户i和客户j的时间先后顺序。

式（11）用以确保每个客户有且仅有一种分级。

2.4 优化算法设计

遗传算法解决路径优化问题时常采用二进制编码，但二进制编码的固定长度受到限制，无法充分表达路径中节点的差异，导致算法容易陷入局部最优解^[18]。鉴于此，本文采用二进制编码与整数编码混合编码方式，利用二者的优点，可以有效表示车辆数目和配送路径，扩大了搜索空间、提高了搜索效率、保持了种群多样性，从而帮助遗传算法克服早熟现象。遗传算法流程如图6所示。

显示原图|下载原图ZIP|生成PPT

图6 遗传算法流程图

1）编码。随机生成的前n列0-1实数表示车辆状态，1表示终止配送，0表示继续配送，这部分编码表示车辆的数量和每辆车是否终止配送，以二进制编码实现。后n列随机生成的1-n序数代表车辆的路径顺序，这部分编码表示每辆车的具体配送路径，是一个整数编码的形式。将两部分编码整合为一个染色体，例如对于有6个客户点和3辆车的情况，一个染色体编码为001011234561，表示共有3辆车，配送路径分别为2-3-4, 5-6, 1。

2）初始化种群。随机生成路径方案，每个路径方案代表一个个体，包含了客户的访问顺序和车辆的路线安排。逐项检验约束条件，对违反约束的路径方案施加惩罚，降低其适应度并淘汰。

3）适应度函数。本文以固定成本、变动成本、客户超时惩罚成本总和最小为优化目标，而在遗传算法中，个体的适应度值越大代表其对应的解决方案在目标函数值上表现越好^[19]，所以本文中的适应度函数为目标函数的倒数。

4）选择操作。本文选择算子操作，采用基于轮盘赌选择改进的随机遍历抽样（Stochastic Universal Sampling, SUS）^[20]。假设有5个个体，即N=5，适应度值分别为8, 5, 3, 3, 6，总适应度值A=25，选择的个体数目也为5。首先，计算指针的间距P=A/N=5。其次，假设随机生成起点指针位置S=2。然后，根据间距及指针起点位置计算得到指针所指位置分别为2, 7, 10, 17, 22。最后，根据各指针位置选择5个个体，个体序号为1, 1, 2, 4, 5。选择操作的具体过程如图7所示。

显示原图|下载原图ZIP|生成PPT

图7 选择操作

5）交叉操作。由于本文采用混合编码的方式，所以对于个体的前n列采用双点交叉，后n列采用单点交叉，实现不同的交叉操作策略，以产生多样化的子代染色体。首先，确保种群中相邻个体固定搭配，避免重复交叉操作。然后，前n列的0, 1和后n列的自然数，分别执行不同的交叉操作。对于前n列采用二进制编码的0和1，随机选择交换点a，交换两个个体位置a左侧部分。后n列的整数编码，随机选择两个基因片段进行交换。交叉操作的具体过程如图8所示。

显示原图|下载原图ZIP|生成PPT

图8 交叉操作

6）变异操作。针对前n列，随机选择一个位置i的基因进行变异：如果基因为1，则变为0；如果基因为0，则变为1。对于后n列，由于每个数字代表唯一位置点，为了避免重复，本文通过随机选择位置a与位置b的基因进行互换变异，可以生成一个新的子代染色体，包括前n列和后n列的变异操作。变异操作的具体过程如图9所示。

显示原图|下载原图ZIP|生成PPT

图9 变异操作

3 案例分析

本文实例分析数据来自沈阳市某一站式即时冷链配送公司。该公司于2010年成立，注册资本1 500万元，为中小食堂、餐馆、个人提供蔬菜、肉蛋禽、果品、水产品、奶制品等生鲜产品即时配送服务，客户可以通过公司网站或电话订购获得即时配送服务。本文以该公司某日上午为30个客户提供即时配送服务的实际数据为例，验证模型的有效性，并进行路径规划。根据1.4节建立的客户分级预测模型对30个客户进行分类预测，客户点坐标、客户需求量、客户可接受时间窗和客户分级结果如表3所示。其中，客户分级列的“1”表示高价值客户、“2”表示潜在高价值客户、“3”表示边缘客户。该公司的配送车辆为江淮JAC国六排放标准中型制冷车。固定成本是综合考虑车辆的购置成本、保险费、车辆折旧、使用年限、驾驶人员薪资、出车频率等因素后得出。变动成本由运输成本和制冷成本组成，运输成本是考虑车辆油耗、车辆维护费用等因素得出。制冷成本由车辆运输过程单位时间制冷成本和卸货制冷成本构成。超时惩罚成本参考企业目前超时惩罚成本、相关研究成果以及对同规模企业超时惩罚成本调研结果后综合得出。具体模型参数如表4所示。

表3 客户信息、需求及分级结果

编号	X坐标 /km	Y坐标 /km	需求量 /kg	客户可接受时间窗	服务时间/min	客户分级
0	0	0		[08:00, 20:00]
1	-1.058	-0.221	14	[09:40, 11:20]	5	3
2	0.708	0.998	16	[09:10, 10:50]	7	2
3	2.319	-0.628	15	[10:10, 11:50]	3	2
4	-0.841	1.223	9	[10:10, 11:50]	4	2
5	-2.262	-0.458	20	[09:40, 10:50]	7	3
6	-2.229	0.533	19	[09:40, 11:20]	9	3
7	-1.362	-3.078	17	[09:10, 10:50]	8	1
8	0.278	-2.006	11	[09:10, 10:50]	6	2
9	1.065	1.913	14	[09:40, 11:20]	9	1
10	1.382	0.567	13	[10:10, 11:50]	4	1
11	2.553	-1.685	19	[09:10, 10:50]	8	2
12	-2.813	1.168	11	[09:40, 10:50]	5	1
13	-3.559	-2.559	14	[10:10, 11:50]	7	1
14	1.300	-0.429	12	[09:40, 11:20]	9	2
15	4.916	0.853	10	[09:40, 11:20]	9	2
16	5.164	1.186	7	[10:10, 11:20]	7	2
17	-1.837	1.425	14	[10:10, 11:50]	6	2
18	3.433	-1.357	18	[09:10, 10:50]	9	2
19	3.515	-1.119	22	[10:10, 11:20]	8	1
20	3.118	-0.017	14	[09:40, 11:20]	6	2
21	2.233	1.271	16	[10:10, 11:50]	7	2
22	2.494	1.649	12	[09:10, 10:50]	8	3
23	-1.184	2.521	14	[10:10, 11:50]	5	3
24	1.607	3.757	11	[09:40, 11:20]	9	3
25	2.270	0.444	17	[10:10, 11:50]	5	3
26	-0.339	2.216	10	[09:40, 11:20]	9	2
27	1.174	-4.413	15	[09:10, 10:50]	9	2
28	-1.143	-1.479	7	[09:10, 10:50]	7	2
29	0.669	-3.707	8	[10:10, 11:50]	6	3
30	3.813	1.407	18	[09:40, 10:50]	7	2

表4 模型参数

参数	C_k/（元/车）	C_s/（元/km）	D/kg	V/（km/h）	C_m/元	C_ti/（元/h）	C_f/（元/h）	f₁/（元/h）	f₂/（元/h）	α
取值	30	3	300	25	1000	360	100	1.2	2	1.2

根据上述数据以及客户分级结果，在MATLAB R2020a平台使用2.4节设计的遗传算法对模型进行求解。对所有方案均进行多次计算从而得出最优方案，避免程序执行中存在的偶然性。遗传算法参数设置如下：种群大小为100，交叉概率均为0.9，变异概率均为0.01，终止进化代数为500。客户分级优先配送路径方案及总成本等数据如表5所示。最优路线各坐标点位置如图10所示。该算法种群进化趋势如图11所示，“最优值”为配送总成本最小值，可以看出种群向“优秀”进化，算法具有收敛性。

表5 客户分级优先的配送路径方案

配送路径	总成本 /元	超时客户编号	超时时长/min	超时客户级别
0-20-3-8-28-6-12-23-9-2-10-0	316.69
0-14-11-19-18-15-16-30-22-21-24-0
0-25-26-17-4-27-29-7-13-5-1-0		5, 25	-7.8, +6	3, 3

注：-表示提前送达，+表示延迟送达。

显示原图|下载原图ZIP|生成PPT

图10 最优路线各坐标点

显示原图|下载原图ZIP|生成PPT

图11 种群进化趋势

在不改变遗传算法各项参数以及费用数据的前提下，不考虑客户分级优先，惩罚成本取该企业实际超时惩罚成本300元/h，对配送路径进行重新优化，得到的配送路径方案及总成本等数据如表6所示。

表6 不考虑客户分级优先的方案

配送路径	总成本/元	超时客户编号	超时时长/min	超时客户级别
0-6-5-23-24-26-1-28-3-11-14-0	298.98	9, 11	-2.7, +4.8	2, 1
0-4-12-17-13-7-27-29-8-25-2-0		1, 10	-10.8, +12	2, 1
0-9-22-20-18-19-15-16-30-21-10-0

注：-表示提前送达，+表示延迟送达。

为验证本文客户分级预测模型在即时配送路径优化中的有效性，将客户分级优先与不考虑客户分级的配送路径优化方案进行对比分析，结果如表7所示。

表7 是否考虑客户分级优先的方案对比

方案	总时长 /min	总距离 /km	总成本 /元	超时客户数量
方案	总时长 /min	总距离 /km	总成本 /元	级别1	级别2	级别3
不考虑客户分级优先	168	57.60	298.98	2	2	0
考虑客户分级优先	165	60.57	316.69	0	0	2
优化后的变化幅度	-1.8%	+5.2%	+5.9%

由表7可以看出，本文提出的考虑客户分级优先的方案与不考虑客户分级的方案在总时长、总距离相近的情况下，超时客户均为边缘客户，且仅有2个；而不考虑客户分级方案的超时点客户为高价值客户和潜在高价值客户，共有4个。本文的方案虽然使总成本增加了5.9%，但是有利于企业维护高价值客户，发展潜在高价值客户向高价值客户发展。

该公司实际配送服务按区域划分，每台配送车辆负责相应配送区域，按照客户要求的配送时间依次配送。由于实际配送车辆行驶距离是按照实际行驶路线计算，而本文中的行驶距离只考虑客户点之间的直线距离，因此实际运输成本高于本文中的运输成本。所以，本文将该公司实际车辆行驶距离设置为客户点间的直线距离，将惩罚成本设定为该公司实际超时惩罚成本300元/h，得出该企业实际配送路径方案下的总成本等数据，如表8所示。

表8 企业实际配送方案

配送路线	总成本/元	超时客户编号	超时时长 /min	超时客户级别
0-10-25-20-15-16-30-22-21-9-2-0	302.05	9	+3	1
0-14-3-19-18-11-29-7-8-28-27-0		11, 28	-5.1, +1.6	2, 2
0-4-24-26-23-17-12-6-5-13-1-0		26, 5, 13	-6.8, +3, +10.2	2, 3, 1

注：-表示提前送达，+表示延迟送达。

为验证本文客户分级优先的即时配送路径规划模型在实际即时配送路径规划中的有效性，将本文优化后的配送方案与实际的配送方案进行对比分析，结果如表9所示。该企业实际配送路线与利用本文方案优化后配送路线对比如图12所示。

表9 本文方案与企业实际配送方案对比

方案	总时长 /min	总距离 /km	总成本 /元	超时客户数量
方案	总时长 /min	总距离 /km	总成本 /元	级别1	级别2	级别3
实际	178	59.86	302.05	2	3	1
考虑客户分级优先	165	60.57	316.69	0	0	2
优化后的变化幅度	-7.3%	+1.2%	+4.8%

显示原图|下载原图ZIP|生成PPT

图12 实际配送路线与本文方案优化后的路线对比

从表9可以看出，本文提出的客户分级优先的配送方案与该企业实际配送方案相比，总距离相近，总成本虽然增加了4.8%，但是配送总时长减少了7.3%。同时，本文提出的方案仅有2个客户超时点且均为边缘客户，而企业实际方案有6个客户超时点，且多数为高价值客户和潜在高价值客户。

综上所述，本文的方案虽然在总成本上略高于实际方案，但是节约了配送时间，从企业的长期发展来看，更有利于维护高价值客户、发展更多的潜在高价值客户成为高价值客户，为保障企业的长期收益提供有效支持。

4 结束语

本文根据即时配送客户特点对RFM模型进行改进，引入客户注册时长指标，利用DBSCAN聚类算法对标准化数据进行聚类，将企业客户分为三级，对应设置不同的超时惩罚成本，利用GBDT对数据进行训练得到客户分级预测模型，基于此模型对沈阳市某即时配送企业某时间段实际产生的即时配送订单，设计遗传算法对配送路径进行规划，得到以下结果。

1）利用本文提出的客户分级优先的即时配送路径规划模型优化后的配送方案相比该企业实际配送方案，在配送成本仅增加4.8%的情况下，客户超时点数量由6减少为2，且超时点均为边缘客户，高价值和潜在高价值客户的货物都在预定时间内送达，同时配送总时间缩短7.3%。从长期来看，企业虽增加了少量成本，但更利于维护现有高价值客户，发展潜在高价值客户转向高价值客户，从而保持或提高企业的长期收益。

2）本文对RFM模型进行改进，针对即时配送客户的特点，利用改进模型构建的基于GBDT算法的客户分级预测模型其5次测试平均准确率为98.95%，方差为0.23。通过实例验证，认为该模型的预测准确率高且稳定，可以应用于客户分级优先的路径规划问题。

由于在实际配送中，车辆的行驶路线并不是模型所设定的客户点之间的直线，实际行驶距离相比模型有所增加，今后可以考虑将更多的即时配送企业作为研究对象，并根据实际行驶路线开展更加精细化的研究。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序

[1]	Frost & Sullivan Consulting Inc. China′s real-time delivery industry trends white paper for 2023[R]. (2024-03-17)[2024-04-01]. https://www.frostchina.com/content/insight/detail?id=65f64369a2aa84f5d865a560.

[2]	中共中央, 国务院. 关于促进即时配送行业高质量发展的指导意见[EB/OL]. (2024-01-22)[2024-04-01]. https://www.gov.cn/zhengce/202401/content_6927940.htm.

[3]	BRAEKERSK, RAMAEKERSK, VAN NIEUWEN-HUYSEI. The vehicle routing problem: State of the art classification and review[J]. Computers & Industrial Engineering, 2016, 99: 300-313.

[4]	SAEED K, MARAL S, IRAJ M, et al. A model for the time dependent vehicle routing problem with time windows under traffic conditions with intelligent travel times[J]. RAIRO Operations Research, 2021, 55(4): 2203-2222.

[5]	YANG Z, OSTA J P, VEEN B, et al. Dynamic vehicle routing with time windows in theory and practice[J]. Natural Computing, 2016, 236(2): 429-443.

[6]	康凯, 韩杰, 普玮, 等. 生鲜农产品冷链物流低碳配送路径优化研究[J]. 计算机工程与应用, 2019, 55(2):259-265. DOI

[7]	户佐安, 贾叶子, 李博威, 等. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107. DOI

[8]	杜琛, 李怡靖. 基于客户满意度和最小损耗的冷链配送路径问题研究[J]. 工业工程与管理, 2020, 25(6): 163-171.

[9]	张建勇, 郭耀煌, 李军. 基于顾客满意度的多目标模糊车辆优化调度问题研究[J]. 铁道学报, 2003, 25(2):15-17.

[10]	杨静, 俞武杨. 基于客户分类和混合车型的绿色车辆路径优化[J]. 信息与管理研究, 2023, 8(1):75-86.

[11]	CUI S, SUN Q, ZHANG Q. A time-dependent vehicle routing problem for real-time delivery based on memetic algorithm[J]. Computational Intelligence and Neuroscience, 2022, 10: 509-520.

[12]	于江霞, 杜红亚, 罗太波. 基于客户分类的即时配送路径优化研究[J]. 交通运输系统工程与信息, 2020, 20(4):202-208.

[13]	张力娅, 张锦, 肖斌. 考虑客户优先级的多目标O2O外卖即时配送路径优化研究[J]. 工业工程与管理, 2021, 26(2):196-204.

[14]	WANG X, ZHOU C, YANG Y, et al. Electricity market customer segmentation based on DBSCAN and k-Means: A Case on Yunnan electricity market[C]// Proceedings of 2020 Asia Energy and Electrical Engineering Symposium(AEEES). Chengdu, China: IEEE, 2020: 869-874.

[15]	FRIEDMAN J H. Greedy function approximation: A gradient boosting machine[J]. The Annals of Statistics, 2001, 29(5): 1189-1232.

[16]	WEI J T, LIN S, WU H H. A review of the application of RFM model[J]. African Journal of Business Management, 2010, 4(19): 4199-4206.

[17]	HUBERT K, ELISHA B. Normalization and Standardization: Methods to preprocess data to have consistent scales and distributions[J]. ResearchGate, 2023, 2237: 10-21.

[18]	KATOCH S, CHAUHAN S, KUMAR V. A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80(5): 8091-8126.

[19]	LEE C, LIN W, CHEN W, et al. Gene selection and sample classification on microarray data based on adaptive genetic algorithm/k-nearest neighbor me-thod[J]. Expert Systems with Applications, 2011, 38(5): 4661-4667.

[20]	魏全新, 刘贤锋, 黄锵, 等. 遗传算法选择方法的比较分析[J]. 通讯与计算机, 2008, 8(45):61-65.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

0 引言

1 问题描述与分级预测模型构建

1.1 问题描述

1.2 相关算法

1.3 对RFM模型的改进

1.4 客户分级预测模型构建

1.4.1 基于改进RFM与DBSCAN的客户分级

图1 数据处理流程

图2 客户聚类结果

表1 部分聚类结果

1.4.2 聚类结果分析

1.4.3 模型测试及评估

图3 准确率随树的深度变化趋势

图4 不同学习率下错误偏差提升率随迭代次数变化趋势

图5 分级预测模型构建流程

2 客户分级优先的即时配送路径优化模型

2.1 参数定义

表2 参数定义

2.2 惩罚函数构建

2.3 即时配送路径规划模型构建

2.4 优化算法设计

图6 遗传算法流程图

图7 选择操作

图8 交叉操作

图9 变异操作

3 案例分析

表3 客户信息、需求及分级结果

表4 模型参数

表5 客户分级优先的配送路径方案

图10 最优路线各坐标点

图11 种群进化趋势

表6 不考虑客户分级优先的方案

表7 是否考虑客户分级优先的方案对比

表8 企业实际配送方案

表9 本文方案与企业实际配送方案对比

图12 实际配送路线与本文方案优化后的路线对比

4 结束语

参考文献