免疫遗传算法求解物流配送中带时间窗的VRP问题

摘 要 建立了带时间窗VRP问题的数学模型，提出了一种改进的免疫遗传算法，该算法在传统遗传算法的基础上加入了自适应交叉算子并运用小生境技术对免疫算法加以改进，实验结果表明该算法具有更好的全局搜索能力和收敛速度，可有效地解决物流配送车辆路径优化问题。

【关键词】免疫遗传算法 物流配送 VRP 小生境

利用人工智能的启发式算法的思想，求解VRP问题是当前研究的热点。遗传算法存在效率低下、易陷入局部最优等缺点。论文则将遗传算法结合人工免疫的思想应用到该问题中，对进化中的种群进行疫苗提取和注射，增强了进化的稳定性，通过疫苗信息的引导加速种群向着好的方向快速进化。

1 物流配送路径优化问题的数学模型

minz=cijxijk+pEmax（ETi-si，0）+pLmax（si-LTi，0）+Mmax（giyik-q，0）

2 免疫遗传算法设计

2.1 产生初始种群

算法实现中，将VRP的目标函数对应于抗原，问题的解对应于抗体。对初次应答，初始抗体随机产生，对再次应答，则借助免疫机制的记忆功能，部分初始抗体由记忆单元获取。本文抗体采用自然数编码。解向量可编成一条长度为k+m+1的染色体（0，i1，i2，…，is，0，ij， …，ik ，0， …，0，ip ， …，iq，0）。

2.2 计算抗体适应度

对任一抗体i，若为一条可行路径（即满足约束条件），且其目标函数值为zi，则其适应度函数取其目标函数值的倒数的β（>1）次方，即 Fitness（i）=（1/zi）β。

2.3 免疫算子

2.3.1 免疫疫苗的选取

记忆库是对种群进化过程中所产生的最优抗体的存储，疫苗的提取可以在记忆库中以以下的公式进行概率选取抗体，当作免疫疫苗。根据高浓度低亲和力的抗体受到抑制，低浓度高亲和力的抗体受到促进这一免疫原理，用基于浓度的选择概率来保证种群的多样性。

2.3.2 注射疫苗

以一定的免疫概率随机从记忆库中选择一个抗体中的一段信息片段，接种到另一个抗体的相对位置上来完成的。为了保证搜索达到的最佳个体不会被各种遗传操作破坏，把新生成的临时群体放入上代种群中去，然后去掉较差的个体直至群体规模还原。

2.4 小生境淘汰运算

将前几步得到的n个个体和记忆的m个个体合并在一起，得到一个含有m+n个个体的新群体。对这m+n个个体，按照下式求出每两个个体Gi和Gj之间的海明距离：

||Gi-Gj||=

（6）

当||Gi-Gj||

=Penalty

依据这m+n个个体的亲和力对各个体进行降序排序，记忆前m个个体。生成新的记忆库。如果满足终止条件，则输出记忆库中的抗体作为最优解，终止计算。否则，将此m个个体作为新的下一代群体，重新进行选择，交叉，变异及小生境淘汰运算。

3 仿真实例

设配送中心和20个客户分布在一个边长为100km的正方形地域内，配送中心坐标为（31，9），车辆载重量为8t，各配送点和配送中心的坐标，需求量为di，各配送点要求的服务时间范围[ai，bi]由表给出，允许最大车辆数为6，要求合理安排车辆的行驶路线，既能满足条件完成所有运输任务，又能使总的运输成本最低。

设置求解参数：群体规模为50，遗传代数为50，小生境间的距离参数L=0.5，罚函数Penalty=10-30，采用本文设计的算法，随机运行。其运行结果如下所示：

4 条配送路径分别为：

子路径1：0740

子路径2：0680

子路径3：053120

与基本遗传算法相比较，改进免疫遗传算法不但收敛速度快，而且表现出较强地脱离局部最小值的能力，最少路程为503.42km。

参考文献

[1]孟辉，蔡田刚，姜忠鹤.基于改进遗传算法的带硬时间窗车辆路径问题研究[J].机械工程师，2011（02）.

[2]聂艳芳.VRP的数学模型及算法分析[J].山西电子技术，2010（01）.

作者单位

1.镇江船艇学院 江苏省镇江市 212003

2.北京市遥感信息研究所 北京市 100085