O2O模式下生鲜农产品配送路径优化

（东北林业大学 交通学院，黑龙江 哈尔滨 150040）

1 引言

O2O（Online To Offline）模式下生鲜农产品电子商务为顾客提供线上交易、线下配送的服务。从生产地到达需求地的过程中，对生鲜农产品损失率影响较大的是配送质量，农产品易腐性对配送服务的时效性要求较高，物流企业以顾客为中心，首先考虑配送时间约束，又兼顾配送成本。因此，配送质量是衡量O2O模式下生鲜农产品供应链最为关键的指标，优化配送路径也成为物流环节最为关注的技术问题之一。

近年来，O2O模式下的生鲜电商取得了快速的发展，随着生鲜农产品需求量的增加，线上交易和线下服务质量研究不断多元化。对于线上交易，一般以提升交易效率和可靠性为研究热点，针对生鲜农产品电商平台发展模式[1]、运营策略[2]和影响顾客购买行为的因素[3]进行研究。在配送路径研究方面，国内外学者一般以车辆行驶路径最短、运输费用最低、配送车辆数量最少、配送时间最短等单个或多个指标作为目标函数，建立多约束下的优化模型，采用混合启发式算法[4-5]、元启发算法[6]、遗传算法[7-8]、蚁群算法[9-10]等求得模型最优解或满意解。

本文在以上研究的基础上，针对目前O2O模式下生鲜农产品配送中存在的问题，以顾客满意度最大和配送成本最小为目标，引入配送消耗成本和时间窗惩罚成本两个决策变量，在顾客时间窗、车辆行驶最大里程和最长时间的限制下构建O2O模式下生鲜农产品配送路径优化模型，结合扫描法与遗传算法，获得模型的最优解。

2 生鲜农产品配送问题描述

O2O模式下生鲜农产品配送问题可以简单描述为下列过程：

（1）生鲜农产品交易线上平台接收、整理、处理顾客订单；

（2）将顾客收货位置、生鲜农产品需求量、设置的时间窗等配送信息传递至线下实体店；

（3）线下实体店根据配送信息，完成生鲜农产品的出库，设计最优配送路径，逐一访问顾客位置，完成生鲜农产品的配送任务。

2.1 配送目标

（1）提高顾客的满意度。一方面，顾客线上交易时间虽然随机化，但对生鲜农产品的接收时间有要求；另一方面，线下实体店尽量在顾客可接收时间内及时完成配送，保证产品新鲜度。

（2）降低配送成本。生鲜商品属于易腐、易耗产品，线下配送成本不仅包括配送车辆的固定成本和变动成本，也包括产品损耗成本和时间惩罚成本。

考虑以上配送目标，在建模时引入车辆行驶最大里程和最长行驶时间的约束条件，同时引入顾客时间窗，当不能满足顾客可接收时间要求时，增加早到或晚到的惩罚成本。车辆的固定成本（如车辆折旧费用）与运输里程和顾客数量都没有直接关系；车辆的变动成本（如油耗）与运输距离有关。生鲜农产品的损耗成本可简化为运输时间的线性函数，这是由于在时间—温度变化品质耐性研究中，随着保存温度、时间的增加，产品质量会受到影响，而温度在一定时间内变化不大，可以不考虑。时间惩罚成本是生鲜配送早于或晚于顾客设定的时间窗完成交货产生的费用。

2.2 约束条件

（1）生鲜农产品实体店数量为1个，接收线上顾客订单信息，有充足货源满足顾客需求，拥有多辆型号相同的专用配送车辆，实体店为线下配送服务的出发地点。

（2）顾客收货的地理位置、时间窗限制和对生鲜农产品的需求量（单一品种）根据线上订单信息可知，每个顾客需求量低于配送车辆的最大载重量，各顾客之间距离低于配送最大行驶里程。

（3）线下配送车辆要在顾客设置的时间窗内完成配送服务，否则产生惩罚成本。

（4）每条配送线路只安排一辆配送车辆，每条线路上顾客需求量之和不超过配送车辆最大载重量，配送线路的长度不能超过设定的最大里程；配送线路的行驶时间不能超过设定的最大时长。

（5）配送车辆配送途中交通条件较好，以匀速行驶至各顾客点，完成所有配送任务后回到生鲜农产品实体店。

