免疫算法在物流配送中心选址中的应用.doc

1、免疫优化算法在物流配送中心选址中的应用摘 要：针对物流配送中心选址问题，以物流成本为目标函数，采用免疫优化算法对配送中心进行选址。通过全国31城市的物流需求点实例进行论证，仿真结果表明，该方法能够快速有效地求得物流配送中心选址问题的全局最优解。关键词：物流配送中心；免疫优化算法；选址Abstract： The immune optimization algorithm is proposed to optimize the selection of logistics distribution center，which takes the logistics cost as objective

2、 functionConducted feasibility studies through the 31 city nationwide logistics demand point，the simulation results show that the method can rapidly converge toward the optimal solutionKey words： Logistics distribution center；Immune optimization algorithm；Location selection0 引言随着世界经济的快速发展以及现代科学技术的进步

3、，物流业作为国民经济的一个新兴服务部门，正在全球范围内迅速发展。物流业的发展给社会的生产和管理、人们的生活和就业乃至政府的职能以及社会的法律制度等带来巨大的影响，因此物流也被认为是国民经济发展的动脉和基础产业，被形象地喻为促进经济发展的“加速器”。在物流系统的运作中，配送中心的任务就是根据各个用户的需求及时、准确和经济地配送商品货物。配送中心是连接供应商和客户的中间桥梁，其选址方式往往决定这物流的配送距离和配送模式，进而影响着物流系统的运行效率。另外，物流中心的位置一旦被确定，其位置难于再改变。因此研究物流配送中心的选址具有重要的理论意义和现实应用意义。一般说来，物流中心选址模型是非凸和非光滑

4、的带有复杂约束的非线性规划模型，属于NP-hard问题。解决物流中心选址问题的方法主要有：层次分析法、专家选择法、比较分析法、模糊评价法、混合整数规划法等。其中，层次分析法、专家选择法、比较分析法、模糊评价法属于定性分析方法，含有一定的主观因素；混合整数规划法具有NP-hard问题性质，当问题规模较大时，求解较困难，因此迫切需要寻求方便高效的配送中心选址的求解算法。1 物流配送中心选址模型的建立配送中心选址问题描述为在有限的位置（m个）中选择一定数量的地点（p个），以合理的规模建立配送中心，为n个配送点配送物品,使得在选出点建立的配送中心在满足配送需求的前提下，成本（包括建造成本和运营成本）最

5、低。因此，在物流配送中心选址模型中作如下假设：（1） 配送中心的规模容量总可以满足需求点需求，并由其配送辐射范围内的需求量决定；（2）一个需求点仅有一个配送中心供应；（3）不考虑工厂到配送中心的运输费用。基于以上假设，建立如下模型。该模型是一个选址/分配模型，在满足距离上限的情况下，需要从n个需求点找出配送中心并向各个需求点配送货物。目标函数是个配送中心到需求点的需求量和距离之的乘积之和最小，目标函数为 （1-1）约束条件为 （1-2） （1-3） （1-4） （1-5） （1-6）其中，是所有需求点的序号集合；为到需求点的距离小于s的备选配送中心集合，表示配送点的需求量；表示从需求点i到离他

6、最近的的配送中心的距离，为0-1变量，表示拥护和物流中心的服务需求分配关系，当其为1时，表示需求点j的需求量由配送中心j供应，否则，是0-1变量，当其为1时，表示点j被选为配送中心，s为新建配送中心里有他服务的需求点的距离上限。式（1-2）保证每个需求点只能由一个配送中心服务，式（1-3）确保需求点的需求量只能被设为配送中心的点供应，既没有配送中心的点不会有客户；式（1-4）规定了被选为配送中心的数量为p；式（1-5）表示变量和是0-1变量；式（1-6）保证了需求点在配送中心可配送到的范围内。2 免疫优化算法免疫算法（immune algorithm）是受生物免疫系统启发，在免疫学基础上发展起

7、来的一种新型的智能计算方法。它利用免疫系统的多样性产生和维持机制来保持群体的多样性，克服了一般寻优过程尤其是多峰函数寻优过程中难处理的早熟问题，最终求得全局最优解。2.1 算法流程免疫算法流程如图2-1所示：图2-1 免疫算法流程图免疫优化算法具体实现步骤如下：（1）分析问题。对问题及其解的特性进行分析，分析解合适表达形式；（2）产生初始抗体群。随机产生N个个体并从记忆库中提取m个个体构成初始群体，其中m为记忆库中个体的数量；（3）对上述群体中各个抗体进行评价。在本算法中对个体的评价是以个体的期望繁殖率P为标准的；（4）形成父带群体。将初始群体按期望繁殖率P进行降序排列，并取前N个个体构成父带

