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

基于遗传算法的冷链物流节点选址研究 基于遗传算法的冷链物流节点选址研究王敏/毛超/杨葱葱【论文专题栏目】物流管理【论文网络来源】【论文期刊期数】2010年03期【论文期刊来源】《科技与管理》(哈尔滨)2009年6期第72～75页【英文标题】A Study on Location of Cold Chain Logistics Node Based on Genetic Algorithms【作者简介】王敏(1984-　)，女，湖南大学中德交通运输与物流研究所，工商管理学院硕士研究生；毛超(1984-　)，男，湖南大学中德交通运输与物流研究所，工商管理学院博士研究生；杨葱葱(1986- )，女，湖南大学中德交通运输与物流研究所，工商管理学院硕士研究生（湖南　长沙　410082）内容提要】 根据传统的T.T.T.理论，在假设温度不变的条件下，推导出食品的腐败率与时间的非线性关系，并在此基础上建立了惩罚函数和冷链物流节点选址模型采用遗传算法对模型进行求解，通过一个算例证明了遗传算法可以有效解决冷链物流节点选址问题According to the classic T.T.T. theory, the non-linear relationship between rate of food corruption and time is introduced under the condition of constant temperature. Based on the previous assumption, a penalty function is introduced and a model of node location of cold chain logistics is set up. The genetic algorithm is applied to solve the model and a computational experiment is adopted to prove GA can solve the problem effectively. 【关 键 词】冷链物流/遗传算法/T.T.T.理论/惩罚函数cold chain/genetic algorithm/T.T.T. theory/penalty function1　引言随着人们生活品质的提高，冷冻（藏）食品的需求量大幅增长，冷链物流随之兴起。

目前，欧美发达国家已经基本建立起了高效冷藏链，然而我国尚缺乏独立封闭的冷链体系，国内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优化结果 【参考文献】 [1]姜大立，杜文，张拥军.易腐物品物流配送中心选址的遗传算法[J].西南交通大学学报，1998,33(4):425-429.[2]沈尔康.易腐物品配送中心选址模型及遗传算法[J].铁道物资科学管理，1998,16(5):35-37.[3]姜大立，杨西龙.易腐物品配送中心连续选址模型及其遗传算法[J].系统工程理论与实践，2003(2):62-67.[4]ZHANG G, HABENICHT W, SPIEβ W E Ludwig. Improving the structure of deep frozen and chilled food chain with tabu search procedure[J]. Journal of Food Engineering, 2003,60(1):67-79.[5]MICHEL L, HENTENRYCK P V. A simple tabu search for warehouse location[J]. European Journal of Operational Research, 2004,157(3):576-591.[6]SOURIRAJAN K, OZSEN L, UZSOY R. A genetic algorithm for a single product network design model with lead time and safety stock considerations[J]. European Journal of Operational Research, 2009,197(2):599-608.[7]KO H J, EVANS G W. A genetic algorithm-based heuristic for the dynamic integrated forward reverse logistics network for 3PLs[J]. Computers & Operations Research, 2007,34(2):346-366.[8]GEN M, SYARIF A. Hybrid genetic algorithm for multi-time period production/distribution planning[J]. Computers & Industrial Engineering, 2005,48(4):799-809.[9]谢如鹤.遗传算法在逆向物流网络规划设计中的应用[J].武汉理工大学学报：交通科学与工程版，2007(5):902-905.[10]田青，郑力，齐二石，等.大规模物流网络的组合遗传算法研究[J].工业工程与管理，2006(4):46-49.[11]LABUZA T P. The Search for Shelf Life[J]. Food Testing Analysis, 2000(5):3-6.^  （本文来源：《论文资料库》 htt。