组合优化问题(Combinatorial Optimization Problems, COPs)在诸多领域具有广泛的实际应用。然而目前大多数组合优化问题(COPs)问题为NP难度问题，它还没有方法能在多项式时间内得到其最优解。实践表明，启发式算法能够在合理的时间内找到其近似解。然而随着问题规模的扩大，启发式算法的计算时间随之增加，随着可用数据的增加，问题的规模也在不断扩大。因此，开发设计高效的启发式算法来处理更大规模问题的需求显得日益迫切。而设计高效启发式算法的关键在于理解所考虑问题的本质，并以正确的方式集成优化各种有效方法。路径重链接(Path relinking)是对于难度问题的主要优化方法之一。本文的主要研究重点是通过理解问题本质以及路径重链接来提升启发式算法的性能。本文中，主要考虑两个具体的优化问题：关键节点检测问题(Critical Node Detection Problem,CNDP)和(Quality of Service,QoS)感知服务选择问题(QoS-aware Service Selection Problem,QSSP)。论文主要的工作如下：
　　(1)在单目标优化的背景下，研究了一种成熟的元启发式方法，即贪婪随机自适应搜索过程(Greedy Randomized Adaptive Search Procedure,GRASP)与混合的外部路径链接的性能改进。
　　外部路径重新链接是最近提出的一种元启发式方法。尽管路径链接被广泛用在贪婪随机自适应搜索过程中，但它仅限于路径连接的内部变体。因此，需要对外部路径连接与贪婪随机自适应搜索过程的混合外部路径连接进行研究。针对CNDP问题，提出了一种新的外路径连接贪婪随机自适应搜索过程混合方案。在新方案中，通过使用外部路径重新链接，将抓取迭代得到的结果与先前发现的高质量解决方案重新链接。外部路径重新链接通过探索两个解决方案之外的邻居来创建路径。计算实验表明，基于外部路径重新链接的算法在解决CNDP问题上优于其他变异的路径链接。此外，与其他方法相比，该算法找到了更高质量的解，并提高了文献中已知数据集16个实例中8个实例的最佳已知值。
　　(2)在多目标优化的背景下，研究了路径链接与交互式进化多目标优化(Evolutionary Multi-objective Optimization, EMO)杂交路径链接的性能改进问题。
　　由于许多组合优化问题(COPs)在本质上有多个目标，因此将用户偏好信息合并到优化过程中是找到最佳解决方案的唯一方法。我们提出了一种新的交互式EMO程序(用cdEMO表示)，它在优化过程中周期性地合并用户偏好信息，并将信息建模为凸锥。该算法利用用户偏好信息将帕累托(Pareto)无与伦比的解决方法分为若干有序类。然后，我们研究了路径重新链接如何支持cdEMO算法的性能。根据用户反馈的要求，路径重新链接提高了cdEMO算法14.3%的性能。计算实验表明，cdEMO算法能够更快地收敛到所需的解。由于cdEMO是一种通用的优化算法，因此它可以用于任何组合优化问题(COPs)。
　　(3)QSSP采用了先前提出的cdEMO的修改版本，这是一个具有高度重要性的现实问题，具有多个性质的目标。
　　我们批判地分析了目前大多数求解QSSP的方法所采用的尺度化方法，并找出了严重的缺点，如难以定义正确的权值向量进行聚合，以及找不到帕累托前沿非凸部分的能力。cdEMO算法通过合并用户偏好信息来解决这两个缺点。实验结果表明，采用路径重链接的改进型cdEMO是一种有效的QSSP方法。
　　(4)研究开发了有效的CNDP算法。通过对CNDP性质的理解，提出了一种适用于大型平面图CNDP的高效启发式算法。
　　证明了CNDP在平面图上的NP难度。由于目标函数的计算代价是O(n)，其中n是问题的大小，因此启发式算法的计算时间随着问题大小的增加而急剧增加。将目标函数转化为双目标函数。提出了一种利用平面图的特殊性质计算变换后的双目标函数的机制，可以通过使用特殊的平面图形的性质，在常数时间内计算被转换的双目标函数。能够用有效的方法开发一个大型图形的平面性需求。相比于最先近的一些方法，计算实验证明所提出的算法在运行时间和解法质量方面具有明显的优越性。