摘要
旅行商问题是组合优化中一个经典的NP-难问题.本文研究旅行商问题的两个变形:带次模惩罚的分组奖励收集旅行商问题和聚集式路旅行商问题. 对于带次模惩罚的分组奖励收集旅行商问题，本文首先利用给出的带次模惩罚的分组奖励收集旅行商问题的实例，通过定义合适的权值函数和次模惩罚函数来构作带次模惩罚的奖励收集旅行商问题的实例.然后，将带次模惩罚的奖励收集旅行商问题的已有近似算法的输出解转化为带次模惩罚的分组奖励收集旅行商问题的解，进而设计带次模惩罚的分组奖励收集旅行商问题的近似算法.最后，我们对该近似算法进行理论分析,给出近似比为2kI,其中k是分组的个数，I是最大分组的基数. 对于聚集式路旅行商问题，本文分四种情形来考虑.首先，我们设计了路堆叠式起重机问题的近似算法和路乡村邮递员问题的近似算法,而这两个问题是我们求解聚集式路旅行商问题的子问题.然后，基于这些能够解决的子问题并调用路旅行商问题的近似算法，我们设计了聚集式路旅行商问题四种情形下的近似算法，近似比分别为8/3，2,8/3,13/4.
NETL