基于自适应免疫算法的物流配送中心选址问题研究

倪卫红 岳晓伟 邵建峰 钱伟民

摘要：关于配送中心选址问题研究，采用免疫算法时单点交叉会产生超级个体以及固定概率会影响搜索能力的情况，分别以均匀交叉和自适应化的方法，在原算法上做出改进。并以实例验证该算法的可行性和有效性，与传统免疫算法比对，能很好避免超级个体的产生同时搜索能力也有增强。该算法自适应的变化更加符合个体在不同阶段演变情况，相比传统免疫算法，达到收敛速度快、鲁棒性高的效果，进而为选址问题研究在原有基础上匹配了一种更好的方法。

Abstract： To solve selection of logistics distribution center， the standard immune algorithm （SIA） has the problem of "super individual" in the operation of single-point crossover and the poor search ability by using fixed probability of crossover and mutation. We try to apply uniform crossover and self-adaptation to SIA. Then， the feasibility and effectiveness of the adaptive immune algorithm are verified by a calculation example. Compared with SIA， AIA makes further efforts to avoid the generation of "super individual". Meanwhile， the search ability is enhanced in a certain extent. In my opinion， the adaptive changes are better to conform to the real state of individual in different stages. The AIA has fast convergence speed and high robustness. It provides a better approach on location problem in the original basis.

關键词：选址;优化;自适应;均匀交叉;免疫算法

Key words： location;optimization;adaptation;uniform crossover;immune algorithm

中图分类号：TP311                                       文献标识码：A                                  文章编号：1006-4311（2018）36-0096-04

0  引言

随着经济的不断增长和交通运输的快速发展，物流产业正依托这有利的环境优势在全球范围内迅猛发展。在这种背景下，物流配送中心的选址问题一直都是研究热点。物流行业的快速发展也引发了行业竞争的日趋白热化，利润空间不断压缩，在此情况下，资源和成本就成为企业增加盈利的根本途径[1-3]。因此，如何做到科学、合理地进行配送中心选址，优化物流网络结构和空间布局，是企业迫切需求的，同时也是相关学者不断深入研究的方向[4]。

通常情况下，配送中心的选址问题，就是在确定众多需求点的基础上，将一些需求点设置为配送中心，以此来满足与其相关的需求点的需求限制，进而构成一系列的配送服务区域。在此基础上，追求配送系统成本的最小化[3]。

当前，在物流配送中心选址问题上针对算法的运用，专家学者进行了大量的理论研究。其中，关于有竞争的物流配送中心选址，高辉[5]等针对有竞争选址模型高维性、非线性和非凸性的特性，给出了一种克隆选择算法;而郜振华[6]等对于同样的问题，为了解决算法“早熟”问题提出了一种混合遗传算法;秦固[7]则用聚类过程来映射配送中心选址问题并将蚁群优化算法作为解决多个物流配送中心选址问题的方法;淦艳[8]等用权值来衡量影响选址的因素，然后用免疫算法解决问题。受上述文献的启发，本文在文献[9]的基础上，对其提出的算法进行自适应等改进，并做出比较，获得了寻优能力进一步提升的良好效果。

1  配送中心选址问题的模型与算法

1.1 配送中心选址问题模型假设

为了构建模型，提出如下几点假设：

①在已知物流配送中心服务区域需求总量的条件下，配送中心所承载的配送能力恒满足其所服务的需求点总需求量;

②在配送中心辐射范围内，需求点仅能由与其相对应的配送中心提供服务;

③仅将配送中心与其所服务的需求点间的运输费用作为模型的服务费用;

④运营费用仅考虑配送中心的日常费用和车辆使用折旧费用之和，其余费用本文暂不考虑;

⑤以降低成本为优化目标，按工业工程标准化原则，可将营运费用标准化限定，从而对成本达到有效化控制[10]。

1.2 配送中心选址问题模型构建

基于以上假设，本文考虑的选址因素较简单，但不乏具有代表性和通用性，主要有以下两部分：①配送中心与其所服务的需求点之间的服务费用;②配送中心基地运营费用。建立如下的选址-分配数学模型：

目标函数：

其中式（1）代表全部配送中心成本总和，构成模型的目标函数。第一部分代表模型的服务成本，剩下部分则代表模型的运营成本，si：需求点i的需求量，dij：物流配送中心和需求点间的距离，Xj：配送中心的运营费用。