3 配送路径优化模型

根据以上问题描述，以配送成本（包括配送车辆固定成本、配送车辆变动成本、生鲜农产品消耗成本和时间惩罚成本）最低为目标函数，建立数学模型如下：

约束条件：

决策变量：

式中：i=0,1,...,n;j=0,1,...,n;k=1,2,...,m;Z表示O2O模式下生鲜农产品配送成本（元）；m表示配送车辆总数（辆）；Pk表示配送车辆k产生的固定费用（元/辆）；e表示车辆单位距离运输成本（元/km）；v表示配送车辆的行驶速度（km/h）；n表示顾客总数；i=0,1,...,n表示实体店和顾客，其中i=0表示实体店；（Xi,Yi）表示顾客i位置坐标；dij（i,j=1,2,...,n）表示顾客i到顾客j的距离（km），dij=dji；doj（j=1,2,...,n）表示实体店到顾客j的距离（km）；qi（i=1,2,...,n）表示顾客对生鲜农产品的需求量（kg）；p表示生鲜农产品平均单价（元/kg）；β表示配送中农产品损耗的比例；ti表示配送车辆到达顾客i的时刻；tij表示配送车辆从顾客i到顾客j的行驶时间，tij=dij/v；tki表示车辆k到达顾客i后进行服务的时间（min）；[Ei,Li]表示顾客i设置的时间窗，其中Ei表示顾客设置时间窗的起始时刻，Li表示顾客设置时间窗的终止时刻；δ1表示配送车辆早于顾客设置的时间窗带来的惩罚系数；δ2表示配送车辆晚于顾客设置的时间窗带来的惩罚系数；Qmax表示配送车辆的最大载货量（kg/辆）；Lmax表示配送车辆的单程行驶最大里程（km）；Tmax表示配送车辆行驶的单程配送最长时间（min）。

式（2）与（3）表示每个顾客恰好被访问一次；式（4）表示每辆配送车辆从实体店出发并最终返回实体店；式（5）与（6）表示配送车辆到达每个顾客后，必须离开该顾客；式（7）为车辆载货量约束；式（8）为车辆行驶最大里程单程里程约束；式（9）为时间约束；式（10）为最长时间单程时间约束。

4 模型求解

4.1 扫描算法

本文采用扫描算法划分车辆配送区域，具体步骤如下：

（1）建立极坐标系。以实体店的位置作为极点，以X轴方向为正方向，建立极坐标系，并对所有顾客所在的位置，进行极坐标系的变换。

（2）分组。首先划分第一组，从正方向开始，按逆时针方向扫描，将顾客逐个加入到第一组中，累加计算顾客的需求量，当累加值超出车辆载货量时，重新建立新的一组，继续扫描，直到所有的顾客都分组完成。

（3）划分区域。根据分组的结果划分车辆配送区域。

4.2 遗传算法

针对每一区域，采用自适应能力强、收敛速度快的遗传算法进行路径优化求解，设计遗传算法如下：

（1）编码。采用自然数编码方式，其中0表示配送中心和不同路径之间的分隔符，例如个体编码020130表示两条路径，第一条路径为配送中心—顾客2—配送中心，第二条路径为配送中心—顾客1—顾客3—配送中心。

（2）初始种群。初始种群是进行遗传进化操作的第一代种群，由N个个体组成，通过随机方式生成。群体规模的大小影响种群多样性和运算速度，进而影响遗传算法优化的最终结果及其计算效率，一般取值为40～100。

（3）计算染色体的适应度。O2O模式下生鲜农产品配送路径目标是使配送总成本最小，即目标函数值最小，而适应度值应该是非负的，适应度值越大，表示个体的性能越好，被选择到下一代的概率越大。因此需要将目标函数转化为适应度，设Zr为染色体r的目标函数值，则染色体r的适应度函数值fr为：，表示目标函数值Zr与适应度函数值fr成反比。

（4）选择操作。采用轮盘赌方式进行选择，从群体中选择一些个体，这些个体被选中的概率与它们的相对适应度值成正比，能够保证适应度高的个体以更大的概率被选中。设群体大小为M，个体r适应度为fr，则个体r被选中的概率这种选择方式首先保证了所有个体都有几率遗传到下一代,并且适应度高的个体会被优先选择,保证了优良基因可随迭代过程持续传递。

