基于免疫遗传算法的快递末端网点优化整合

高瑞萍，纪寿文，张永昕

（1.北京交通大学　城市交通复杂系统理论与技术教育部重点实验室，北京　100044；2.交通银行日照分行，山东　日照　276800）



基于免疫遗传算法的快递末端网点优化整合

高瑞萍1，纪寿文1，张永昕2

（1.北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京100044；2.交通银行日照分行，山东日照276800）

在研究末端网点优化整合原则的基础上，建立了以末端网点运营成本和运输成本最小为目标函数、以满足客户群集中点的服务需求和末端网点的服务能力为约束条件的优化模型，并针对此模型的特点，选择免疫遗传算法对快递分拨中心选址和最终成本进行求解。该算法综合了免疫系统和遗传算法的优点，具有良好的全局收敛能力，通过算例对网点优化整合模型进行求解，验证了该算法的有效性。

快递末端网点；优化整合；免疫遗传算法

1　引言

随着经济快速、健康、持续的发展，我国快递行业也得到了迅速发展，成为国民经济发展的基础产业。为了使快递行业得到更好的发展，2014年国务院出台了《关于进一步促进资本市场健康发展的若干意见》［1］，鼓励在市场条件下的各种企业并购重组以优化人力、资源和资金的配置。对于快递物流企业来说，在满足客户需求的前提下，降低企业运营成本、提高企业的竞争力、提高企业的利润一直是物流管理领域研究的热点，其中快递物流网络的基础和优化研究是研究的重点，国内外的很多学者做了相应的研究。Mehrsai.A等使用启发式算法（遗传算法和模拟退火方法）和模糊系统混合方法，基于多目标建模方法对推拉式混合供应链物流网络中的物流运作进行研究［2］。叶耀华等将省际转运网的优化问题转变为带有时间以及容量限制的网络优化设计问题，并用拉格朗日松弛法和列生成法进行了求解［3］。余明珠基于快递公司网络结构以及快件配送模式的特点，构建了一个能够实现装卸一体化的车辆路径模型，然后提出了针对该模型的求解方法，实现了运输成本的最优化以及货物在途时间的加权最小化［4］。

快递末端网点是快递企业运营的空间集聚点，其数量和规模既可以反映出快递企业可提供服务水平和服务能力的大小，也决定了快递企业的生存发展空间。因此，末端网点优化整合对于快递企业兼并重组后的发展有着举足轻重的作用。上述文献中基于物流网络基础研究集中于定性的对物流整合各环节进行论述，对其定量的深入研究较少；而基于物流网络的优化研究大多数都集中在满足营运限制、道路能力限制等约束条件下总成本或总收益等为评价指标的物流网络的路径优化方面。而本文主要研究的是针对两个快递企业发生兼并重组［5］之后快递物流末端网点的优化整合问题，通过优化整合达到满足客户需求、减少不必要的网点、优化资源配置、减少成本的目的。从定量出发，在某一城市建立发生兼并重组的两快递企业间的末端网点优化整合的数学模型。为克服标准遗传算法早熟收敛问题，将免疫系统与遗传算法相结合，形成免疫遗传算法，并利用免疫遗传算法具有良好的全局收敛能力这一优点对其进行求解，并最后确定满足顾客需求下成本最小的网点优化整合方案，从而建立起高效率、低费用、高服务水平的末端网点网络［6］。

2　快递末端网点优化整合问题的数学模型

快递末端网点优化整合模型就是对两企业现有的末端网点进行重新优化整合。该问题可以描述为：在客户群和需求量已知的情况下，在现有的末端网络中选出最少的末端网点，这些网点能够服务所有的顾客需求点，而且所选网点的运营费用和顾客聚集点到达这些末端网点所需运输费用的总和最小，并满足以下条件：

（1）有两个快递公司发生兼并重组，需要对这两个公司现有的末端网点进行优化整合，这里可以把这两个公司在某一区域的末端网点看成一个整体进行整合，两公司的末端网点分布情况如图1所示。

图1　末端网点分布图

（2）保留一个末端网点需要一定的运营费用，尽量用最少的网点去覆盖所有需求点。

（3）假定所有末端网点有最大的服务半径，超过这个范围，顾客聚集点就不在该末端网点的服务范围内。

（4）顾客群聚集点到末端网点的运输单价用两点的距离表示。

