基于Selenium和遗传算法的配送路径优化研究——以HFZ便民直销店为例

王西状，陈玉兰 （新疆农业大学 经济与贸易学院，新疆 乌鲁木齐 830052）

0 引言

随着人们物质生活水平的提高，人们对蔬菜、水果、蛋类和肉类等生鲜农产品需求量增加的同时，其新鲜程度、获取的价格和便利性也成为关注的重点。生鲜农产品不像其他商品，其保质期短，容易磕碰损坏，种类繁多，每种生鲜农产品的运输条件又不尽相同。生鲜农产品配送体系的不健全，在存储和运输环节保鲜技术低，容易造成大量的生鲜农产品腐烂变质，这不仅仅会危害公司的利益，也会造成生鲜农产品价格的上涨和食品安全隐患，降低了人们的生活水平和生活质量。

“红房子”社区便民直销店（HFZ）是奎屯市重点企业——奎屯泽惠果蔬配送有限公司旗下的连锁便民超市，建立自有物流配送中心，实现了采、配、销一体化运营模式，目前全市共设有63个门店，遍及奎屯市各社区。通过在调研中发现，由于HFZ尚处于发展阶段，相关的技术和实践不够成熟，忽视配送路线规划问题，配送路线采取以司机分片区负责的方式，司机的主观性较大，经常出现某一网点缺货或存货过多造成损耗的问题。本文正是基于以上背景，拟利用Selenium和遗传算法建立HFZ社区便民直销店生鲜农产品物流路径优化模型，合理安排车辆和优化运输路径，以达到降低企业物流成本、提高企业经济效益的目的。

1 HFZ生鲜农产品配送路径优化模型构建

在物流配送路径优化模型选择方面。王玥丹（2014）、高帅仁（2018）、景晓腾（2020）、程钰（2021）、刘娜娜（2021）、田帅辉（2021）等均采用遗传算法求解配送路线优化问题，并证实遗传算法在配送路线优化上具有显著优势。

1.1 优化目标

本文以HFZ社区便利店为例，对配送路径进行优化，在需求量一定、车辆最大行驶距离、车辆最大装载量及各个门店的时间窗等约束条件下，使得社区便利店的生鲜农产品配送总费用最低，距离最短。

1.2 问题描述

本文研究的是奎屯市HFZ社区便利店的生鲜农产品配送问题，具体问题描述如下：

（1）配送的车辆能够将生鲜农产品有序的送达63家门店。

（2）HFZ配送车辆所能装载生鲜农产品的重量是有限的，各个社区便利店的需求是一定的且小于配送车辆的装载重量，可以将多个连锁店的生鲜商品需求汇总装在同一辆车上进行配送，提高配送车辆的装载率。

（3）社区便利店的配送中心是起点也是终点，泽惠果蔬配送中心所有的配送车辆向63家便利店配送生鲜农产品，每辆车配送结束后都返回到配送中心。

（4）63家社区便利店接收生鲜农产品都有自己的时间窗约束。

（5）在Y连锁超市生鲜商品的配送路径优化方案时，优化目标是配送的总成本最小，约束条件有：时间窗、配送车辆装载量的限制、配送车辆行驶距离最短。

1.3 模型假设

为了使构建的配送路径优化模型与社区便利店的实际情况更加符合，提高模型的真实性，本文在构建配送路径优化模型之前从多个方面提出以下假设：

（1）社区便利店的配送中心和63家门店的位置都是已知的，配送中心可以将63家社区便利店所需的生鲜农产品送达。

（2）配送车辆型号统一，车辆的最大载重量和最远行驶距离相同。

（3）配送车辆只承担送货任务，不承担取货任务，送完生鲜农产品后返回配送中心。

（4）63家便利店需要的生鲜商品可以混装在不同车辆上。

（5）配送车辆行驶速度已知且恒定，配送是在早高峰来临之前，路上几乎不存在交通拥堵状况。

（6）配送生鲜农产品时生鲜农产品的损坏率只是与时间有联系。

（7）63家便利店的需求量是已知的，每一个连锁门店只能由一辆车服务。

（8）配送中心的生鲜农产品的数量能够满足63家连锁门店所有的需求，配送中心的一辆冷藏车一次可以为多个社区便利店送去生鲜农产品。

1.4 参数说明

对车辆路径优化模型中重要的参数做如下说明：

Y：目标函数；

X：配送车辆编码；

B：配送中心和63家便利店的集合；

C：生鲜农产品配送车辆的固定费用；

C：生鲜农产品配送车辆的单位变动成本；

Q：配送中心每辆配送车辆的最大装载量；

L：从便利店i完成配送任务后到达便利店j所用的距离；

［ET,LT］：各个便利店最早和最晚接收货物的时间；

U：配送车辆提前到达连锁门店等待配送产生的成本；

U：配送车辆晚点到达连锁门店配送产生的惩罚费用；

R：便利店i的需求量（以重量计算）；

L：配送车辆x的可以行驶的最大里程；

m：运输的时候生鲜商品损坏的概率；

m：卸货的时候生鲜商品损坏的概率；

v：配送车在配送路途中的行驶速度；

e：配送车辆装卸效率；

f：配送车辆数量；

T：在便利店j处的卸货时间；

P：生鲜商品的单位价格；

Q：便利店i处卸货后车内剩余生鲜商品的数量；

T：配送车辆到达连锁门店i处的时间；

S：在区间（i,j）内车辆x的装载量；

W=1，表示车辆x从便利店i到便利店j，否则W=0；

Z=1，便利店i由配送车辆x配送，否则Z=0。

1.5 目标函数