（5）交叉操作。采用顺序交叉法，首先随机选择一对父代中几个基因的起止位置（两染色体被选位置相同），然后生成一个子代，并保证子代中被选中的基因的位置与父代相同，接着找出第一步选中的基因在另一个父代中的位置，最后再将其余基因按顺序放入上一步生成的子代中。

交叉操作需要确定交叉概率，交叉概率与父代间发生交叉概率有关，一般情况取0.5上下[11]。

（6）变异。采用随机变异法，即随机选择两点并交换位置，可保持群体的多样性，增强遗传算法的随机搜索能力，以防止出现过早收敛现象。变异概率一般取0.1-0.3[11]。

（7）设置终止条件。采用事先确定最大遗传代数作为遗传算法的终止规则，保证能有效地获得可行的最优解，而不是无限地循环计算，其值根据研究的问题而定。

5 模型验证

5.1 参数设置

某生鲜农产品实体店线上交易平台9：00至10:00点接到17个顾客订单，即n=17（人），生鲜农产品平均单价p=7（元/kg），顾客相关信息（地理坐标、需求量、时间窗、车辆到达位置至离开的服务时间）见表1和图1。实体店拥有5辆相同型号并配备了保鲜箱的电动车。电动车的长宽高为56cm，车厢最大装载量为Qmax=25（kg/辆），单位距离运输成本e=0.4（元/km），平均车速v=35（km/h）。考虑到车与配送人员一一对应，且电动车的固定成本很小，因此车辆产生的固定费用Pk=20（元/辆）。根据以往数据，配送中农产品损耗的比例β=2%。单程里程约束Lmax=35（km），单程时间约束Tmax=60（min），早于时间窗惩罚成本系数δ1=0.2，晚到时间窗产生的惩罚成本系数为δ2=0.3。遗传算法求解中，种群规模为60，交叉概率是0.8，变异概率0.2，迭代次数500次。

表1 顾客基本信息

图1 顾客位置

5.2 模型求解

本文分别采用遗传算法、遗传算法结合扫描算法两种求解方法，扫描算法分区如图2所示，求得的配送路径和成本见表2，最优配送路径如图3所示：

图2 扫描算法分区

表2 两种求解方法求解的配送路径

由表2和图3可知，与不预先采用扫描算法相比，只采用遗传算法确定的最优配送路径总成本较高。这是因为遗传算法求解时，有较大的随机性，当种群规模、交叉概率、变异概率和最大迭代数等遗传参数确定时，种群中个体的数量多，随机性大，初始种群找到最优解的可能性小，即使经过选择、交叉和变异的操作会增加寻找到最优解的概率，但其仍存在着随机性，最优解被找到的概率依然较小。相比较而言，首先运用扫描算法进行路线分区，使运用遗传算法计算的种群个体数量减少，在遗传参数确定的条件下，初始种群较易找到最优解，且经过选择、交叉和变异操作进一步优化解，最终得到最优解的概率大大增加；且这些个体相对位置集中，有利于优化最短路径，使生鲜配送车辆的变动成本、生鲜损耗成本和时间惩罚成本降低，从而降低了生鲜配送总成本。此外，采用扫描算法预先分区后，每个区域的变量数量相对减少，遗传算法迭代次数降低，计算速度更快。

图3 最优配送路径图

6 结语

对于O2O模式下生鲜农产品实体店，配送成本直接影响企业利润，配送服务质量影响企业的可持续发展。本文深入分析线上交易、线下配送的O2O生鲜农产品供应链模式，以配送总成本最低和顾客满意度最大为目标函数，建立了线下配送路径优化模型。模型的约束条件既考虑了消耗成本、车辆行驶里程和行驶时间，又考虑了顾客收货的时间窗及其惩罚系数。最后采用扫描算法预先分区，再用遗传算法求得最优配送路径。与不采用扫描算法相比，该综合算法降低了生鲜配送总成本，提高了计算速度。采用扫描算法分区时，本文考虑了顾客收货时间窗和车辆额定载货量，但没有考虑各顾客之间道路交通条件，后续研究中加入交通拥堵系数、道路条件等指标，以使分区更加合理。