基于自适应遗传算法的生鲜产品冷链物流配送中心选址研究

张亦弛，刘晓佳 （集美大学航海学院，福建 厦门 361000）

0 引 言

在一个物流网络系统中，配送中心是非常重要的基础设施，配送是最末端的环节，也是极为关键的环节。配送中心发挥着承上启下的作用，对上承接来自发件网点货物的集运任务，对下承接收件网点的配送运输任务，其选址结果将会对配送路径的规划、运营成本、配送效率等产生直接的影响。由于生鲜冷链产品具有价值高、需求大、易腐败、不宜长时间储藏的特点，所以对于生鲜冷链产品来说，其配送中心选址就显得尤为重要。

张于贤等人[1]利用DEA 方法对已有配送中心的效率进行评估，根据评估的结果代入选址分析模型中，得到物流配送中心再选址的DEA 评估规划模型，以配送收益与物流成本之差作为目标函数，以供需均衡关系、配送中心流出量与流入量平衡、选址变量与流量内在联系构建约束条件，通过算例并借助于MATLAB 软件验证了模型的有效性。宋瑞敏等人[2]提出一种基于布谷鸟搜索算法求解平面选址问题，仿真结果表明，该算法具有平衡全局优化与局部搜索的优点，但不适用于多目标选址。生力军[3]将量子进化算法融入经典粒子群算法中，采用量子理论中独有的叠加态和概率幅特性，粒子最优位置的搜寻采用量子自旋门完成，粒子位置的多样性变异采用量子非门完成，以免出现局部最优解和早熟收敛缺陷。李晶晶[4]运用灰色GM 1,（ ）1 模型，预测太原市某地区未来五年的需求量，并分析降价销售对顾客购买需求的影响，建立以满足需求为前提、总成本最小为目标的冷链配送中心选址模型，并用lingo 软件求解。冉昊杰等[5]将遗传算法与模拟退火算法融合，实现选址过程的整体优化。这些研究中，大多对智能算法进行了改进，使其更加适用于选址问题。

在上述学者研究内容的基础上，本文将不同地段的建设价格、生鲜产品的运输途中变质速度等因素考虑在内，建立生鲜产品冷链物流配送中心选址模型，并采用自适应的遗传算法对模型求解。分析遗传算法的原理和步骤，针对算例进行编码，通过仿真，得出配送中心的选址与分配。

1 模型假设与参数设定

1.1 模型假设

（1） 一个生产基地可以给多个配送中心供货；

（2） 一个配送中心只能接收一个生产基地的货物；

（3） 一个配送中心可以服务于多个需求网点；

（4） 一个需求网点只能被一个配送中心服务；

（5） 生产基地的供货量不超过配送中心仓储的最大容量；

（6） 配送中心的容量总和大于各需求网点的总需求量；

（7） 运输距离用单位运输成本体现，二者线性相关；

（8） 部分受运输储存影响的商品仍可以降价出售。

运输过程如图1 所示。

图1 生鲜产品的运输基本流程

1.2 变量设定

本模型的变量及其释义如表1 所示。

表1 模型变量及其释义

2 模型构建与算法

2.1 模型假设

本生鲜产品冷链物流配送中心选址模型涉及生产基地、配送中心、各需求网点这三层结构；模型目标是使得总成本最低，所考虑的3 个影响因素分别是：固定成本、运输成本、变质成本。

（1） 固定成本：固定成本是冷链物流配送中心选址中起决定性作用的因素，它主要包括建设配送中心的土地费用和建设费用、冷链设备等大型机器的购置费用、配送中心每个运营周期所产生的维护费用。同时，地理位置不同，地价也会改变。交通便利，地理位置优越，环境良好的场地价格会高，反之则低。本文中固定成本由设备运营成本和地段建设成本共同决定，二者都与配送中心的容量有关。引入θj作为反映地价高低的系数，引入b作为反映购置冷链设备和维护的成本系数，则配送中心的总固定成本可用如下公式表示。

（2） 运输成本：运输分为两个阶段，一是从生产基地到配送中心；二是从配送中心到各个需求网点。本文单位运输成本指每单位重量的生鲜商品的运输成本，运输距离越远，则单位运输成本越高。在确定运输线路的距离且不考虑交通拥堵和交通事故的情况下，假设运输成本与运输货量成正比，可以得到如下公式。

（3） 变质成本：生鲜商品的新鲜度是其最重要的属性之一，直接影响商品的价格。在储存和运输过程中，生鲜产品会因时间、温度、挤压等因素而不再新鲜，甚至会变质。对于未完全腐败，仍可以降价出售的生鲜产品，可以用变质成本来计算其损耗。假设变质成本与运输时间有关，根据文中的假设7，两地之间的单位运输成本越高，两地之间的距离就越远，从而运输的时间就越长，商品越容易变质。因此变质成本与单位运输成本相关。生鲜产品变质对成本损耗是实时变化且没有特定标准来衡量的，本文引入变质成本系数来表示生鲜产品的新鲜度随运输距离长短而变化的速率。

其中：q为变质成本系数。根据假设，对于新鲜度明显降低的商品，其价格会降低，成本损失如下：

综上所述，本模型的总成本C是C1,C2,C3之和，结合模型成本最小化的目标，可以得到如下函数：

2.2 模型算法

自适应遗传算法（Adaptive Genetic Algorithm，AGA） 是对基本遗传算法的一种改进，它通过对遗传参数的自适应调整，大大提高了遗传算法的收敛精度，加快了收敛速度。自适应遗传算法在保持群体多样性的同时，保证了遗传算法的收敛性。自适应遗传算法的遗传参数是自适应的，提高了基本遗传算法的收敛速度和收敛精度。该算法的实现步骤如下：

