基于SVM的生鲜食品冷链共配实时订单分类模型*

□ 高 甜，伍景琼，徐浩然，苏 娜

(1.昆明理工大学 交通工程学院，云南 昆明 650500；2.上海德邦物流有限公司，上海 200000)

1 引言

随着人民生活水平的不断提高，人民对于生鲜食品的品质也越来越重视。但是，由于生鲜食品的易腐性以及时效性等，使得生鲜食品冷链共配发展滞后，导致客户日益增长的优质生鲜食品需求与落后的生鲜食品冷链共配现状存在显著矛盾。

为有效缓解这一矛盾，大量学者从客户生鲜食品订单需求角度展开研究。Jean-Charles Créput等[1]针对新的客户需求，利用自组织映射神经网络对客户订单进行聚类分析。张潜等[2]提出先用优先级综合聚类分析法对客户进行分类，再用改进遗传算法来求解多目标车辆路径问题的优化方法。崔丽[3]针对需求驱动下动态城市车辆调度问题，提出先对客户需求订单进行分类，然后再对车辆调度问题进行求解。Alan Slater[4]针对新客户需求，提出基于需求预测的动态调度系统，用闭环的专家系统对需求进行预测。Naccache[5]基于B2C电子商务对订单合并运输问题进行了研究，以运输成本最小为目标，求解最佳车辆调度方案。Chen等[6]针对实时订单需求，提出了采用列生成的动态办法来求解带时间窗的车辆路径问题。李琳等[7]提出了将禁忌搜索算法与插入算法相结合进行求解订单预测模型，可以有效地利用电子订货系统预测订单的未来信息。孙刘诚，孙焰[8]研究了带订单选择车辆路径问题，以最大化企业经济效益为优化目标，建立了混合整数规划模型，发现通过订单交换和协调，不仅能够提高企业的利润，并能够一定程度上减少车辆的行驶距离。Chen[9]则考虑了组合拍卖机制中的运输企业的订单选择行为，并将其剥离出来形成独立的子问题进行研究。

现有研究主要针对一般商品的共同配送订单进行分析与预测，而生鲜食品具有时效性、多样性、易腐性等特点，现实配送中不仅需要考虑个别客户的紧急订单，还要考虑某些生鲜食品易腐败的特点。因此，本文建立以实时客户订单为基础的生鲜食品冷链共配实时订单分类模型，从订单筛选、订单分类及确定服务优先级三个阶段对实时订单进行分析，以保证生鲜食品冷链共配的准确性与时效性。

2 支持向量机分类算法

支持向量机(Support Vector Machine，SVM)是由Vapnik基于统计学习理论的提出的一种针对分类和回归问题的新型机器学习方法[10]。SVM具备较为完全整的数学理论，其具有较强的泛化能力，在解决小样本、非线性及高维空间模式识别的问题上具有较好的效果。支持向量机是一种监督学习模型，可以通过对历史数据的学习，来解决分类问题。

支持向量机的原理是随机产生一个超平面，然后移动它直至不同分类的点刚好位于超平面的不同侧面，并且保证分类的精度。根据SVM的原理，支持向量机可以完美的实现对线性可分数据的分类。SVM的数学模型如下：把两类数据输入到在一个n维空间中，支持向量机通过构造一个和这两类数据边界距离最远的超平面，来实现对这两类数据的分类。给定一个SVM的训练集{xi,yi}，其中i=1,2,L，l，yi∈{-1,1},xi∈RD(xi包含D个特征)。用来区分两类数据的超平面可以表示为wx+b=0，其中w是超平面的法向量，|b|/‖w‖是超平面距原点的垂直距离。全部的训练样本满足条件：

yi(xiw+b)-1+ξi≥0,ξi≥0,∀i

(1)

引入松弛变量来解决线性不可分的问题，其中，ξi≥0，i=1,2,L,l。通过式(1)，可以将最大化支持向量机的界线转换成解决如下的最优化问题：

(2)

s.t.yi(xiw+b)-1+ξi≥0,ξi≥0,∀i

(3)

式中：C为惩罚系数，C具有平衡松弛变量和分类范围的大小的作用。(3) 式是一个凸二次优化的问题，其解为：

(4)

常用的支持向量机核函数有多项式函数、径向基函数、复合核函数和Sigmoid函数等，通过这些不一样的核函数可以构造出相应的支持向量机。核函数的选择对构造支持向量机有着至关重要的影响，选用适合的核函数，可以降低计算的复杂度，得到更好的分类结果。

支持向量机在求解多类分类问题时，主要的解决办法有两种：一种是基于原来的SVM优化函数，引入多类机制对其进行改进，使其扩展为多类支持向量机，改进后的SVM可以直接进行多类分类。但是，这种解决多类分类问题方法具有较为复杂的目标函数，很难实现。另一种是通过结合多个两类SVM组成一个多类分类器，通过这些两类SVM间接的进行多类分类。经常用到的组合多个两类SVM的方法有四种：一对多法、一对一法、导向无环图法和二叉树法。本文采用一对一法来解决客户订单的多类分类问题。

一对一法中每一个二值分类器仅对所有类别中的两类进行分类处理，可以减少样本学习的时间。同时，每一个两类分类器的学习样本是均衡的，训练精度较高。

3 生鲜食品冷链共配实时订单分类模型

建立以实时客户订单为基础的生鲜食品冷链共配实时订单分类模型，从订单筛选、订单分类及确定服务优先级三个阶段对实时订单进行分析，及时响应客户的实时需求，保证生鲜食品冷链共配的准确性与合理性。