本文所要建立的HFZ社区便利店的生鲜农产品配送路径优化模型的总目标为配送总成本最小。而生鲜农产品配送的总成本包括4个方面，分别是固定成本、运输成本、货损成本和等待成本或惩罚成本。虽然是生鲜农产品，但是便利店的配送没有采用冷藏车配送，因此成本中不存在制冷成本。

（1）固定成本

固定成本只有一个，就是配送车辆司机师傅的工资，由于便利店的车辆是师傅自己的，所以不存在设备折旧费，该成本不受其他因素的影响，是固定不变的。固定成本的表达式如下：

（2）运输成本

HFZ社区便利店的生鲜农产品的运输成本主要是配送车辆的燃油费，影响运输成本的因素有行驶距离的远近和配送门店的数量。运输成本的表达式如下：

（3）货损成本

货损成本主要由运输途中的损失和卸货时的损失两部分组成。货损成本的具体表达式如下：

（4）等待成本或惩罚成本

63家便利店对生鲜商品的送达时间都有自己的要求，用等待成本和惩罚费用来衡量配送车辆能否在规定时间内将生鲜农产品从配送中心送至各个便利店。如果车辆在门店的规定送货时间之前到达连锁门店的话，就会产生等待成本，如果车辆在门店规定的送货时间延迟送达，那么就会产生惩罚费用。生鲜农产品配送的等待成本和惩罚成本的具体表达式如下：

以总成本最小构建HFZ社区便利店配送路径优化模型的目标是总成本最低，即固定成本、变动成本、货损成本、等待成本和惩罚成本相加之和最小。配送路径优化模型如下：

1.6 约束条件

公式（8）表示HFZ社区便利店63家店都能被配送到一次；公式（9）明确了W和Z两个变量之间的关系；公式（10）表示一条配送路线的生鲜农产品由配送中心的一辆车负责配送，车辆在执行一次任务时只能离开配送中心一次；公式（11）表示在一次配送的过程中，配送车辆在完成配送任务时，配送行驶的距离要小于配送车辆的最大行驶距离；公式（12）表示配送中心的配送车辆对生鲜农产品的最大载重量；公式（13）、公式（14）表示配送车辆的起点和终点都是配送中心；公式（15）表示63家社区便利店都能够被配送到而且只能够被配送到一次；公式（16）表示在一次配送的过程中，所有的配送车辆各自能装载的最大重量相加之和要大于63家便利店的需求量之和，并且一次能满足63家便利店的需求。

2 模型求解与结果分析

2.1 利用Selenium工具获取距离相关数据

利用Selenium工具进行网络爬虫，计算63个便利店和1个配送中心之间的距离，该方法就是先输入一个URL，然后网络爬虫可以按照刚才的命令和程序得到其他的URL，本文的距离查找过程是，先找到两个便利店的位置，然后将在百度地图里查找最短路线的编码输入进去，网络爬虫根据这个命令将其余便利店和配送中心的距离计算出来。采用这种方式的优点是可以准确得到配送中心和各个便利店之间的距离。

2.2 利用遗传算法优化配送路径

本文采用遗传算法和MATLAB软件来求解HFZ社区便利店配送路径模型，首先确定各项运行参数，包括群体的规模、变异的概率、交叉的概率、终止进化的迭代代数。其次再经过编码、确定初始种群、选择、交叉、变异、终止等步骤后，求得最优解。HFZ社区便利店配送路径优化模型求解的最终迭代收敛图如图1所示：

图1 优化过程图

图1是通过遗传算法和MATLAB软件求解配送路径优化模型进程图，从图1中可以看出曲线在迭代100次之前迅速下降，在这个过程中是不断淘汰较差的个体；在迭代到100~800次下降速度缓慢，在迭代到820次之后成一条水平的直线，说明算法在此时已经得到了最优解。即HFZ社区便利店在成本最低的目标下，表1得出的车辆的行驶距离、车辆的总装载量及车辆的装载率。

表1 最优的配送路径分布表

从表1可以看出，优化后的车辆装载率基本都达到了百分之八十，并且比较均匀。用遗传算法计算出配送的成本是每天2 980.5302元。

2.3 优化前后对比分析

优化前后数据对比如表2所示。

（1）配送总的行驶距离分析

配送路径优化之前每次行驶的总距离为272.89km，优化后的配送路径总距离是每次182.09km，配送前后每次配送距离相差90.8km，每次配送可以节省变动成本127.12元。

（2）车辆装载率分析

配送中心路线优化前配送路径是固定的8条，每条线路由一辆车进行配送，每辆车负责8~9个门店生鲜农产品的配送，所有车辆的平均装载率为83%，从这个平均数值来看，车辆的装载率较高，但是车辆的装载率很不均衡。优化后配送路径也是8条，每辆车的平均装载率也是83%。但是优化后的装载量符合整体的平均水平，且每辆车的装载率较均衡，避免了优化前2次配送问题的出现。

（3）车辆配送总成本分析

车辆配送的总成本包括固定成本、变动成本、货损成本、等待成本和惩罚成本，通过遗传算法进行优化后，每次配送可以节省总成本299.3元，每次成本降低10.04%。为后期业务的不断扩大减少了成本投入，提高了企业的效率，间接提高客户的满意度。

3 结束语

本文通过对HFZ社区便利店的实际情况进行分析，首先利用Selenium工具进行网络爬虫，查找63个便利店和1个配送中心之间的最短路线，然后构建考虑时间窗的生鲜农产品配送路径优化模型，得出了车辆配送路径的最优线路，最优路线每次配送节约了90.8km的路程，降低了299.3元的总成本费用，达到配送距离缩短，成本降低的双目标。