2.4　基于免疫算法的限量弧路由问题

限量弧路由问题（CapacitatedArc Routing Problem，CARP）是经典的NP-hard组合优化问题 ^[45] ，有着广泛的社会应用，如冬季扫雪路由、校车调度规划、输气管道或石油管道的检查、邮件递送规划等。其问题可以简略的描述为：给定一个网络图，预先定义约束边缘和弧线（即有向边），这些边和弧即代表需要完成的服务任务，车辆从某个顶点出发去网络图中的所有任务边，设计一个最优调度路线去寻求最小成本下，完成服务任务的一个子集 ^[46] 。常见的CARP问题有单目标CARP和小目标CARP，随着任务量和复杂度的增加，大规模CARP和多目标CARP越来越受到学者的关注和研究。

解决CARP问题常用的方法主要包括启发式算法和元启发式算法。启发式算法能够以较快速度收敛到问题的局部最优，适用于小规模CARP的求解。典型的启发式算法有path-scanning算法 ^[47] ，augment-merge算法 ^[46] 、ulosoy-split ^[48] 算法。但随着问题规模的增加，启发式算法只能收敛到问题的局部最优，于是学者们提出了搜索能力更强的元启发式算法。第一个用元启发式算法解决CARP的是Eglese，Eglese于1994年运用模拟退火算法解决了城市撒盐路径规划问题 ^[49] 。而后在2000年，Hertz、Mittaz和Laporte提出了禁忌搜索算法 ^[50] ，该算法针对CARP问题设计了有效解的表达方式和惩罚函数的评估方式。2004年，Lacomme等在传统遗传算法的基础上加以改进并结合局部搜索（local search）提出了Memetic算法（Memetic Algorithm，MA） ^[51] 。2009年，唐珂、梅一等在MA的基础上设计并应用了具有扩展搜索步长的搜索算子，提出了基于扩展邻域搜索的Memetic算法 ^[52] 。2012年，尚荣华等提出了免疫克隆选择算法用于求解多目标问题 ^[56] ，该算法用克隆操作实现全局择优，并在后续的改进算法中成功适用于多目标CARP。

2.4.1　限量弧路由问题模型

CARP问题可以描述为：给定一个连通图 G =（ V ， E ， A ），其中 V 代表顶点集合， E 代表无方向边集合， A 代表有方向边集合。把无方向边称作“边”，有方向边称为“弧”。顶点集合 V ={ v ₀ ， v ₁ ，…， v _l }， v ₀ 是顶点集合中的一个特殊点，是车辆停放的车库（源点）。对于连通图中边集合的每条边 e ，都具有服务消耗、经过消耗和需求量这3个非负属性。同样地，对于连通图中的每条弧 a ，也都具有服务消耗、经过消耗和需求量这3个非负属性。

于是，CARP问题可以表述为：有一辆或多辆容量为 Q 的车从车库出发，对连通图中所有的边任务和弧任务进行服务，并最终回到车库，求使得所有回路中使经过消耗和服务消耗之和的最小的路径，其必须满足的约束条件为：

（1）每辆车必须从车库出发，并且服务结束后返回到车库；

（2）每个边任务或者弧任务都被服务且仅被服务一次；

（3）每条路线中的经过消耗和服务消耗之和不能超过车辆的最大容量 Q 。

按照如上表述，单目标CARP由问题的数学模型可以表述为：

其中， ，表示第 h 条路线； 表示边缘序列 由第 h 个车辆提供服务， 表示这条路径只是被经过而没有被提供服务； 表示第 h 条服务路线包含的任务总数； 和 表示边任务总数和弧任务总数。式（2-16）和式（2-17）保证了每个任务只被服务一次。

基于上述单目标CARP模型，多目标CARP也必须满足以上3个约束条件，其数学模型可以定义为：

式（2-19）表示最小化一个解中的总花费（服务花费加经过花费），式（2-20）是最小化最长回路中的总花费。

2.4.2　基于免疫协同进化的限量弧路由问题

免疫克隆选择算法在应用时，主要包含以下几个模块 ^[53-56] 。

（1）选择合适的编码规则表示抗体，并利用某种机制产生初始种群。

（2）对抗体进行评价，抗体自身的亲和度（适应度）代表该解的质量，抗体与抗体间的亲和力反应种群的多样性。

（3）利用抗体的亲和度，抗体和抗体之间的亲和度计算每个抗体的克隆比例。

（4）高频变异，增加种群多样性。

（5）选择操作，选择种群中的优秀个体进入下一次进化，保证种群进化的质量。

1．抗体初始化

抗体就是优化问题的可行解，同遗传算法一样，算法开始前要先对解进行初始化。最简单的做法是随机初始化，但随机初始化的解容易使算法陷入局部最优，且不利于算法的收敛。为解决该问题，可以采用一些启发式算法生成初始解。如Usberti等在文献中提出的贪心随机启发式方法 ^[57] ，其原型是Golden在1983年提出的路径扫描方法 ^[47] 。

2．免疫克隆算子

免疫克隆操作是免疫克隆算法中一个主要步骤，克隆就是对种群进行复制。通过克隆种群中较好的解，可以增加算法在当前解的区域内搜索到更好解的可能性。如何评判解的优劣，取决于抗体与抗原之间的亲和度，抗原一般指需要优化的问题，所以在CARP中，抗体-抗原亲和度是指候选解所定影的最小路径消耗的值：

其中，lower_bound表示测试实例的下界，是解 x _i 的总花费； P _size 为父代抗体种群规模。

每个抗体的克隆比例不仅与抗体-抗原之间的亲和度有关，还会与抗体-抗体之间的亲和力有关。抗体亲和力越大，说明相似程度越大，抗体之间的抑制能力就越强。抗体 x _i 的克隆比例计算：

其中， 表示向下取整； d _i 反映了抗体 i 与其他抗体的亲和程度。

3．交叉、变异算子

为了生成新的种群，免疫克隆选择算法依然采用了交叉和变异算子来生成新的子代个体。交叉、变异算子作用于克隆之后的群体，能增加种群多样性，使算法不易陷入局部最优，也增加了算法找到全局最优的可能性。简单的变异算子有单任务插入：随机选择一个任务将其移动到另一个任务前面；两任务插入：随机选择两个不同位置的任务并交换其位置。

4．抗体修正算子

抗体修正是指对一些抗体在初始化时或交叉、变异后产生的不可行解的修正，将其修正为可行解，这些问题被称为约束优化问题，常用的方法有惩罚函数法 ^[58] 、多目标策略 ^[59] 、不可行解的修复 ^[60] 。惩罚函数法的本质是容许种群内个体在一定程度上可以违反约束条件，个体违反约束条件的程度由惩罚函数决定。多目标策略是将约束优化问题转化为多目标优化。不可行解的修复则是结合实际问题设计独特的修复算子将非可行解进行改进，使其从不可行解转变为可行解。

5．克隆选择算子

克隆选择算子就是选择子代中的优秀个体遗传到下一代作为新的父代，其目的是保留优秀基因，去除差基因，为种群选择正确的进化方向。随机排序法选择子代是由Runarsson和Yao提出的 ^[61] ，它根据亲和度函数和对约束条件的违背程度对抗体进行随机排序。具体排序准则为：当两个不同的抗体比较，且均为可行解，则根据两个抗体与抗原的亲和度排序；否则以 p _f 概率根据亲和度来排序，以1- p _f 概率根据对约束条件的违背度排序。 p _f 值大小一般为0.45。最终选择排序后的前 p _size 个抗体。对容量的违背程度定义为：

6．算法整体流程

免疫克隆选择算法求解CARP的主要流程如表2.1所示。