基于模拟退火算法的泗阳鲜桃物流配送路径优化研究

文/王淋 梁子婧 马卫东

1.引言

“互联网+”时代背景下，电商行业蓬勃发展，人们对农产品需求日益上升。文中运用模拟退火算法对农产品的物流配送车辆进行路径优化，减少物流车辆行驶总路程，节省物流运送时间，以达到节能减排、提质增效的目标。

2.模拟退火算法模型

2.1 模拟退火算法介绍

模拟退火法是一种非常典型的概率模拟算法，是基于Monte-Carlo迭代求解策略的一种寻优算法[2]。模拟退火算法通过模拟热力学当中固体退火过程与一般组合优化问题之间的相似性结合概率突跳性是局部最优解能概率性地跳出并趋于全局最优的模式[3]。

2.2 模拟退火算法模型构建步骤

Step1：初始解采用随机的方式产生，记为x0，然后令xbest=x0，并计算目标函数值E（0x0）；k=0；t0tmax。

Step2:设置一个初始温度，记为T0将S记为迭代起点，令迭代次数i=1，如果在这个温度到达内循环的时候停止，则直接到Step3；如果当这个温度到达内循环的时候没有停止，则从目前最优解xbest的邻域N（xbest）中随机选择一个变量作为xnew，除了计算新的目标函数值E（new）外，还要计算目标函数值的增量ΔE=E（xnew）。若计算出来的结果是 ΔE＜0，则 xbest=xnew；否则ΔE＞0；当 exp（-ΔE/tk）＞时，xbest=xnew。

Step3：有 tk+1=d（tk）；k=k+1，如果达到设定的条件则终止计算，如果没有达到则回到Step2。输出最优解为xbest；否则，回到step2。

2.3 算法路径求解步骤：

设解空间为S，S是恰好遍访每个销售点一次的所有回路，是（1，…，n）的所有循环排列的集合，S中的成员记为（w1，w2…，wn），并记作 wn+1=w1。初始解可选的范围为（1，…，n）。此时的目标函数就是访问完所有销售点的总路程，也称为代价函数，需要做的就是求此代价函数的最小值。新的解随机产生在1和n之间，记为 k和 m，若 k＜m，则将（w1，w2，…，wk，wk+1，…，wm，wn）变为（w1，w2，…，wm，wm-1，…，wk+1，wk，…，wn）；如果是 k＞m，则将（w1，w2，…，wk，wk-1，…，wm，wn）变为（wm，wm-1，…，w1，wm+1，…，wk-1，wn，wn-1，…，wk）。

2.4 算法实现的技术问题

（1）解的形式和邻域结构

邻域的构造直接决定解的表现形式，比如：（f x）=x2，0≤x≤100，x∈Z的解可以采用0-1编码。

（2）状态转移概率(接受概率)

状态转移概率是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率，简而言之就是接受一个新的解，作为当前的解的概率。状态转移概率与当前的温度参数T有关，概率随温度下降而减小；一般采用Metropolis准则：

（3）初始温度

通过实验得知，当设置的初始温度越大，获得高质量解的概率就会越大，但是计算的时间也会大大增加；当初始温度过低时，则会使算法过早的结束，落入局部最优陷阱。因此，初始温的确定应折中考虑优化质量和优化效果。t0=Kδ，K为充分大的数；δ=max{f（j），j∈D}-min{f（j），j∈D}，在实际计算中，可以令K等于整数试验值。

（4）冷却进度T(t)

冷却进度表是指一个高温的状态T0冷却至低温的状态整个过程的降温管理表。需要综合考虑解的质量和算法运算速度，经典模拟退火算法的降温方式为快速模拟退火算法的降温方式为（为保证较大的搜索空间，α一般取接近于1的值）

常用的两种简单下降方式：tk+1=αtk，其中0＜α＜1其中K为算法温度下降的总次数

