基于改进模拟退火算法的生鲜农产品配送中心选址

冉昊杰，王宏智

(青岛农业大学管理学院，山东 青岛 266109)

0 引 言

随着我国经济社会的发展，配送中心除承担基本物流职能外，还要越来越多地执行动态调度、信息筛选等职能。通常情况下，生鲜农产品的物流配送半径较小，但是其供应链及物流网络结构复杂，涉及的相关利益者较多。因此，实现生鲜农产品配送中心的最优选址决策，建立高标准、高效率的配送体系，以最快的速度将最好品质的生鲜农产品运送到超市大卖场等终端销售网点，对整个生鲜农产品物流系统的优化具有重要的现实意义。

近年来，我国诸多学者针对配送中心选址问题的算法求解及改进措施进行了积极的探索研究，从定性和定量方面提出了许多可供借鉴学习的解决方法。李晶晶[1]运用灰色模型分析新鲜度降低和打折销售对顾客购买需求的影响，建立以满足需求为前提、总成本最小为目标的冷链配送中心选址模型。裴时域等[2]采用一种部分流量再配置的新解产生方式，并基于改进的模拟退火算法对该问题进行优化求解，使其具有良好的求解能力。刘婧[3]采用与粒子群算法相结合的方式，改进模拟退火算法，使其收敛性能更佳，降低配送和仓储成本。

其中遗传算法为群体需求点搜索方式，在实际运算中算力规模较大。相比之下，模拟退火算法为个体需求点搜索，虽然算力规模较小，但会在算法后期产生大量无效搜索[4]。为探究生鲜农产品配送中心选址问题的更优思路，本文基于传统模拟退火算法，引入遗传算法解决方案，在改进原有算法搜索性能的同时保证搜索精度，使得在实际应用中做到更优的选址决策。

1 生鲜农产品配送中心选址模型建立

1.1 选址问题描述

生鲜农产品配送中心选址问题可描述为：某个地区范围内有若干个生鲜农产品需求点，且各需求点的需求情况确定，选取若干个配送中心备选点，并从中选取部分建立配送中心，以满足该地区需求点的需求，并实现包括货物运输固定费用以及生鲜农产品存储费用在内的总费用最少[5]。

本文所建立的生鲜农产品配送中心选址问题的数学模型假设为：运输费用与生鲜农产品运量情况成正比；配送中心仅建立在备选点当中；单个配送中心的容量足够满足所包含需求点的需求；各需求点的生鲜农产品需求量确定，并且在短期内不会产生较大波动。

1.2 构建选址模型

假设有n个生鲜农产品需求点，各个需求点的需求量已知，将t个生鲜农产品配送中心建立在m个备选地当中，实现生鲜农产品配送系统的总费用最少。可将多个生鲜农产品配送中心的选址问题表示成如下线性规划模型：

(1)

(2)

(3)

(4)

xij≥0,yj∈{0,1};i=1,2,…,m;j=1,2,…,n

(5)

式(1)表示配送中心到需求点总运输费用最小值的目标函数，第1项表示从配送中心到需求点的总运输费用，第2项表示配送中心的固定费用，第3项表示配送中心的存储费用，m为配送中心备选地个数，n为需求点个数，hij为从配送中心到目标需求点的单位运费，xij为配送中心为目标需求点供应的货物量，yi为在备选地i建立配送中心的情况[6]，Fi为在第i个备选点建立生鲜农产品配送中心的年固定费用，Ci为在第i个配送中心存储单位货物的存储费。约束条件式(2)表示各个需求点的需求量必须得到满足，Dj为第j个需求点的生鲜农产品年需求量。式(3)表示在备选地中选取若干建立配送中心，t为拟建配送中心个数。式(4)表示如果一个备选地为某些需求点提供货物，则需要在该地建立配送中心，其中M是一个很大的正数，表示该配送中心能够充分满足所包含需求点的需求量。式(5)表示变量的取值限制。

2 模拟退火算法优化改进

2.1 模拟退火算法原理

模拟退火算法是由固体退火原理产生，二者比较如表1所示。在模拟退火算法中，首先需要将固体加热融化为完全无序液态，此时固体中的粒子内能增大，处于自由运动态；随后逐渐降温，粒子运动逐渐趋于有序；当温度降低到结晶程度时，粒子内能减为最小，运动为围绕晶格点的规则振动。同时采用Metropolis准则，以概率接受新状态，得到非线性规划问题的优化解[7]。

表1 固体退火过程与模拟退火过程比较

2.2 模拟退火算法求解流程

2.2.1 求得局部最优解

从某个初始解出发，在约束区间中随机搜索，利用以概率接受新状态的准则，使无序逐渐向收敛过渡，实现局部最优解。算法准则规定系统从某一状态能量E1变化到另一状态能量E2时，能量变化概率情况如式(6)所示。