设研究区域内有n个顾客群聚集点，两个企业共有m个待选末端网点，顾客群聚集点集合为A，待选末端网点集合为B。顾客群聚集点i的业务量为 pi（i=1，2，…，n），该业务量中被分配给待选末端网点j的部分为yij，从顾客群聚集点i到达待选末端网点j的单位运量的成本为cij，能够服务顾客群聚集点i的待选末端网点的集合为B（i）。待选末端网点j的服务能力为qj（j= 1，2，…，m），其运营的固定成本为 fj，该网点服务范围内的顾客群聚集点的集合为A（j）。定义变量xi为0-1变量，该变量取值为1时，说明保留待选末端网点j，将其选为新网络的网点，取值为0时，说明舍弃待选末端网点j。可建立如下快递末端网点优化整合问题的数学模型：

上述模型中，公式（1）为目标函数保证保留的末端网点运营成本和顾客群聚集点与末端网点之间的运输成本最小，约束（2）满足每个客户群集中点［7］的服务需求，约束（3）对保留末端网点的服务能力进行限制，变量xi的约束保证了在原末端网点处最多保留一个末端网点。公式（4）表示变量xj的取值为0或1，公式（5）确保送达某点的业务量在客户集聚区的总量以下。

3　快递末端网点优化整合问题的免疫遗传算法

免疫遗传算法［8］是通过利用生物免疫机制的一种改进的遗传算法，它主要是通过模拟和反映生物机体免疫系统的机理来达到优化的目的。用求解问题的目标函数表示免疫遗传算法中的抗原，免疫系统产生的抗体作为对应问题的解，利用抗原和抗体之间的亲和力来表示可行解与最优解的逼近程度。

假设免疫系统由N个抗体组成，采用符号集大小为S（若用二进制进行编码，S=2，即采用0、1两种字符），每个抗体基因长度为M。

免疫遗传算法具体实现步骤如下：

（1）抗原输入。把需要求解问题的目标函数和各种约束作为免疫遗传算法抗原输入。

（2）产生初始群体。在免疫系统发生初次免疫应答之后，初始抗体就随机产生。当免疫系统再次遇到抗原发生应答时，免疫机制中的记忆功能就会启动，部分初始抗体可以从记忆细胞中获取，由于记忆细胞中抗体的适应度值较高，通过免疫记忆功能可以提高算法收敛速度。

（3）计算抗体适应度。分别计算出抗原和抗体之间、抗体与抗体之间的亲和度。

（4）记忆细胞更新。找出与抗原亲和度高的抗体，由于记忆细胞数目是有限制的，要用新找出的抗体取代记忆细胞中与其亲和度最高的原有抗体，并将其加到记忆细胞中，完成记忆细胞更新。

（5）抗体生成的促进和抑制。在寻找问题最优解的过程中，如果抗体在种群中浓度过大超过一定范围时，会导致求解过程停滞不前，造成算法过早的收敛，得不到全局最优解，所以用控制抗体浓度的方法来解决抗体或相似抗体数量的问题。

用抗体和群体中与其相似抗体之间的比值来表示抗体浓度，即：

其中λ为相似度常数，一般取0.9≤λ≤1。计算出抗体浓度后，找出浓度较大的个体，记为个体1，2，...，t，

则定义该t个个体的浓度概率为：

其它N-t个个体的浓度概率为：

采用轮盘赌选择法计算个体的适应度概率pf。适应度概率Pf和浓度概率Pd两部分加权计算得到个体的选择概率p，即：

式（10）中，a为亲和系数，a＞0，pd，pf＜1。其中如果个体适应度值越大，则该个体被选择的概率也越大，而个体浓度越大，其选择概率越小。利用这种方式不仅可以将适应度高的个体保留，同时又能够确保个体的多样性。免疫遗传算法采用传统遗传算法的选择方式，计算出选择概率p后，选择合适的个体进入下一代进行遗传操作。

（6）群体更新。免疫遗传算法中变异和交叉操作与遗传算法中方法相同。随机挑出两个抗体按照前面步骤中设定的变异概率进行变异，之后相互之间再进行交叉。重复执行步骤3至步骤6步，直到符合算法的终止条件。

（7）终止条件判断。所定参数满足算法的终止条件，则算法结束并输出最优解；否则转向步骤3。

4　算例分析

有两个快递公司A和B发生兼并重组，需要将其在城市C的末端网点进行优化整合，达到减少成本，并能最大限度地满足客户需求服务的目的。两公司现有末端网点信息见表1，顾客聚集群信息见表2。

表1　末端网点信息

表2　顾客聚集群信息

根据算例条件进行免疫遗传算法求解该问题：

李吉林老师的情境教学告诉我们：“情感是语文教学的根”。学生主动参与，乐于参与，才是获得高效、保持长久的情感体验。而这种主动的情感需要教师去调动，培养。

