基于免疫算法的地下物流中转分配节点选址研究

刘桂汝 魏赟

摘要：互联网加速了物流业发展，地下物流网络节点选址成为新的研究热点。将二分K-均值算法和免疫算法相结合，对物流中转分配节点（一、二级节点）选址进行了研究。首先根据问题的约束条件和优化目标建立物流一、二级节点选址数学模型，然后采用二分K-均值算法和免疫算法求解最佳一、二级节点选址方案。对南京市仙林区110个物流节点分配方案进行实验，结果表明该算法能很好地解决组合优化问题。

关键词：免疫算法；二分K-均值算法；地下物流系统；组合优化；节点选址

DOIDOI：10.11907/rjdk.173155

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2018）008-0169-05

英文摘要Abstract：The Internet accelerates the development of the logistics industry.A more efficient underground logistics system in cities has become a new research hotspot.We propose an immune algorithm based on the transfer of distribution nodes （first and second levels of nodes） site selection.Firstly，by considering the constraints and optimization objectives of the problem，a mathematic model of first and second level nodes in logistics are established，and then the best one or two node location model is solved by immune algorithm.Finally，the test on the 110 logistics nodes in Xianlin District of Nanjing is conducted and it is concluded that 17 second-level relay nodes and nine first-level relay nodes need to be established，which verifies that the algorithm can well solve the combinatorial optimization problem.

英文关键词Key Words：immune optimization algorithm ；bisecting K-means algorithm； underground logistics system； combinatorial optimization； node location

0 引言

隨着电商的发展，城市道路上流转货物越来越多。大型货车的增多使道路越来越拥挤，地下物流系统[1]概念随之提出，而物流中转节点组合优化模型因其未知数量多，非线性度和复杂度而困扰模型的求解。

免疫系统作为一种新兴的生物信息处理机制近年受到关注。免疫算法[2-4]是受生物免疫系统启发，在免疫学理论基础上发展起来的一种新兴智能计算方法。此算法强调群体中个体之间的信息交换，克服一般寻优过程尤其是多峰函数寻优过程中难处理的“早熟”问题，最终求得全局最优解。本文通过二分K-均值算法[5]与免疫算法相结合解决组合优化问题。二分K-均值算法不受初始化问题影响，因为这里不存在随机点的选取，且每一步都保证了误差最小。将110个物流节点进行聚类，求解出二级中转节点的位置，在此基础上利用免疫算法以最少预算为约束对一级中转节点进行选取，验证了算法的可行性。

1 地下物流系统

地下物流系统（Underground Logistics System）[6-7]指城市内部及城市间通过类似地铁的地下管道运输货物的供应系统。该系统先将各地的货物通过各种运输方式运到城市外围的物流园区、机场、火车货运站等，经过处理后进入地下。无人驾驶技术的出现，加速了地下物流系统的发展。除了需要考虑基本的运输单元以及为实现高度自动化和准确化而采用的自动导航系统外，地下物流系统的网络形态和中转分配节点位置直接影响着物流系统的运转效率，也直接影响该系统结构的合理性、工程投资以及经济效益和社会效益。本文将二分K-均值算法与免疫算法相结合，应用于物流中转节点选址问题中，最终从候选节点选出更为科学、合理的节点。

2 基于二分K-均值算法的二级中转节点选取

在物流中心点确定过程中，二级中转节点的选取问题是要得到局部最小而不是全局最小，二分K-均值算法可以很好地解决此问题。该算法首先将所有点作为一个簇，然后将簇一分为二，之后选择其中一个簇继续划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE值。SSE值（误差平方和）越小表示数据点越接近于质心，聚类效果也越好。选择SSE最大的簇进行划分，基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。

3 基于免疫算法的节点优化

传统算法[8]无法避免因节点位置、地下物流网结构变化引起的干扰，降低了地下物流网节点分配的有效性。本文提出一种基于免疫优化算法的地下物流网[9-10]中转节点分配方法。免疫算法来源于生物免疫系统，生物免疫系统的概念与免疫算法的对应关系如表1所示。