(6)

其中T为算法初始设定的模拟温度值。

如果新解比当前解更优，即E2≥E1，则接受该变化状态产生的新解；否则算法将基于Metropolis准则判断是否接受新解。该变化状态新解被接受的概率如式(7)所示。

(7)

2.2.2 控制相对最优解

通过逐渐减小控制参数的值，重复执行以概率接受新状态的算法准则，经过大量求解运算后，得到在系统约束范围内的相对最优解。

温度变量在算法准则中起到决定性控制作用：在温度逐渐升至最高时，系统可以接受任何情况下的恶化解；随着温度的逐渐降低，系统只接受较好情况下的恶化解；最后在温度趋于最低时，系统将不接受任何恶化解。

2.2.3 获得整体最优解

温度作为决定性的控制参数必须缓慢衰减，使系统通过一定次数的迭代运算，趋于相对稳定的能量分布态。当控制参数趋于最低时，模拟退火算法将求得非线性规划问题的整体最优解。具体流程如图1所示。

2.3 模拟退火算法求解模型过程中的特点

由上述求解过程可知，模拟退火算法求得整体最优解的可实现性高，缓慢降温过程有效避免了搜索过程陷入局部最优解的缺陷，以一定的概率接受恶化解，从而提高整体最优解的可靠性。

但同时求解过程存在较为明显的矛盾，主要体现在降温过程与解的质量之间。若要在算法后期进行更加有效的搜索，就必须减小退火温度的衰变值，根据搜索的需要表现出系统的分散性；而延长降温过程，会造成迂回搜索和局部极小解的问题[8]。

2.4 遗传算法原理及其求解模型过程中的特点

遗传算法是由生物进化原理产生的搜索算法，用于解决最佳化问题。在遗传算法中，需要在已知求解空间的前提下对可行解进行编码，并在可行解空间里随机生成初始种群，求出种群中各个体的适应度值，借助遗传的选择复制交叉变异等算子，依据适者生存的原理，引导搜索出全局最优解[9-12]。其良好的可扩展性和灵活性，能够与传统优化算法进行有机结合，形成混合算法，有效改进传统模拟退火算法的缺陷。

2.5 遗传算法与模拟退火算法的融合

本文将遗传算法与模拟退火算法融合，实现对模拟退火算法的改进。在退火过程的温度阈值搜索环节引入以配送中心为自然数编码的染色体个体，在此基础上创建符合约束条件的初始种群。

进一步，筛选出符合当前控制参数条件的染色体集。通过轮盘赌选择，选出若干个适应度大的个体作为父代，在此基础上进行交叉和变异操作，产生新一代种群P(gen+1)，保证优良父代的染色体片段遗传给后代的同时，变异跳出局部最优，实现整体最优，并输出退火过程的最优解。

3 算例分析

3.1 山东省A公司生鲜农产品配送中心选址问题

A公司是山东省内一家知名生鲜农产品企业，表2描述了该公司分布在省内的20个区域的需求点及其需求量。为提高配送效率，有效降低服务成本，该企业决定建立若干配送中心。由于其车辆设备等硬件需要，配送中心备选地分别是胶州市、平度市、莱西市、招远市、蓬莱市、栖霞市、诸城市、寿光市。从上述8个备选地中选择3个建立生鲜农产品配送中心，实现优化[13-20]。

表2 A公司生鲜农产品需求点及对应需求量

3.2 改进模拟退火算法选址过程

结合A公司实际的选址要求，运用改进后的模拟退火算法进行选址，选址具体过程如下。

3.2.1 获取基本数据

对A公司分布在山东省内的20个区域的需求点进行划分，将每个区域内客户的需求量汇总作为该需求点的运输量。再利用ArcGIS空间查询功能获得各需求点的经纬度坐标，建立平面直角坐标系如图2所示。

在实际选址过程中，生鲜农产品昂贵的存储费用是影响生鲜农产品配送中心运营成本的重要因素，主要包括货损费及仓库保管费等。且不同城市间运输情况不同，导致单位运费存在较大差异[21-23]。A公司各备选点存储费用及单位运费情况如表3和表4所示。

表3 A公司各备选点单位存储及固定费用

表4 A公司备选点到需求点单位运输费用表 单位：元/t

3.2.2 温度搜索环节引入染色体个体形成初始种群

本文在模拟退火算法的退火温度阈值搜索环节引入以配送中心为自然数编码的染色体个体，在此基础上创建符合约束条件的初始种群。在确定初始种群的过程中，N表示种群规模，Mb表示最大进化代数，pc表示交叉概率，pm表示变异概率，gen表示当前执行代数，C表示遗传代沟。

3.2.3 通过适应度函数选出父代个体

