基于云自适应遗传算法的物流配送中心选址问题研究.doc

基于云自适应遗传算法的物流配送中心选址问题研究-工程论文基于云自适应遗传算法的物流配送中心选址问题研究 李娟 LI Juan （重庆工商职业学院财经管理学院，重庆 400052） 摘要： 物流配送中心是整个物流系统的关键环节，对于降低物流成本、提高物流效率具有重大意义。现有求解物流配送中心选址问题的传统遗传算法，存在种群多样性较差、个体退化等缺点，算法性能有待进一步改善。针对该问题，在云模型理论的基础上，本文提出了求解物流配送中心选址问题的云自适应遗传算法。算法的核心思想在于利用云模型理论生成交叉和变异概率。最后的仿真实例表明，本文所提算法具有更好的求解性能。 关键词： 物流中心选址；遗传算法；云模型 中图分类号：F224 文献标识码：A 文章编号：1006-4311（2015）23-0060-03 作者简介：李娟（1984-），女，山西大同人，讲师，硕士，研究方向为物流管理。 0 引言 随着我国经济的增长，物流行业也取得了快速的发展。如今，物流作为“第三方利润源泉”，已然成为我国经济发展的新增长点，整个物流系统包含着巨大的经济效益1。物流配送中心作为物流系统的关键节点，能够提高物流系统的运作效率，降低运作成本，因此广受学者关注，关于物流中心选址问题的求解算法更是不甚枚举。其中，由于并发性能较好、搜索范围较大等优点，遗传算法被应用得最为广泛，如文献2-5。传统遗传算法虽然在一定程度上解决了物流配送中心选址的难题，但固定的交叉和变异概率值一方面限制了种群的多样性。另一方面，个体在算法进化过程中也时常产生退化现象，进而算法求解性能有待提高。 云理论来源于“隶属云与语言原子模型”等概念，是一种定量定性转换模型，最初由李德毅院士提出6-7。云自适应遗传算法则是由文献8针对传统遗传算法中种群多样性较差、算法退化等现象，在云模型理论的基础上提出的一种自适应遗传算法。该算法通过云模型理论生成遗传算法中的交叉和变异概率，利用云滴的稳定倾向性使交叉概率具有稳定倾向性，从而避免了算法出现退化现象，加快了算法的求解速度；此外，由于云滴还具有随机性，因此通过云模型设计交叉和变异概率，还能提高种群的多样性，进而提高算法求解性能。 基于上述分析，本文提出了求解物流配送中心选址问题的云自适应遗传算法。 1 物流配送中心选址问题的数学模型 物流配送中心选址问题一般可以描述为：企业需要从一系列候选地点中选择几个点建立物流配送中心。候选地点、配送中心供应商、客户以及配送成本等相关信息全部已知，要求在合理的地点建立数量合理的配送中心，使整个网络的成本最小，包括配送中心费用和配送费用。 设m、n和l分别表示供应商、配送中心候选地点、配送中心服务客户的数量；k（k=1，2，m）、i（i=1，2，n）和j（j=1，2，l）分别表示供应商、配送中心和客户的序号；Ak表示第k个供应商的最大供应量；Mi表示第i个配送中心候选地的最大容量；Dj为第j个用户的需求量；P表示最多建立的配送中心的数量； cki表示第k个供应商到第i个配送中心的单位运输成本；xki表示第k个供应商到第i个配送中心的配送量；hij表示第i个配送中心到第j个客户的单位运输成本；xij表示第i个配送中心到第j个客户的配送量；Vi表示第i个配送中心的可变成本系数；Fi表示第i个配送中心的固定费用；Wi表示第i个配送中心的流量，；zi是0-1变量，zi=1表示第i个配送中心候选地被选为配送中心，zi=0表示其他。物流配送中心选址问题的数学模型为： 其中，式（1）表示物流配送中心固定成本、变动成本和配送成本之和最小的优化目标，；式（2）表示供应商的供应量约束；式（3）表示客户的需求量约束；式（4）表示配送中心输出流量和输入流量平衡；式（5）表示配送中心的最大容量约束；式（6）表示配送中心的数量约束；式（7）表示变量非负约束。 2 云自适应遗传算法在物流配送中心选址问题中的应用 2.1 个体编码。采用二进制编码，1表示候选地被选为配送中心，0表示其他。如一个具有6个配送中心候选地的个体可以编码为（1，0，1，0，1，0）。 2.2 适应度函数。遗传算法中的适应度值表示个体的优秀程度，通常越优秀的个体，其适应度函数值越大。因此，本文对式（1）进行如下修改，作为遗传算法的适应度函数。 fitness=a/f （8） 式中，a为一个常数，可以根据问题的规模进行调整。 2.3 选择算子。为了提高算法进化过程中种群的质量，保护种群中的优秀个体。在进行选择操作时，首先将所有个体按适应度函数值进行由高到地的排序；然后种群中前10%的个体直接进入下一代；剩余的个体则按照轮盘赌选择算子进行操作。 2.4 交叉算子。在交叉操作上，采用传统的两点交叉算子，即随机生成两个交叉点，将待交叉个体中位于两个交叉点之间的部分进行互换。而自适应交叉概率则按文献9中的云自适应算法进行调整（如表1）。 2.5 变异算子。本文采用传统的单点变异算子，随机产生一个变异点进行变异，如果个体此处原来是1，现在则变为0；反之，则变为1。自适应变异概率同样按表1所示的云自适应遗传算法进行调整。 2.6 约束条件的处理。由于物流配送中心选址问题的约束条件较多，因此在算法进化过程中，必然产生很多不可行的个体编码。此时，将其目标函数值直接赋予0（或一个非常小的数，根据具体问题确定），则该个体进入下一代种群的概率就非常小。 2.7 算法步骤： 输入算法参数，包括最大迭代次数、种群规模、调整常数a等。 随机生成初始种群。随机生成满足种群规模的0-1编码串。 遗传算子操作，包括选择、交叉和变异操作，产生新的种群。 算法停止。如果算法达到了最大迭代次数，则停止迭代，输出最优解；否则，进入步骤。 3 仿真算例 采用文献3中的实例作为仿真算例，同时分别利用传统遗传算法、文献10中的粒子群算法和云自适应遗传算法对其进行求解，各算法分别运行20次，统计相关求解结果，如表2所示。 从表2中可知，传统遗传算法求解性能较差，容易陷入局部最优解，而且求解速度较慢，这与传统遗传算法使用固定的交叉和变异概率值有关；粒子群算法虽然在全局寻优能力上有所提高，但算法求解速度是最慢的；而本文所提的云自适应遗传算法其全局寻优能力最好，而且求解速度较快，这得益于云自适应遗传算法通过云模型理论，利用云滴的随机性和稳定倾向性改善了算法的求解性能。 4 结束语 物流配送中心选址问题是整个物流系统规划的核心所在，因此对物流配送中心选址问题的求解算法进行研究具有重大意义。本文针对传统遗传算法在求解物流配送中心选址问题时存在的缺点，结合云模型理论，提出了求解物流配送中心选址问题的云自适应遗传算法。该算法充分利用云滴的随机性和稳定倾向性提高了算法的全局寻优能力和求解速度。当然本文的研究仍然存在许多不足之处，如算法求解速度虽然有所提高，但仍然耗时较长，这也将是本文的下一步研究方向。 参考文献： 1蔡丽艳.不确定性物流中心选址问题研究J.物流科技，2013，06：64-68. 2胡莹.基于MATLAB遗传算法的物流中心选址问题研究J.中国水运（下半月），2010，07：72-73，75. 3封燕，高建瓴，粱志福.城市物流中心选址问题研究J.贵州大学学报（自然科学版），2010，05：76-80. 4陶羿，朱建青，李明.基于改进遗传算法的物流中心选址优化J.计算机工程与应用，2007，25：221-223. 5张雪东，季一木.基于模拟退火遗传混合算法的物流中心选址问题研究J.电脑开发与应用，2006，06：4-6. 6李德毅，杜益.不确定性人工智能M.北京：国防工业出版社，2005. 7李德毅，刘常昱.论正态云模型的普适性J.中国工程科学，2004，6（8）：