3.1 免疫算法流程

免疫算法流程如图1所示，实现步骤如下：

①产生初始抗体群。随机产生26个个体，并从记忆库里抽取9个个体形成初始群体；

②对群体中的抗体进行评价，评价以个体的期望繁殖率p为标准；

③形成父代群体。将初始群体按期望繁殖率p进行降序排列，并提取前26个个体构成父代群体，同时取前9个个体存入记忆库；

④对结束条件进行判断，如果是则结束，否就进行下一步操作；

⑤新群体产生。基于步骤④的计算结果对抗体群体进行选择、交叉、变异等操作，得到新群体，再从记忆库中取出记忆的个体，共同构成新一代群体；

⑥转去执行步骤③。

3.2 初始群体产生

如果记忆库非空，则初始抗体群从记忆库中选择生成，否则在可行解空间随机产生初始抗体群。此处采用简单編码方式。每个选址方案可形成一个长度为x的抗体（x表示一级节点个数），每个抗体代表选为一级节点的序列。例如，1～26是代表二级节点的序号，从中选择9个作为一级节点，免疫算法所产生的[1，2，4，9，10，16，18，20，25]为产生的可行解，表示[1，2，4，9，10，16，18，20，25]被改变为一级节点。

3.3 解的多样性评价

由式（5）可见，个体适应度值越高，则期望繁殖率越大；个体浓度越大，则期望繁殖率也越大。这样既鼓励了适应度高的个体，又抑制了浓度高的个体，从而确保了个体多样性。

3.4 免疫操作

选择：依照轮盘赌选择机制进行，个体选择概率为式（5）计算的期望繁殖概率；

交叉：基于免疫优化算法的物流中转节点选址模型[12-14]采用单点交叉操作；

变异：采用常用的变异方法，即随机选择变异位进行变异操作。

4 实验结果分析

图2所示为南京市仙林区货运区域划分，小红点为节点，红点旁边的数字代表货运站标号，1、2、3、4代表4个物流园区。现在需要再设置一些中转分配节点（一级节点、二级节点）。由于一级节点与二级节点都遵循服务范围3km，也就是说从一级节点、二级节点到路面上的服务节点范围是3km，采用二分K-均值算法对这些小节点进行聚类。

4.1 二分K-均值优化二级节点分布

求解二级节点时，将交通货运区域划分图中的每个节点视为聚类对象，利用二分K-均值算法进行聚类，所得的质心[15]视为所求的二级节点。算法得出的二级节点（聚类中心点）个数及位置分布如图3所示。由于二级节点要将每个区域的中心点覆盖，经过多次聚类，得出当算法将所有区域聚成了17个簇时，能将所有的中心节点覆盖，因此，选择这17个聚类得到的质心点作为二级节点。将这些二级节点与图上的小节点连接，形成一个区域，这个区域就是二级节点的覆盖范围。

图4为二级节点与小节点的连接图，二级节点的具体位置及服务范围（每个节点标号）如表2所示。

由表2可知，二级节点服务范围划分存在一些不均衡状况，比如1号二级节点的服务范围只包含一个节点，说明该区域的货运流量比较稀疏。服务范围不均衡状况有助于确定一级节点的个数及分布情况。根据各个二级节点的服务范围，可求出每个二级节点的实际货运量，具体结果见表3。

二级节点的实际货运量是其服务范围内所有节点通过地下物流系统运输的货物量进出口总和，表3中的实际货运量是针对地下物流系统而言。1号二级节点的实际货运量为0，并不是说该节点所在的区域没有货运流通，而是说明该区域的货运流量比较稀疏，交通比较畅通，不需要转入地下物流系统进行货运，所以其货运量为0。

4.2 免疫算法求解一级节点