(8)

si+fi+tij-M(1-kij)≤sj

(9)

(10)

式(8)表示车辆的容积约束，qi表示单个车辆从配送中心i装载的货物量，kj表示向需求点j运输货物的车辆数，K表示配送中心可供运输货物的车辆总数。式(9)表示车辆配送的时间窗约束，si表示配送服务的开始时刻，sj表示配送服务的结束时刻，fi表示配送服务的持续时间，tij表示从配送中心i到需求点j车辆行驶所消耗的时间。kij表示车辆从配送中心i行驶到需求点j的情况判断，若有车辆从配送中心行驶到需求点，则kij=1；否则kij=0。M仍为一个很大的正数，当没有车辆对需求点进行配送服务时，车辆配送的时间窗约束仍成立。式(10)表示时间窗约束的惩罚适应度函数。其中，ai、bi表示客户规定的最早和最晚开始配送服务的时间。当配送服务在客户规定的最早与最晚服务时间内进行时，会产生相应的单位激励成本c1；当配送服务晚于客户规定的最晚服务时间时，会产生相应的单位惩罚成本c2。由此得到Ci为时间窗约束的惩罚成本适应度值。

3.2.4 通过轮盘赌选择进行顺序交叉和变异

进一步，筛选出符合当前控制参数条件的染色体集。通过轮盘赌选择，选出若干个适应度大的个体作为父代，并在此基础上进行顺序交叉操作，产生新一代种群P(gen+1)，保证优良父代的染色体片段遗传给后代。同时进行变异操作跳出局部最优，实现整体最优。

3.2.5 将基础数据代入算法模型，求得最优解

采用Matlab求解，得到3个配送中心分别应该建在招远市、诸城市和莱西市，最小总费用为1613952元。

根据计算结果，得出模拟退火算法求出的配送中心与需求点之间的最优分配结果，3个配送中心网点基本覆盖20个需求点，如表5所示。

表5 配送中心与需求点之间最优分配结果

3.3 改进前后模拟退火算法求解过程对比

算例仿真所在的实验平台为Win11系统，采用MATLAB R2021b软件进行实验运算，迭代总次数为2000次，输出改进前后的模拟退火算法总成本变化趋势图，即算法评价函数值曲线，如图3所示。其中纵坐标表示选址总成本的平均适应度值。

通过图3对比可以发现在算法运行早期，改进前后的算法表现同样高效，评价值下降平稳且较快；从第100次左右迭代开始，改进前的算法搜索过程出现明显断层停滞，说明迂回搜索和无效搜索已经出现，相比之下，改进后的算法搜索更为连续平滑；在第200次迭代时，改进前的算法搜索进入了相对瓶颈期，虽然在第500、第700和第1000次左右仍然寻找到了更优解，但与改进后算法搜索的有效性和连续性上存在较大差异；从第1200次迭代以后，改进前的算法评价函数值曲线基本保持不变，说明搜索进入无效阶段，而改进后的算法仍在保持有效搜索，直到第2000次算法停止迭代。

因此，模拟退火算法与遗传算法融合后，既保持了群体搜索方式在实际应用中的并行优势和极强的容错能力，又延续了单点搜索方式的更少算力，二者兼备使得改进后的模拟退火算法有效解决了降温过程与解质量的矛盾[24-26]，在保证更少迭代的基础上，减少模拟退火算法在迭代后期(1200次及以后)大量迂回搜索、无效搜索的问题。

4 结束语

本文通过构建生鲜农产品配送中心选址模型，借鉴模拟退火算法在已有的一些组合优化问题中的成功应用经验，分析模拟退火算法的实际求解流程。通过求解可知在生鲜农产品配送中心选址过程中，模拟退火算法作为单点搜索方式表现出算法简单，便于实现，全局整体最优求解的可靠性高，适用于复杂非线性优化问题的求解，同时也暴露出求解过程中体现在降温过程与解的质量之间的矛盾。因此，本文将遗传算法与模拟退火算法融合，实现对模拟退火算法的改进，在退火过程的温度阈值搜索环节引入以配送中心为自然数编码的染色体个体，筛选出符合当前控制参数条件的染色体集。进一步通过轮盘赌选择，选出若干个适应度大的个体作为父代，并在此基础上进行交叉和变异操作，保证优良父代的染色体片段遗传给后代的同时，变异跳出局部最优，实现整体最优。

通过对以山东省A公司的生鲜农产品配送中心选址问题为例进行仿真模拟，实验结果表明改进的模拟退火算法在实际应用中保持了遗传算法搜索的并行优势和极强的容错能力，又延续了模拟退火算法搜索的最优算力。由此可见，本文所提改进的模拟退火算法对于生鲜农产品配送中心选址问题的解决具有一定的实用价值。