基于遗传算法的冷链物流节点选址研究

      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)选择算子。选择操作是建立在群体中个体的适应度评估基础上的，适应度值越小，该个体被遗传到下一代群体中的概率也就越大。本文采用精英法进行染色体的选择，即将上一代中最好的一个或多个个体直接加入下一代中。再按轮盘赌方式进行选择，这样可以保证遗传算法的收敛性。