基于模拟退火算法的电商物流配送问题研究

2021-04-23王旭颖杨金云倪秋铭刘朱丹

中国管理信息化 2021年7期

王旭颖，杨金云，陈哲，倪秋铭，刘朱丹

（徐州工程学院，江苏徐州 221008）

0 引言

徐州电商的发展，离不开供应商和消费群体。由于集聚效应，徐州新沂市墨河皮草电商产业园同时聚集了皮草企业、制造商与物流企业，拥有自己的产品展销区、仓储物流区、配套服务区、生产厂房区、创业孵化区。影响电商企业成本的重要因素从产业链中间环节，变得更加倾向于物流运输成本。因此，为了更快地将产品送达消费群体，墨河皮草产业园迫切需要改进产品运往皮草店铺和商城路径规划的问题。物流运输时间越长，需要支付运输人员的工资和产品所发生的损耗就越多，对电商园区的利润影响就越大，制订合理的运输方案有利于提高企业的成本控制能力。

1 电商产业园物流配送问题的描述

路径规划（TSP）问题的本质是从某点出发，依据某些准则，寻找到达终点的最优化路径。常用的算法有Dijkstra 算法、蚁群算法、遗传算法等。Dijkstra 算法只对当前做出最优选择，不能回溯，因此容易出现局部最优解。蚁群算法、遗传算法都具有全局优化的能力，但蚁群算法容易陷入局部最优，遗传算法的缺点是运算效率不高。模拟退火算法，也存在收敛速度慢、随机性大等缺点，但通过多次寻优，调整参数的方法，可以减少随机性对结果的影响。本文求解从徐州墨河皮草产业园出发，经过徐州都市圈内部分皮草商铺，最终回到徐州电商产业园的路径优化问题，通过运用百度拾取坐标系统，获得产业园和商铺点的经纬度信息，用A 标识皮草产业园，用B，C，…，U 标识各皮草销售点，通过软件绘制分布图如图1 所示。

2 模拟退火算法的物流配送路径优化

2.1 模拟退火算法的原理

模拟退火算法（SA）是一种适用于大规模组合优化问题的有效近似算法，来源于对固体退火过程的模拟。统计力学表明，在给定初始温度的条件下，通过将温度缓慢降低，微观粒子会在各个温度达到热平衡状态，当物体冷却到常温时达到基态，内能达到最小。模拟固体退火的过程，给定一个初始温度和初始解，随着温度的下降，每一个温度状态下，通过解的变换生成新的解。如果解的目标函数值小于前一个解，接受当前解；否则，以概率接受新解。最终的解是迭代寻优的结果。模拟退火算法以概率突跳性，能够跳出局部最优陷阱，找到全局最优解。模拟退火算法依据Metropolis 接收准则接受新解，而不是使用完全确定的规则。它构成了模拟退火算法退火过程的基础。当固体从状态i 经过降温变化到状态j，它所具有的能量从E（i）变化到E（j）。显然，如果E（j）＜E（i），接受新的状态j。否则，依据概率P 接受新解。

其中，K 是物理学波尔兹曼常数，T 是固体的温度。

这种概率，在路径规划的问题中，就是当新解的目标函数值小于原来的解的函数值，新解仍被接受的概率。以x 表示温度T 下的一个解，通过退火，可以生成一个新解x′。那么，接收x′的概率为：

2.2 模拟退火算法模型的建立

2.2.1 目标函数

首先，规定解空间。对销售点B，C，U 重新进行编号（2，3，…，21），A 点为产业园，既是起点也是终点，将它进行两次编号，记为1 号和22 号，以便于程序计算。问题转化为求解从1 出发，走遍所有中间点，到达22 的一个最短路径。本文通过运用百度拾取坐标系统，获得产业园和商铺点的经纬度信息。由于，本文选取的点的范围在徐州都市圈，两点之间的曲线距离可以近似看作直线距离。用k1和k2分别表示经度、纬度和千米的换算系数，将经纬度转换为千米。通过改进坐标距离公式计算距离：

计算得到皮草产业园和所有销售点中，任意两点间的距离，构成一个对称矩阵D=（dij）22×22。规定z1，z2，…，z22中，z2，z3，…z21，是由2～21 随机打乱得到的一组数，则dzizi+1表示所有可能路径中，第i 个和第i＋1 个经过的点间的距离。目标函数为运输经过所有目标的路径长度最小：

2.2.2 模拟退火算法实现过程

Step 1 初始化

通过MATLAB 随机模拟数给定初始路径，计算得到初始路径长度。设定初始温度T（0）=1。

Step 2 产生新解

运用变换法，任选序号a，b（a＜b），交换a 和b 之间的顺序，得到新的路径：

Step 3 判定标准

新路径与原路径长度的差可以表示为：

当路径差Δf<0 时，用新路径代替原路径。否则，以概率exp（-Δf/T）接受新的路径。

Step 4 重复步骤2 和步骤3，进行迭代。

Step 5 结束条件

选用降温系数α，令T←αT，得到新的温度。当温度降至终止温度，算法结束，输出当前状态。

3 MATLAB 模拟退火算法求解

本文以徐州都市圈为例，运用模拟退火算法，对最优路径进行选择，用MATLAB 软件计算结果。本文研究的是同一起讫点的电商物流配送路径优化问题，实际上，就是从徐州墨河皮草产业园出发经过徐州都市圈各省市部分皮草商铺和商城，最终回到产业园的问题。本文首先通过百度坐标拾取系统，拾取其中20 个皮草商铺和商城的坐标，并对其进行编号，如表1 所示。

表1 徐州都市圈个皮草经营点经纬度坐标

由于通过坐标拾取系统得到的地点坐标的单位是经纬度，与实际生活使用的距离单位不符合，不便于求解分析。本文通过MATLAB 计算得到范围内近似经度换算系数k1=92.164 4 千米／经度，纬度换算系数k2=111.177 5 千米／纬度。于是根据改进的距离公式，可以得到各邻接点的距离矩阵D=（dij）22×22：

模拟退火算法的初始温度参数不妨假设为1，温度变化系数α 一般取0.95～0.99 之间，本文取变化系数为0.99。根据若干次对初始温度和终止温度的调整，最终得到初始温度为2 200，终止温度为9.908 2×10-4。对徐州都市圈的实例进行1 455 次M ATLAB 仿真计算。最终计算得到路径长度最小值为913.822 1千米，最终最短路径为A-N-M-O-K-L-J-R-G-I-D-F-C-B-QP-U-E-H-T-S-A。在MATLAB 运行计算结果过程中，迭代具体变化过程见图2。

通过MATLAB 运行仿真计算得出最优路径坐标，如图3所示。

图2 迭代变化过程图

结合模拟退火算法结果和图中坐标，可以得出从徐州新沂市墨河皮草产业园出发的车辆配送货物的顺序：新沂市墨河皮草产业园—墨尚皮草—海州海宁皮草特卖—贵夫人—优尚皮草行—泗阳海宁皮草—泗洪海宁皮草城—名媛皮草—睢宁海宁皮草—邳州海宁皮革城—国亚皮革店—润龙裘皮—云龙海宁皮草—徐州海宁皮草城—埇桥海宁皮草—华东濉溪皮革—名牌之家经典皮草行—梦源皮革—东方皮草—三星皮草行—丽豪皮草行—新沂市墨河皮草产业园。