（5）内循环终止准则。内循环终止条件也被称为Metropolis抽样稳定准则，作用是决定在各种温度下产生的候选解的数目。常用的方法：①固定长度：在每一个温度选取相同的迭代步数，步数的选取与问题有关，一般情况下采用与邻域的大小直接相关的准则。②：伴随着温度的下降，就要将同一个温度的迭代步数增加。

（6）外循环终止准则。外循环终止准则就是整个算法的终止条件，常用的包括:①零度法:设置一个终止温度的阈值，将阈值设为：小正数ε；②循环总数控制法：；③基于不改进规则的控制法:算法搜索到的最优值连续若干步保持不变。根据上述的模拟退火算法模型，将各项指标设置并带入算法，利用算法来对泗阳鲜桃物流车辆的路径进行优化[4]。

3 实例分析

3.1 销售点分布统计。本文主要讲述泗阳鲜桃在宿迁市宿城区各个超市站点路径规划问题，文章主要选取了宿城区客流量较大的10个超市（图1、表1所示）来进行举例分析。

图1 泗阳鲜桃宿城区10个销售点分布图

表1 泗阳鲜桃宿城区10个销售点地址统计表

3.2 销售点经纬度

现选取这10个销售点的经纬度如表2所示，并计算得出这10个地方两两之间的距离。这10个销售点用序号1到10依次表示。[5]。

表2 泗阳鲜桃宿城区10个销售点经纬度统计表

3.3 销售点距离计算

除了需要各个销售点的经纬度之外还需要计算这10销售点任意两点之间的距离。设：1销售点的坐标为(x1，y1)，2销售点坐标为(x2，y2)。地球半径为R=6370km，则两点距离为d=R·arccos[cos（y1）·cos（y2）cos（x1-x2）+sin（y1）·sin（y2）][5]。

表3 10个销售点任意两点之间的距离

此时解空间S里的n=10，集合里面所有成员，解空间S就物流车辆走遍每个销售点的所有路径。基于模拟退火算法得出泗阳鲜桃物流运输车辆优化前后对比[6]。（如图2、表4所示）

表4 优化前后路径信息

图2 泗阳鲜桃配送路径优化前后对比

通过表4可以轻松得知泗阳鲜桃优化前的配送总路程为213km，优化后为175km。优化后比优化前节省路程38km,运送泗阳鲜桃的物流车辆能更快完成运送任务的同时还节省了物流运输成本[7]。

4.结论与展望

文章通过对泗阳鲜桃从产地向各销售点之间配送的数据查找和收集，了解到在配送上面产生了较大物流运输成本。首先对模拟退火算法进行了步骤分析进而利用图表分析法清楚地表达出算法优化前后的对比分析。最后利用了模拟退火算法来对泗阳鲜桃的配送路径进行优化，选择最优、最短、最省的路径来对泗阳鲜桃进行配送。

引用出处

[1]张欣,梁子婧,蔡志群,等."互联网+"背景下农村快递发展的影响因素与对策研究--以苏北地区为例[J].2021(2017-16):137-138.

[2]Kwanho Kim,Hyunjin Kim,Sang-Kuk Kim,Jae-Yoon Jung.I-RM:Anintelligentrisk managementframework for context-aware ubiquitouscoldchainlogistics[J].ExpertSystems With Application,2016,46(46).

[3]Giosa.New assignment algorithms for the multi-depot vehicle routing problem[J].Journal of the Operational Research Society2017

[4]姚新,陈国良.模拟退火算法及其应用 [J].计算机研究与发展,1990(7):1-6.

[5]杨真真,方秀男.模拟退火算法及实例应用 [J].中国科技信息,2021(15):2.李伟，杨延梅，刘汉英，等.城市末端物流配送路径优化研究[J].铁道货运，2019，37(03)：5-10.

[6]裴小兵,贾定芳.基于模拟退火算法的城市物流多目标配送车辆路径优化研究[J].数学的实践与认识,2016,46(2):105-113.

[7]杨志清.城市快递配送条件下的多目标车辆路径优化研究[D].哈尔滨工业大学，2015.