摘 要： 在分析了一类配送中心选址问题的基础上，建立了该配送中心选址问题的数学模型。提出一种具有双重信息的遗传算法编码方案，并结合相应的遗传操作进行求寻优求解，最后通过实验证明了该方法的可行性和有效性。
关键词： 双重信息；遗传算法；配送中心；模型
随着市场竞争的日益加剧，越来越多的企业认识到，如何合理地设立分销配送中心，加强对配送环节的有效管理，是提高企业竞争力非常有效的途径。配送是指在经济合理区域范围内里，配送中心根据客户要求，对物品进行拣选、加工、包装、分割、组配等，并按时送达指定地点建立中间分销配送中心[1]。科学建立配送中心，不仅可以使企业快速把握和响应市场反应，而且还能通过优化的配送中心以及相应的配送方案给企业节约很大的成本。
目前，越来越多的研究人员趋向于采用遗传算法、拉格朗日松弛法、模拟退火算法等启发式算法来达到或逼近该问题的最优解[2]。参考文献[3]使用两步骤近似法构建在库存和运输双重能力约束下，每个周期配送中心的库存成本计算方法，分别用遗传算法、克隆选择算法、粒子群算法求解所建立的模型；参考文献[4]使用经遗传算法改进的人工神经网络模型对粮食配送中心选址问题进行求解；参考文献[5]采用以模拟退火的思想对遗传算子参数进行自适应的改进方法，解决以区域分销中心选址为基础的汽车零部件物流网络优化解决方案；参考文献[6]采用改进的遗传算法求解带有时间窗的单配送中心的车辆调度模型。遗传算法具有随机和多点搜寻特性[7]。本文对遗传算法进行改进，设计一种具有双重信息的编码方案和相应的遗传操作，将之应用到配送中心选址模型，使算法能够有效地收敛到该模型的全局最优解。
1 一类配送中心选址数学模型
1.1 问题描述
若某企业需要在某市建立若干个配送中心，现有m个备选配送中心和n个配送点，并且已知每个备选配送中心的建设费用以及其建成后可具有的容量，以及配送中心向配送点配送时每单位重量需花费的运输费用和每个配送点的需求量，现需要从m个备选配送点中选择若干个建设成配送中心，那么选取哪些备用配送中心以及如何分配这些配送中心的配送点，使得配送中心建设费用以及向配送点配送时的花费最少[8]。
1.2 数学模型
根据问题描述，该类配送中心选址问题的数学模型描述如下：
式（1）表示总的建设费用和运输费用最小；式（2）表示对i点的需求量应小于等于其容量；式（3）表示向配送点j配送的量应大于等于其需求量；式（4）Ai为标志整型变量，标明第i个备选点是否被选中。
2 针对此模型的改进遗传算法
2.1 具有双重信息的染色体编码方案设计
传统的遗传算法染色体编码经常采用二进制编码。对于本文所提出的选址中心数学模型，如果采用二进制编码，可以用染色体的每个基因位相应的下标来代表每个备选配送中心，用染色体的每个基因位上的0-1值代表该备选配送中心是否被选中，若共有6个备选配送中心和8个配送点，则染色体长度应设置为6，如果某个染色体如图1所示。
则表示1号、2号、6号备选配送中心被选中，利用这种编码方案虽然可以表示出哪些备选配送中心被选中，但是从染色体上体现不出这些选出来的配送中心为哪些配送点进行配送，如果要继续确定这些配送中心的配送点，又需要在此基础上进行相应的设计，这无疑会增加算法的复杂度和编程的工作量。
针对二进制编码的上述问题，本文提出了一种具有双重信息的染色体编码方案，使染色体可以体现双重信息，从染色体上既可以体现出哪些备选配送中心被选中，而且还可以体现出这些选出来的配送中心为哪些配送点进行配送，这会很大程度上提高解决问题的效率。具体方法是：若要从m个备选配送中心选择若干个为n个配送点进行配送服务，则设置染色体的长度是n，染色体由n个[1，m]之间的整数构成，如要从6个备选中心中选择若干个为8个配送点服务，则染色体长度为8，染色体由8个[1，6]之间的整数构成。这样染色体的每个基因位上的值就代表选中的配送中心的编号，而染色体的每个基因位相应的下标表示其所服务的配送点。如果某个染色体如图2所示。
2.4 遗传算法步骤设计
将上述改进遗传算法应用到本文的配送中心选址模型求解中，具体步骤如下：
（1）设置遗传算法基本参数：种群数量NIND，最大代数MAXGEN，代沟GGAP，交叉概率Pc，变异概率Pm，读入各备选配送中心的建设费用和建设之后的容量，以及各个配送点的需求和配送单位重量需要的运输费用。
（2）产生初始种群：产生NIND行n列个范围在[1，m]之间的随机整数作为初始种群Chrom，其中n为配送点的个数，m为备用配送中心的个数。
（3）分别计算种群Chrom中各染色体的目标值Objv，根据各自的目标值按照代沟GGAP按前述方法进行选择操作，形成Selch。
（4）对Selch按照交叉概率Pc和变异概率Pm依次进行交叉和变异操作，形成子代种群。
（5）记录子代种群的最优目标值，并对子代种群按步骤（2）的方法产生若干个染色体对子代种群进行补充。
（6）判断Gen是否大于MAXGEN，是则退出，否则转向步骤（3）。
3 仿真测试
假设某公司需要为其在某市的8个配送点选择配送中心，需要从6个备选点选择若干个对其进行建设作为配送中心，那么选择哪些备选点作为配送中心会使得建设费用和运输费用最小，其中8个配送点的需求量如表1所示，各个备选配送中心的建设费用及容量如表2所示，各配送中心向配送点配送时每单位重量需花费的运输费用如表3所示。
采用上述改进遗传算法对此问题进行仿真测试，其中参数设置为：种群数量NIND=20，最大代数MAXGEN=100，代沟GGAP=0.7，交叉概率Pc=0.7。
程序运行后的最优解的染色体为：21121222，从该染色体可以得出：从6个备选配送中心中选择1号、2号建设成为配送中心，其中1号配送中心为2号、3号、5号配送点配送服务，2号配送中心为1号、4号、6号、7号、8号配送点配送服务。
其中遗传算法进行100代时每代的最优目标值如图3所示，从图中可以看出，运行到100代时得出最优解，总的建设和运输费用是804个单位值，进化时每代的最优目标值从最初的1 655左右逐渐下降到804，说明该算法有很好的寻优能力，能有效地对这类配送中心选址数学模型进行优化。
科学建立配送中心，不仅可以使企业快速把握和响应市场，而且还能通过优化的配送中心以及相应的配送方案提高企业的市场竞争力。本文针对一类配送中心选址问题出发，对其进行数学建模，并提出一种具有双重信息的编码设计方案，使得从染色体编码上不仅可以体现出哪些备选配送中心被选中，而且还可以体现出这些选出来的配送中心为哪些配送点进行配送。通过仿真测试，证明了该方法在解决这一类模型时的可行性和有效性。
参考文献
[1] 谢天保，雷西玲，席文玲.物流配送中心配载车辆调度问题研究[J].计算机工程与应用，2010，46（36）：237-240.
[2] 王喆.基于组合遗传算法的铁路危险货物办理站点整合优化[J].计算机应用，2010，39（9）：2301-2304.
[3] 税文兵，叶怀珍，张诗波.物流配送中心动态选址模型及算法研究[J].计算机应用研究，2010，27（12）：4476-4479.
[4] 许德刚，肖人彬.基于改进神经网络的粮食配送中心选址决策研究[J].计算机应用研究，2010，27（3）：887-890.
[5] 朱爽，王东.汽车零部件物流网络优化设计与实现[J].计算机工程，2011，37（12）：258-261.
[6] 施朝春，王旭，葛显龙.带有时间窗的多配送中心车辆调度问题研究[J].计算机工程与应用，2009，45（34）：21-24.
[7] 李净，袁小华，朱云飞.物流配送系统中车辆路径问题的实现[J].计算机工程与设计，2009，30（16）：3783-3786.
[8] 张玉芬，齐红然，刘世普.一类应急服务设施选址问题的模型及算法[J].数学的实践与认识，2009，39（14）：37-41.