旅行商问题是经典的NP完全问题,被组合优化领域的学者广泛研究。它衍生出了很多变种问题,比如着色旅行商问题、多旅行商问题、车辆路径问题等。旅行商问题可应用在安排生产作业任务等实际应用场景,着色旅行商问题可应用在多桥加工系统等实际应用场景,都有十分重要的研究意义。旅行商问题为给定具有距离信息的若干城市,求出旅行商从一个城市出发走完所有城市后返回该城市所需的最短距离。目前,将机器学习的算法和启发式算法进行结合所产生的混合算法已经被证实可以产生优于启发式算法的解。因此,在已有最好的启发式LKH（Lin-Kernighan-Helsgaun）算法和深度学习模型Att-GCRN（Graph Convolutional Residual Network with Attention mechanism）网络的基础上提出了一个混合算法Att-GCRN+LKH。该算法使用了深度学习网络对问题的特征进行了提取,并且将所提取的特征有效转换为LKH算法中的关键概念候选集。其在4组旅行商问题的数据集上进行了实验测试,实验结果表明了所提出的混合算法在4组数据集上效果均超过了纯机器学习算法,且和纯启发式算法相比差距保持在千分之一之下。同时对着色旅行商问题进行了研究,该问题是在旅行商问题的基础上,对旅行商以及城市分别进行了着色,指定颜色的旅行商只能访问相同颜色的城市。着色旅行商问题主要采用启发式算法进行求解。针对问题的特性,基于启发式算法ITPLS（Iterated Two-Phase Local Search）算法,提出了一个混合搜索算法。该算法运用了两阶段搜索的思想,并在搜索最优路径中,有效分离出了着色旅行商问题中可用求解旅行商问题的算法求解的部分,从而有效地将求解旅行商问题的LKH算法成功应用到了求解着色旅行商问题的算法之中。其在2组着色旅行商问题的数据集上进行了实验测试,实验结果表明了所提出的ITPLS+LKH混合算法在14个算例上有9个结果达到或超过了对比算法的实验结果。