表3中的实际货运量很多都超过了3 000t，而实际要求二级节点从地面收发货物总量上限为3 000t，所以需要增添一级节点来分摊二级节点中多余的货运量。在满足要求的前提下，通过免疫算法，对17个二级节点操作，在该方案下各需求点货运量权重[16]的距离和为5.68×105，得出总预算最小。算法收敛曲线如图5曲线所示。

经过免疫遗传算法，将17个二级节点划分成9部分，每部分对应一个一级节点，从而得出一级节点的个数为9，且一级节点主要分布在二级节点比较密集的区域，这种分布有效缓解了二级节点货运量较大问题，从而确保了交通畅通。一级节点位置坐标及服务范围如表4所示。

一级节点的服务范围由其所覆盖的二级节点构成，每个二级节点有各自的服务范围，所以表中显示一级节点的服务范围较大。由一级节点的服务范围可求得一级节点的实际货运量，结果如表5所示。

一级节点的实际货运量由其服务范围内所有二级节点的实际货运量构成。要求一级节点从地面收发货物总量上限为4 000t，表中显示各一级节点的实际货运量都超出了4 000t，但是一级节点是在地下物流系统中运行的，其货运量没有明确限制。一级节点主要用来分担二级节点货运压力和缓解交通畅通度，通过设置9个一级节点，所有二级节点都能满足3000t上限要求，从而保证交通畅通，所以选取的一级节点是合理的。

5 结语

针对地下物流系统中转节点规划问题，本文将二分K-均值算法和免疫算法相结合，对地下物流中转节点进行选址。其中免疫优化算法既可利用免疫算子加强算法的全局搜索能力，又能充分利用待规划问题中的全部特征信息，以准确找到全局最优解，收敛速度也很快，实例计算结果表明该算法实用可行。

参考文献：

[1] CHEN Z L，DONG J J，REN R.Urban underground logistics system in China：opportunities or challenges [J].Underground Space，2017（2）：195-508.

[2] 王煦法，张显俊.一种基于免疫原理的遗传算法[J].小型微型计算机，1999，20（2）：117 -120.

[3] GONG M G，JIAO L C，ZHANG X R.A population-based artificial immune system for numerical optimization[J].Neu-Rocompuring.2008，72（1-3）：149-161.

[4] WOLDEMARIAM K M，YEN G G.Vaccine-enhanced artificial immune system for multimodal function optimization[J].IEEE Transaction.On Systems，Man，and Cybernetics，Part B：Cybernetics，2010，40（1）：218-228.

[5] 王超，吳小丽.地铁隧道与邻近高层构筑物建设时序优化研究[J].隧道建设，2012（5）：5-17.

[6] 李锐，李鹏，曲亚东，等.机器学习实战[M].北京：人民邮电出版社，2013.

[7] 蔡自兴.人工智能及其应用[M].北京：清华大学出版社，2007：249-283.

[8] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numberische Mathematik，1959，1（1）：269-271.

[9] 高飞.MATLAB智能算法超级学习手册[M].北京：人民邮电出版社，2011.

[10] 闫文涛.城市地下物流系统节点选址研究—以重庆市为例[D].重庆：重庆交通大学，2015.

[11] MITCHELL M，FORREST S.Genetic algorithms and artificial life[M].Artificial Life，1994.

[12] 彭丽英.改进的蚁群算法网络节点覆盖优化研究[J].计算机仿真，2011（9）：151-153.

[13] 姜阳光，庞大钧.基于集合覆盖模型的城市 ULS 物流节点选址分析[J]，物流科技，2009（10）：54-55.

[14] 乔联宝，朱华桂.危险品配送中心选址及路线选择问题研究[J].物流科技，2013（4）：37-42.

[15] 李蔚田，神会存.智能物流[M].北京：北京大学出版社，2013.

[16] 王四春.GP算法中适应度函数的光滑拟合与调整参数方法研究 [J].自动化学报，2006（3）：23-30.

（责任编辑：杜能钢）