式（2）、（3）为假设（2）的数学语言，即确保每个需求点有且仅能够由与其对应的配送中心服务，Yij、Hj是两个0-1变量，当均为1时，表示配送中心j与需求点i的服务关系用Yij来表示，需求点j被设置为物流配送中心由Hj来表示，当均为0时，则表示相反;

式（4）规定在n个需求点集合中，选出k个配送中心;

式（5）表示配送中心服務范围能覆盖其所服务的全部需求点;

式（6）、（7）分别表示需求点和配送中心数量。

2  配送中心选址问题的AIA算法

2.1 自适应免疫优化算法介绍

首先，在众多智能算法中，免疫算法（immune algorithm，IA）产生得比较晚，是由T-Fukuda等人在1998年提出的一种算法。IA逐渐被运用在求解多态优化问题 [11]。类似于遗传算法模仿生物界的遗传进化规律，免疫算法同样是受到生物学免疫系统学说的启发。受到人体免疫系统的多样性产生和维持机制的启发下，该算法的群体呈现出多样性。这样一来，在一般寻优过程中产生的老大难问题——“早熟”问题可以得到解决，因此在处理多峰函数寻优问题时，本文认为采用免疫算法虽然将会得到比较理想的全局最优解，但仍有改进之处。在此基础上，提出自适应免疫算法，并进行对比[12]。

通常情况下，免疫算法具有以下具体实现步骤：

步骤1 ，对研究问题进行分析，然后构建目标函数和约束条件，表示抗原对机体的侵入。接着对编码方式进行设置，并在参数设置时，将Pc、Pm做出自适应化。

步骤2， 产生初始抗体群。

步骤3，对抗体进行评价。

步骤4，形成父代群体，并产生记忆细胞。

步骤5，以是否满足算法终止条件作为能否跳出循环过程的依据。

步骤6，通过对算法进行一系列操作来达到产生新群体的效果，如选择、交叉、变异等操作。

步骤7，对步骤3至步骤6进行重复操，直到终止条件被满足，最后输出结果。

如图1为AIA的流程图。

2.2 自适应免疫算法求解问题

2.2.1 编码方法

此处将运用自然数编码方式。AIA将被选作为物流配送中心的需求点编号序列表示为长度k是的个体。比如在一个拥有25个需求点的区域，首先用1-25的数来对各需求点进行编号，再从这25个编号中挑选出5个来作为物流配送中心，因此像[7 5 21 16 23]的抗体，就表示为一个可行解，意思是编号7、5、21、16、23的需求点是配送中心。这样的编码方式完全满足上述设置的约束条件。

2.2.2 免疫操作

①选择：采用常见的轮盘赌选择机制，依照期望繁殖概率来对抗体进行遴选。该概率表达式为：

（Av、Cv均参照文献[13]）。

②交叉：采用均匀交叉法来进行交叉操作。

③变异：对抗体的变异采用常用的随机变异位法。

相较于文献[9]，在算法自适应性和交叉操作两方面做出了改进，以下将分别对此进行阐述。

首先，对于算法的自适应这方面，本文在交叉概率、变异概率上设计自适应变化，将这两个概率都表示为关于进化代数t的函数，参照文献[14]，对其自适应提出新的自适应化，表示如下：

鉴于研究证明，在智能算法中Pc的大小与算法局部寻优能力正相关，Pc数值越大，算法具备的搜索能力越强，种群的进化速度越快;变异概率是与算法个体的适应性负相关，Pm越小，抗体所具有的适应能力则越强，存活下来的几率就越大。在智能算法寻优过程中，一般分为进化初期、进化中期、和进化后期三个不同的阶段。按这三个阶段将Pc、Pm分为三段值，相较于文献[9]这样的通常算法中将Pc、Pm始终固定为一个值的情况，能够做到在进化速度和搜寻的解质量中进行权衡，使算法过程更加智能化，同时对于问题也是更好的处理，进而到达自适应的变化。

此处，为了更加形象地表达以上自适应过程，将用图2、3来表示Pc、Pm在初期、中后期和后期三个阶段的变化情况，并非代表真实函数关系。为了方便图形表达，在图中用k表示。