8、群体；同时取前m个个体存入记忆库中。（5）判断是否满足结束条件，是则结束；反之，则进行下一步操作；（6）新群体产生。基于步骤（4）的计算结果对抗体群体进行选择、交叉、变异操作得到新群体，再从记忆库中取出记忆的个体，共同构成新一代群体。（7）转去执行步骤（3）。2.2 初始抗体群的产生如果记忆库为空，则初始抗体群从记忆库中选择生成。否则，在可行解空间随机产生初始抗体群。此处采用简单编码方式。每个选址方案可形成一个长度为p的抗体（p表示配送中心数量），每个抗体代表被选为配送中心的需求点的序列。例如，考虑包含31个需求点的问题1,2，,31表示需求点的序列。从中选出6个作为配送中心。抗体2 7 15

9、 21 29 11代表一个可行解，它表示2,7,15,21,29,11被选为配送中心。这种编码方式能够满足与约束条件。2.3 解的多样性评价（1）抗体与抗原间亲和力抗体与抗原之间的亲和力用于表示抗体对抗原的识别程度，此处针对上述配送中心选址模型设计亲和力函数 （2-1）其中，为目标函数；分母中第二项表示为违反距离约束的解给予惩罚，C取一个比较大的正数。（2）抗体与抗体间亲合力抗体与抗体之间的亲和力反映了抗体之间的相似程度。鉴于此处抗原的编码方法，各位之间不需考虑排序，可参考变形的R位连续方法计算抗体间亲和度，即 （2-2）其中，为抗体v与抗体s中相同的位数；L为抗体的长度。（3）抗体浓度抗体的

10、浓度即群体中相似抗体所占的比例，即 （2-3）其中，N为抗体总数；T为预先设定的一个阀值。（4）期望繁殖概率在群体中，每个个体的期望繁殖概率有抗体与抗原间亲和力和抗体浓度两部分共同决定，即 （2-4）其中，为常数。由上式可见，个体适应度越高，则期望繁殖概率越大；个体浓度越大，则期望繁殖概率越小。2.4 免疫操作 （1）选择：按照轮盘赌选择机制进行选择操作，个体被选择的概率为式（2-4）计算出期望繁殖概率。（2）交叉：本文采用单点交叉法进行交叉操作；（3）变异：采用常用的变异方法，即随机选择变异位进行变异。3 仿真实验及结果分析为证明算法的可行性和有效性，采集了全国31个城市的坐标，每个用户的位

11、置及其物资需求量由表3-1中给出，这里的物资需求量是经过规范化处理后的数值，并不代表实际值。从中选择6个作为物流配送中心。根据配送中心选址模型，按照免疫算法步骤对算例进行求解，算法的参数分别为：种群规模为50，记忆库容量为10，迭代次数为100，交叉概率为0.5，变异概率为0.4，多样性评价参数设为0.95，求得配送中心的选址方案为18 25 5 27 9 14,此方案以各需求点需求量为权重的距离和为。表3-1 用户的位置及其物资需求量j()j()j()1(1304,2312)2012(2562,1756)4023（3429,1908）802(3639,1315)9013(2788,1491)

12、4024（3507,2376）703(4177,2244)9014(2381,1676)4025（3394,2643）804(3712,1399)6015(1332,695)2026（3439,3201）405(3488,1535)7016（3715,1678）8027(2935,3240)406(3326,1556)7017（3918,2179）9028(3140,3550)607(3238,1229)4018（4061,2370）7029(2545,2357)708(4196,1044)9019（3780,2212）10030(2778,2826)509(4312,790)9020（367

13、6,2578）5031(2370,2975)3010(4386,570)7021（4029,2838）5011(3007,1970)6022（4263,2931）50免疫算法收敛曲线如图3-1所示。得到的物流配送中心选址方案如图3-2所示。图3-1 免疫算法收敛曲线图3-2 物流配送中心选址方案4 结论本文在物流配送中心选址优化问题数学模型的基础上，构造了一种免疫优化算法用于求解该问题。在算法中引入了抗体克隆选择扩增、抗体抑制等思想，使得该算法具备了较强的寻优能力。通过对物流配送中心选址的仿真结果表明，利用免疫优化算法可以方便地求得物流配送中心选址优化问题的最优解。参考文献：1 肖人彬，曹鹏斌，刘勇.工程免疫计算M.北京：科学出版社，2007.2 史峰，王辉等.MATLAB智能算法30个案例分析M.北京：北京航空航天大学出版社，2011.7.3 刘冰.人工免疫算法及其应用研究D.重庆：重庆大学，2004.4 郭莉.随机需求下的物流配送中心动态选址研究D.成都：西南交通大学，2006.5 周梅芳，叶洪涛.基于免疫算法的物流配送中心选址J.广西工学院学报,2012,23(3):77-79.