本文所研究的限量弧路由问题(Capacitated Arc Routing Problem，CARP)是一个经典的组合优化问题。它在现实中具有非常广泛的应用，如冬季撒盐路由、城市垃圾清理、信件投递等现实应用均能够抽象为限量弧路由问题。基于上述原因，该问题在近年来越来越受到研究者的关注。然而，由于其问题本身的复杂性，现有的解决方法均无法在对问题规模的多项式时间内找到全局最优解。因此，我们考虑利用近似算法中的元启发式方法(Meta-heuristics)来对问题进行求解以得到尽可能逼近最优解的次优解。由限量弧路由问题的基本模型开始，我们设计了一个问题相关的全局修复算子。该全局修复算子能够很好地嵌入任意基于搜索的限量弧路由问题优化算法并提高其搜索效率。　　 由整个算法框架角度出发，模因演算法(Memetic Algorithms)在许多从实际出发的离散问题与组合优化问题上均得到了成功。它可看作是传统演化算法与局部搜索相结合而构成的混合算法框架。模因演算法中包含的局部搜索所带来的高选择压力使其能够比传统的演化算法更快地找到质量更好的解。当应用于限量弧路由问题时，我们发现传统的局部搜索(基于传统的小步长搜索算子的局部搜索)依旧难以对具有搜索吸引力的区域有效地进行开发，因而面临解无法跳出局部最优的风险。基于上述原因，我们提出了一个基于扩展邻域搜索的模因演算法以帮助这样的解跳出当前局部最优从而到达新的更好的局部最优解。经验证该算法能够得到质量远高于当前性能最优算法的解，尽管其所需计算消耗更大。　　 接下来，我们进一步研究了限量弧路由问题的两种更为复杂的模型：周期性限量弧路由问题与多目标限量弧路由问题。周期性限量弧路由问题为基本限量弧路由问题从单时期至多时期的一个扩展模型。该问题引入了最小化整个周期内所需车辆数目这一主要优化目标，而在基本限量弧路由问题中的唯一优化目标，即最小化回路总消耗，则变为次要优化目标。基于问题主要优化目标对传统搜索算子的敏感性较低这一现象，我们提出了一个将主要目标与次要目标分离进行优化的算法。具体来说，我们设计了一个专门优化主要目标的特定算子并将其在算法中的局部搜索之前进行调用。通过实验我们得出，在解决具有对传统搜索算子敏感性较低目标的问题时，将其与其余敏感性较高的目标分离进行优化将能够得到更好的结果。　　 多目标限量弧路由问题同时具有多目标优化问题与组合优化问题所导致的难度，这使其成为一个极具挑战性的问题。基于在多目标限量弧路由问题环境下对现有演化多目标优化策略的性能评估结果，我们将单目标限量弧路由优化方法与演化多目标优化策略的优势进行了有机地结合，并通过实验验证了这样的组合方式在性能上能够同时超越简单地扩展单目标限量弧路由算法与直接应用现有多目标演化算法框架这两种对于多目标限量弧路由问题的解决方法。　　 最后，我们对非确定限量弧路由问题进行了研究。至今为止，关于限量弧路由问题的大部分研究工作均集中于关注确定环境下的限量弧路由问题。在确定性限量弧路由问题中，包括任务需求量与顶点之间经过消耗等问题参数均为已知常数。然而，在许多现实应用问题中，这些问题参数的精确值无从得知，因此只能将其假设为落在某个特定区间范围之内。在此情况下，问题目标将不再是寻找某特定环境下的最优解，而是寻找在所有可能环境中鲁棒性较强的解。在本文研究工作中，我们根据实际需求为非确定限量弧路由问题定义了一个鲁棒性评价标准。同时，我们将现有的确定性限量弧路由问题测试集通过扩展从而对非确定限量弧路由问题生成了相应的测试集。