关于算法交叉操作方面，一般情况下，均采用单点交叉或者是双点交叉，这两种交叉法都能比较好保留父代的特征，但面临很大概率产生超级个体的问题。这将会造成算法陷入局部最优。因此，本文在交叉操作时选用均匀交叉法，这样在具备单双交叉法优点的同时又能很好避免超级个体的产生。该操作不仅需要两个父代个体，同时还要引入一个隐码。本文中，用0、1两种字符来构成与父代长度相同的所需隐码，通过此隐码来决定各个基因位是否交叉。父代中基因位是否需要进行交叉则由隐码中该基因位是否为1来决定，反之不进行交叉。特举例说明：

2.3 实例仿真

本文在文献[13]数据的基础上，对此算法的可行性和有效性进行验证。同时，将本文提出来的AIA与SIA仿真结果进行比对。设置基本参数：种群规模=50，记忆库容量=10，迭代次数=100。基于同等条件，得出图4算法比对图。从图中明显看出，利用AIA获得的结果相较于SIA得出来的精度要更高。此外AIA在收敛速度、运算速度及寻优能力等方面均优于SIA。

在与SIA对比后，为了进一步测试自适应免疫算法的性能。对于该配送中心选址问题方案确定，运用遗传算法来仿真，并将其与AIA比对，如图5所示。同样，从上述的各种性能看，AIA也是优于GA。

经过以上对比，认为能用AIA更好解决该问题。于是用MATLAB多次求解，在众多求得的配送中心选址方案中，[27 11 20 12 17 5]是最优方案，其值为5.49×105。图6、7分别是AIA算法收敛图和物流配送中心选址方案。

3  结论

针对物流配送中心的选址，本文在原有算法基础上加入一种自适应的交叉、变异算子并用均匀交叉操作替换常用的单双点交叉操作。这两个方面的改进，不仅更好地避免了单双点交叉操作中高概率产生“超级个体”的情况，进而避免算法的“早熟”。由此，变化的Pc、Pm与算法不同阶段的真实情况相符合，从而对抗体种群的多样性起到更好的保持作用。AIA在具備较强寻优能力的同时，收敛速度、求解精度和鲁棒性均得到一定程度的改进。因此，该算法作为算法求解选址问题的研究是一种有效补充，具有一定的参考价值。此外，后续研究可在建模优化方面加入更多工业工程相关专业知识，以对该问题做更深层次的优化。

参考文献：

[1]魏娜.关于物流配送中心选址优化问题研究[D].东北财经大学，2007.

[2]蒋利军，蒋明，赵正佳.配送中心选址问题研究文献综述[J]. 物流科技，2008，31（4）：31-33.

[3]Hua X， Hu X， Yuan W. Research optimization on logistics distribution center location based on adaptive particle swarm algorithm[J]. Optik - International Journal for Light and Electron Optics， 2016， 127（20）：8443-8450.

[4]Klose A， Drexl A. Facility location models for distribution system design[J]. European Journal of Operational Research， 2005， 162（1）：4-29.

[5]高辉，徐光辉，王哲人，等.克隆选择算法在一类有竞争的物流配送中心选址问题中的应用[J].公路交通科技，2007，24（6）：144-147.

[6]郜振华，陈森发.遗传算法在有竞争的物流配送中心选址中的应用[J].公路交通科技，2005，22（8）：138-141.

[7]秦固.基于蚁群优化的多物流配送中心选址算法[J].系统工程理论与实践，2006，26（4）：120-124.

[8]淦艳，魏延，杨有.免疫算法在带权值的物流配送中心选址中的应用[J].重庆师范大学学报（自然科学版），2015（5）：107-113.

[9]周梅芳，叶洪涛.基于免疫算法的物流配送中心选址[J].广西科技大学学报，2012，23（3）：77-79.

[10]想田丰太郎.生产现场最优分析法，图解生产实务[M].东方出版社，2011：42.

[11]Wang C Y， Liu Z N. An Immunity-Based Algorithm for Distribution Center Location[J]. Advanced Materials Research， 2014， 971-973：1537-1542.

[12]葛红.免疫算法与遗传算法比较[J].暨南大学学报自然科学与医学版，2003，24（1）：22-25.

[13]史峰，王辉，郁磊，等.MATLAB智能算法30个案例分析[M].北京航空航天大学出版社，2015：128.

[14]刘姝廷，金太东，王连生.一种改进的自适应遗传算法[J]. 江西理工大学学报，2010，31（1）：59-61.