（1）初始种群规模设定。从理论上讲，群体规模越大种群的多样性越高，找到越接近真实值的最优解的概率越大。但如果群体的规模过大则会影响计算的效率，权衡计算分析效率和群体种群多样性的需要，将初始群体规模取为50。

（2）解码与编码规则。本算法中采用实数进行编码，编码长度由末端网点数量决定（假定有最后结果N个末端网点，编码的长度就为N）。每个位置上的数字是由计算机随机生成的1-11（有11个待整合的末端网点）之间的一个整数表示末端网点的编号。个体编码示例如图2所示，表明保留的1-N末端网点分别是3、5…8。

图2　编码示例

（3）优化参数设定。对于免疫遗传算法的参数见表3。

由matlab实现的算法计算后的结果如下［9］：

使用2个网点的最小成本为：3.816 8e+07；

使用3个网点的最小成本为：3.187 8e+07；

使用4个网点的最小成本为：2.928 8e+07；

使用5个网点的最小成本为：2.741 6e+07；

表3　算法参数表

使用6个网点的最小成本为：2.542 9e+07；

使用7个网点的最小成本为：2.451 4e+07；

使用8个网点的最小成本为：2.451 8e+07；

使用9个网点的最小成本为：2.476 3e+07；

使用10个网点的最小成本为：2.510 7e+07；

使用11个网点的最小成本为：2.547 5e+07。

根据计算结果得到最优方案为保留7个网点，总成本为2.451 4e+07，所保留的末端网点分别为1号、2号、3号、5号、6号、8号、9号，保留末端网点结果如图3所示。

图3　保留的末端网点

5　结语

在快递企业兼并重组的条件下，对快递的末端网点优化整合问题进行研究对于快递企业的长远发展有重要的意义。本文提出了在满足各顾客群聚集点的服务需求和各末端网点的服务能力的前提下，建立快递末端网点优化整合模型。在对模型求解过程中选用免疫遗传算法，并介绍免疫遗传算法的相关原理、特点以及算法步骤。最后运用算例对网点优化整合模型进行求解验证，表明了该算法的可行性。

［1］国务院.关于进一步促进资本市场健康发展的若干意见［EB/ OL］.2014-05-08.

［2］Mehrsai A，Karimi H R，Thoben K D，et al.Using metaheuristic and fuzzy system for the optimization of material pull in a push-pull flow logistics network［J］.Mathematical Problems in Engineering，2013.

［3］叶耀华，王律，杨文涛，等.我国邮政网络的优化设计方法［J］.管理工程学报，2004，18（2）：39-43.

［4］余明珠，李建斌，雷东.装卸一体化的车辆路径问题及基于插入法的新禁忌算法［J］.中国管理科学，2010，18（4）：89-95.

［5］王晓东.中国民营快递企业现状与发展建议［J］.企业导报，2010，（3）：129-130.

［6］张洪斌，聂玉超.中国快递企业的网络系统分析［J］.物流技术，2009，（9）：35-37.

［7］国家发改委经济运行司，南开大学物流研究中心，中国物流市场发展报告［M］.北京：机械工业出版社，2005.

［8］龚非.人工免疫算法及SOPC实现［D］.哈尔滨：哈尔滨工程大学，2009.

［9］陈丽安.免疫遗传算法在MATLAB环境中的实现［J］.福州大学学报，2004，（5）：554-559.

Optimization and Integration of Express Delivery Terminals Based on Immunity GA

Gao Ruiping1，Ji Shouwen1，Zhang Yongxin2
（1. MOE Key Laboratory for Urban Traffic Complex System Theories Technologies， Beijing Jiaotong University， Beijing 100044；2. Bank of Communication Rizhao Branch， Rizhao 276800， China）

In this paper， on the basis of the principle in the optimization and integration of the terminal network， we established theoptimization model with the minimization of the terminal operational cost and transportation cost as the objective and the satisfaction of theservice demand of the customer groups and the service capacity of the terminals as the constraint， and then in view of the characteristics of themodel， selected the immunity genetic algorithm to derive the location and ultimate cost of the express parcel sorting center. At the end，through a numerical example， we demonstrated the validity of the algorithm in this field.

express delivery terminal； optimization and integration； immunity genetic algorithm

F224；F252.24

A

1005-152X（2016）07-0083-04

10.3969/j.issn.1005-152X.2016.07.019

2016-05-23

科技部支撑计划课题“供应链物流实时监测、跟踪与管理技术研究”（2014BAH23F01）

高瑞萍，北京交通大学硕士研究生，研究方向：物流信息化；纪寿文（1967-），博士后，副教授，研究方向：物流工程、物流信息化。