Step1：编码。将问题的候选解用染色体表示，实现解空间向编码空间的映射过程。将空间的决策变量转换成由基因按一定结构组成的染色体。编码方式有很多，如二进制编码、实数向量编码、整数排列编码、通用数据结构编码等。本文将采用二进制编码的方式，将十进制的变量转换成二进制，用0 和1 组成的数字串模拟染色体，可以很方便地实现基因交叉、变异等操作。

Step2：种群初始化。产生由n条染色体（Chromosome） 组成的初始群体。群体（Population） 的规模（即n值） 设置的过小很可能会导致过早收敛，最终不能获取到全局最优解；而如果群体规模设置过大又会影响计算时间。

Step3：计算个体适应度。利用适应度函数（Fitness Function） 计算各个个体的适应度大小。适应度函数值越大，则种群中优良基因作为父代基因遗传到下一代的可能性越大；否则可能性越小。目标函数为最小时，建立如下与目标函数之间存在映射关系的适应度函数：

Cmax为f（x）的最大值，并且会随着遗传的代数不断变化。

Step4：选择、交叉和变异。通过选择、交叉、变异，产生出代表新的解集的群体。

（1） 选择（Selection）：根据个体适应度大小，按照优胜劣汰的原则，淘汰不合理的个体。最常见的选择方法是轮盘赌法，假设种群数目n, 某个个体其适应度为fi, 则其被选中的概率为：

其中：n为种群规模，fi为个体i的适应度。

（2） 交叉（Crossover）：将交叉算子作用于群体，对选中的成对个体，以某一概率交换它们之间的部分染色体，产生新的染色体，也叫做基因重组。如图2 所示，即是最简单的一种交叉。

图2 遗传算法中的交叉算子示例

交叉的概率决定着交叉算子操作效果的好与坏。交叉概率如果很大，会使得模型收敛速度过快，从而导致局部收敛；交叉概率如果很小，则收敛速度又会过慢。因此，本文引入自适应交叉算子操作，计算过程中交叉概率会随着适应度函数值的不同而自动调整，其计算公式如下：

其中：Pc为自适应交叉概率，fmax为群体中个体最大的适应度函数值，favg为每代群体的平均适应度函数值，f为产生交叉的两个个体其中一个个体为较大的适应度函数值，C1,2为区间（0,1）的常数。

（3） 变异（Mutation）：将变异算子作用于群体，对选中的个体，以某一概率改变某一个或一些基因值为其他的等位基因，类似于基因突变。如图3 所示，即是最简单的一种变异。

图3 遗传算法中的变异算子示例

当变异概率过小时，不利于染色体新个体结构的产生；当变异概率过大时，染色体结构遭到破坏的可能性会增大，遗传算法搜索的有效性随之降低。针对变异算子操作中的寻优问题，本文引入自适应变异算子操作，其计算公式如下。

其中：Pm为自适应变异概率，C3,C4为区间（0,1）的常数。

Step5：循环操作并判断终止。当达到预先设定的最大迭代次数Tmax时，终止迭代。

3 算例分析

为了验证改进的自适应遗传算法模型在生鲜冷链物流配送中心选址中的可靠性，本文结合算法模型设计了具体的算例，通过对算例的求解来验证遗传算法模型在配送中心选址问题研究中的有效性和实用性。以厦门市某地为例，设生产基地共有3处，分别记为A1,A2,A3；可供选择配送中心地址共有6 处，分别记为B1,B2,B3,B4,B5,B6；需求网点有12 处，分别为C1,C2,C3,C4,C5,C6,C7,C8,C9,C10,C11,C12。可供选择的配送中心的容量和固定成本如表2 至表5 所示：

表2 可供选择的配送中心的固定成本和最大容量

表3 各需求网点的需求量

表4 生产基地到配送中心的单位运输成本

表5 配送中心到需求网点的单位运输成本

设变质成本系数q=0.005，生鲜产品单价p=25，采用自适应遗传算法，运用MATLAB 编程进行仿真, 具体参数为：初始种群规模N=100，设置最大迭代次数Mmax=1 000，基因交叉的概率Pi=0.7，基因变异的概率Pc=0.07，经过求解，得出的结果如图4 和表6、表7 所示。

图4 MATLAB 仿真最优解变化图

表6 生产基地到配送中心的供货仿真结果

表7 生配送中心到需求网点的分配仿真结果

配送中心B1为需求网点C1,C4,C6提供服务，配送中心B2为需求网点C7提供服务，配送中心B4为需求网点C5,C8,C9,C12提供服务，配送中心B6为需求网点C3,C10,C11提供服务，配送中心B3,B5将不被考虑。遗传算法迭代了150 次左右时，解已经趋于稳定。

4 结 论

本文采用自适应遗传算法对生鲜产品冷链物流配送中心选址的问题进行了研究，将影响选址的成本因素分为固定成本、运输成本和变质成本，建立了生鲜产品冷链物流中心选址模型并用自适应遗传算法进行求解，仿真结果表明该模型和算法可以较好地应用于实际选址问题当中。在构建最小成本目标函数时；地段价格系数来体现不同地段建设配送中心的地价不同；用单位运输成本来体现运输距离和运输时长；引入变质成本系数来控制生鲜产品在运输途中变质造成损失的速率。

由于配送中心选址是一个相对多样且复杂的研究问题，本文在理论和实例研究部分还有诸多不足，有待进一步深入研究。