限量弧路由规划问题(Capacitated Arc Routing Problem)是一个非常具有代表性的组合优化难题，CARP问题有广泛的社会应用：城市垃圾清理、信件投递、洒水车路径规划、冬季除雪路由优化和校车调度等。基于上述原因，CARP问题受到了国内外研究学者的广泛关注。然而，由于CARP本身存在多重约束，使得解空间高度离散，现有的算法均无法在对问题规模的多项式时间内找到全局最优解。而基于人工免疫系统的免疫克隆选择算法和基于协同进化理论的协同算法都是高度进化的、并行类进化算法，且成功应用于求解许多离散问题与组合优化问题。因此，我们考虑利用基于免疫协同进化理论的算法来对问题进行求解，来尽可能得到逼近最优解下界的次优解。本文主要工作如下：1)现有的解决CARP问题的进化类算法往往是通过随机选择子代来进行遍历式的局部搜索，这有利于找到新的测试实例下界，然而却需要花费较高的函数评价次数。而现实中CARP问题的任务变化具有一定实时性，我们的目的就是在一定的函数评价次数内寻找求解CARP问题的高效算法。基于上述原因，我们提出了一种解决该问题的新算法—免疫克隆选择算法(ICSA-CARP)。该算法首先利用强健的构造型启发式算法产生初始抗体种群，好的初始抗体有利于加速算法收敛；其次在框架上采用免疫克隆选择算法框架，克隆操作有利于将我们的计算资源集中于那些高质量的抗体；其次通过对同一抗体分裂得来的不同克隆抗体实行不同的变异策略，能促进抗体之间的合作和信息交换，提高种群的多样性，加快收敛；最后针对不同类型的不可行解设计了相应的抗体修正策略，使其更逼近最优解。数值实验表明，新算法得到的结果极具有竞争性。2)接下来，我们研究了CARP问题中更为复杂的模型—多目标限量弧路由问题(MO-CARP)。在2012年，梅一和唐珂提出了一种基于问题分解的memetic算法用于求解MO-CARP问题(D-MAENS)，该算法已经被证明在求解MO-CARP问题上优于现有的其它算法，但是仍然存在不足之处。首先在D-MAENS中，后代解的更替不够及时，降低了算法的收敛速度；其次在D-MAENS中，子种群的划分不够完善，容易缺失精英解。针对上述问题，本文提出了一种改进后的新算法ID-MAENS，新算法ID-MAENS针对D-MAENS的不足进行了两点改进。实验结果表明ID-MAENS在大规模测试问题egl上的24个实例中的20个找到了优于D-MAENS的结果，并且在其中9个测试实例上ID-MAENS找到的解集完全支配了D-MAENS的解集。3)针对MO-CARP问题，我们基于协同进化理论提出了多种群协同进化算法(MPCCA)。它首先利用一组方向向量将整个种群划分为不同的子种群，每个子种群都有自己独特的函数评价机制。这些子种群独立进化，但是在每次迭代开始之前，我们都要将这些子种群内个体进行合并并根据进化情况重新分配给各个子种群。同时在进化过程中，相邻的子种群可以通过邻域共享的机制进行合作。除此之外，MPCCA还增加了其它的特性，比如说：多种精英档案策略、快速非支配排序、拥挤度距离等。经过最后的实验表明MPCCA可以保持很好的多样性和快速的收敛性。本文工作得到了国家自然科学基金(No.61001202)，国家教育部博士点新教师基金(No.20100203120008)和中央高校基础科研业务费(K5051302028)的资助。