基于遗传算法的冷链物流节点选址研究，本文主要内容关键词为：节点论文,算法论文,物流论文,冷链论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 引言
随着人们生活品质的提高，冷冻（藏）食品的需求量大幅增长，冷链物流随之兴起。目前，欧美发达国家已经基本建立起了高效冷藏链，然而我国尚缺乏独立封闭的冷链体系，国内80%以上的生鲜食品运输还是采用常温手段，造成大量损失。而在冷链体系的建设中节点选址是其中关键的一环。国内关于冷链物流的节点选址研究还处于起步阶段，虽然已有一些学者进行了探索，如姜大立，沈尔康于1998年建立了易腐物品的配送中心选址模型并采用遗传算法进行求解，此后，姜大立又采用同样的方法求解易腐物品配送中心的连续选址模型，但他们的研究都建立在物品的腐败率与时间呈线性关系的基础上[1-3]。事实上，根据T.T.T.理论（1958年，美国的阿萨德等人提出了冷冻食品品质保证的时间、温度、耐藏限度的概念即time-temperature-tolerance，简称T.T.T.），食品的腐败率与时间并非简单的线性关系，Guimei Zhang和Walter Habenicht虽然注意到了这个事实，但他们采用的是禁忌搜索算法来优化冷链物流网络结构[4]。禁忌搜索算法与遗传算法相比用于大规模、多阶段物流网络尚不成熟[5]。
针对上述已有研究的不足，根据T.T.T理论，在假设温度不变的条件下，推导出了食品腐败率与时间的非线性关系。并在总结前人研究成果的基础上，建立了冷链物流网点布局模型。此外，由于遗传算法具有较强的全局优化搜索能力、运算简单、收敛速度快、鲁棒性强等优点，已经广泛应用于各个领域。在物流网络设计方面，文献[6-10]都表明了遗传算法十分适合于求解多阶段、多层次复杂物流网络模型。所以，本文首次提出了采用遗传算法来求解冷链物流节点选址问题。
2 变质率与时间关系的推导
在冷链中即使是保持最适宜的温度，产品质量也会随着时间的推移下降。质量影响反应动力学大体上可以用化学反应动力学来描述。根据传统的T.T.T.理论，食品品质的腐败与时间和温度有关系。本文在T.T.T.理论基础上，通过总结冷链各个环节中的产品变质情况来确定产品的变质率。全变质率lqm/%可以用质量变化量与初始质量的比来确定[4]，即
图1 冷链物流网络拓扑结构
给定某一地区所有需求点（用户）的地址集合，要求从中选出一定数目的地址建立配送中心，从而建立一系列的配送区域，实现各个需求点的配送，使得在选出点建立的配送中心与各需求点形成的配送系统总配送费用最少。为了便于建立模型，作一定的假设，假设系统满足如下条件：①仅在一定的被选范围内考虑设置新的配送中心；②运输费用与运量成正比；③产品从工厂到用户的运输和仓储过程中温度保持不变；④一个需求点仅由一个配送中心或工厂供应；⑤配送中心容量可以满足需求；⑥各资源厂的供给量和各需求点的需求量一定且为已知；⑦所有点间运输速度一样，均为常数。模型如下
5 模型求解
上述问题属于大规模冷链物流网络设计问题，分为两个子问题，配送中心的选址问题和根据就近原则对客户进行分派，具有NP-Hard性质，本文采用遗传算法来求解，通过Matlab编程来实现，其算法流程，如图2所示。
1)二进制编码。染色体的基因位数为待选配送中心位置数。若基因位的值为0，则表示该位置未被选中；若基因位的值为1，则表示该位置被选中。
2)初始化。包括选址的初始化和在选址条件下的分派优化问题。在第i个染色体中，从k个待选地中随机选择2或3个配送中心，然后采用就近原则把客户分派给选中的配送中心或工厂。并保证配送中心的流入量等于流出量。
3)计算适应度值。适配值函数用于对各状态的目标值作适当的变换，用以体现各状态性能的差异。本文采用总物流费用作为适应度值进行评价，即用式(7)计算，相关的系数由费用计算公式和统计数据获得。
图2 GA方法求解程序
4)选择算子。选择操作是建立在群体中个体的适应度评估基础上的，适应度值越小，该个体被遗传到下一代群体中的概率也就越大。本文采用精英法进行染色体的选择，即将上一代中最好的一个或多个个体直接加入下一代中。再按轮盘赌方式进行选择，这样可以保证遗传算法的收敛性。
5)交叉算子。寻优的搜索过程主要通过交叉算子来实现。对于只选2个配送中心的染色体，本文采用二进制加法与错位交叉相结合产生后代，如：父代；A：100100，B：101000则二进制加法产生后代为001100；父代：A：110000，B：001100则错位交叉产生后代为101000、100100、011000和010100。
对于选2个以上配送中心的染色体，采用双断点交叉。为保证染色体的合法性和可行性，即保证双亲的第一段中取值为1的基因总数保持不变，如表1所示。
6)变异算子。变异算子目的是改善遗传的局部搜索能力，维持群体的多样性，防止出现早熟现象。本文的变异操作对基本变异(Simple Mutation)作了一些改动，即用在二进制码中常用的变异方法即随机选择变异位，然后取反。
6 算例
本文设计了3个工厂、8个备选配送中心和100个顾客需求点的算例。各工厂的坐标和产量，如表2所示，各备选配送中心的坐标和固定建设费用，如表3所示，部分顾客的坐标和需求量，如表4所示。
参数选取如下：种群规模16，进化代数10，变异概率0.005，迭代次数200，系数A=-0.004，运输费率C=1，仓储费率Ck=5，惩罚系数c=10。
进化后最优解为选择第1号和第8号配送中心，其中，第1号配送中心的量为134.06，由工厂A配送；第8号配送中心的量为133.82，由工厂C配送，工厂B直接配送到客户的量为42.40。图3表示的是200代的迭代过程中每一代目标函数的平均值。从图3可以看出第127代的函数平均值最低，为767300。
系统总费用为759590，比初始种群平均值777940节省了18350。可见，通过遗传算法对冷链物流网点进行布局能节约物流系统费用，具有重要意义。
7 结语
根据传统的T.T.T理论，在假设温度不变的条件下，推导出了食品腐败率与时间的非线性关系。建立了冷链物流节点选址模型，提出了采用遗传算法来求解冷链物流节点选址问题，之后通过一定规模的算例表明，采用遗传方法可以有效解决冷链物流节点选址问题，并得到了满意的结果，对冷链物流体系的构建具有重要的理论和实践意义。
图3 遗传算法的Matlab优化结果