3.1 需求订单筛选

需求订单筛选，是以客户订单处理周期为依据，确定每个周期内所需要处理的相关客户订单。为了方便建模，本文假定配送中心的客户订单处理周期是T(包括订单分类时间和车辆调度时间)，在周期T开始时，配送中心需要将该周期内处理的订单筛选出来，为之后的客户订单处理阶段做准备。

在周期T内处理的订单需要满足以下条件：

(5)

(6)

通式(5)和(6)筛选出生鲜食品客户订单，将筛选出的订单输入到下一个阶段，对其进行分类。每个订单处理周期都不断地重复这个过程，订单筛选的过程如图1所示。

图1 订单筛选示意图

3.2 需求订单分类

需求订单分类阶段主要是针对通过筛选阶段的实时订单，根据其相似属性(内在与外在属性)对其进行聚类分组。该阶段主要分为两个部分，首先进行特征参数的选取分析，然后采用支持向量机(SVM)对客户订单进行聚类分析。

3.2.1 特征参数的选取

基于生鲜食品的属性和车辆调度的需求，本文选取了6个特征参数进行订单分类处理。具体如下所示：

3.2.2 SVM算法聚类分组

使用支持向量机对生鲜食品客户订单进行分类，是通过对历史生鲜食品订单数支持向量机据的学习后，对订单进行分类，得到订单分类结果具有较好的客观性。基于支持向量机的订单分类过程如下：

①对历史客户订单进行分析，选取相关的特征参数，建立指标体系。

②根据指标体系中的特征参数，收集相关的历史客户订单，构成支持向量机的训练样本集。

③根据支持向量机的分类算法对训练样本集进行训练，获取订单分类的客观规律。

④找到训练集中的支持向量构造支持向量机决策函数。

⑤将待分类的客户订单输入到决策函数中，从而得到分类结果。

3.3 确定客户服务优先级

确定客户服务优先级是在订单分类确定后各个客户组别的服务顺序，然后根据服务顺序制定合理的生鲜食品配送方案。生鲜食品具有时效性、多样性、易腐性等特点，现实配送中不仅需要考虑个别客户的紧急订单，还要考虑某些生鲜食品易腐败的特点。因此，配送企业需要综合考虑各种影响因素，合理确定订单的服务优先级，来提高企业的服务水平和整体效益。

表1 多因素法确定客户优先级量化值计算

根据表1的计算结果，来确定客户的服务优先级，然后根据优先级制定车辆调度方案。采用多因素法确定服务优先级，可以较为全面的考虑各种影响因素，提高企业的效益。因此，生鲜食品企业需要综合考虑各种影响因素，以快速响应客户需求和企业效益水平为目标，科学地确定客户服务优先级。

3 算例分析

3.1 算例概述

本文假设某区域有3个生鲜食品配送中心，对周围边长为20km的正方形地域内的30个客户提供配送服务，每个客户的生鲜食品需求量都在2t以下，配送中心有10台配送车辆，配送车辆的最大载重量为5t，蓄冷保温箱的容量为1t，最大配送距离为60km。将客户需求量按照常温、冷藏、冷冻三个温层的生鲜食品的比例(0.25:0.65：0.1)拆分[11]，每个生鲜食品的客户订单中包含3种温层的生鲜食品。利用MATLAB随机生成30个初始客户的坐标和需求量，配送中心与初始客户的坐标如表2所示。初始客户的需求量如表3所示。

表2 配送中心与初始客户位置坐标

表3 初始客户需求量

3.2 算例求解

通过实时订单分配模型对客户订单进行分组并确定其服务优先级。为了方便操作，本论文假设订单商品价值相差不大，商品的内兼容性和外兼容性均较好。因此，本文选择客户位置、时间窗和客户的需求量3个指标作为聚类参数。在对客户订单进行分类之前，需要量化这些指标，如表4所示。

表4 初始客户订单分类指标量化值

采用MATLAB软件在LibSVM工具包的基础上对30个初始客户订单进行分类，选取多分类SVM中一对一组合方法，选择RBF核函数。惩罚系数C和核参数的选择主要采用网格搜索寻优法。其基本思路是：分别选定C和的一个区间，确定步长，在选定的区间内，让C和呈指数增长，不断改变C和的组合，初步寻找两者的最佳组合，然后确定准确率出现最高的一个小区间，并逐步缩短步长重复搜索，直至搜索结果精度变化不大为止，所得结果即为最优化参数。利用MATLAB对客户订单进行分类，结果如图2所示，验证精度达93.333%，如图3所示。

图2 客户订单SVM分类结果

图3 客户订单SVM分类精度

最终，客户生鲜冷链共配实时订单分配结果如表5所示，30个客户被分成了7个组别。其中，组别1、组别3和组别6优先配送；组别2和组别5次之；组别4中客户数量最多，其优先级为3；组别7则最后配送。

表5 客户订单分类结果

4 结论

为了高效妥善地解决随机性、零散化的动态客户需求，建立了基于支持向量机的生鲜食品冷链共配实时订单分类模型，用来对订单进行筛选、分类和确定服务优先级，并通过算例验证模型的有效性。该模型中支持向量机分类法能在较短的时间内求得共配订单的分类结果，同时根据客户位置、时间窗和客户的需求量科学安排服务的先后顺序，在节约企业成本的同时，最大程度地满足了客户的个性化需求。