旅行商问题是著名的路径规划问题,在现实生活中有着广泛的应用。伴随着城市数目的增多,传统的算法在旅行商问题巨大搜索空间里的寻优能力越来越差,很难达到精确地求出最优解的目的。如何设计出一个性能高效的近似求解算法成了众多学者的研究重点。遗传算法以其优良的性能,擅长全局搜索的优点,成为了研究组合优化问题中常用的算法。但长期的实际应用中,暴露了遗传算法难以对局部空间进行搜索,导致算法进化后期搜索效率偏低,解质量不高的缺点。因此,近年来学者通过结合局部搜索来提升算法的性能。目前,解旅行商问题局部寻优较好的算子有opt的各种形式(2-opt,3-opt等)以及Lin-Kernighan(LK),然而因为LK的复杂性高,通常较少使用。另外,由于opt的固有特性,其各种形式的局部搜索算子都难较精细地对个体邻域进行搜索。综上所述,本文将单点插入算子(Single Insertion,SI)、交换算子(Swap)引入TSP问题的局部搜索,并结合2-opt,组成一种特有的局部搜索算子集合。同时,鉴于遗传算法在全局搜索能力上的优秀表现,将上述算子集合嵌入遗传算法,从而形成混合遗传算法(HGA),并以其对TSP问题求解。通过国际通用的TSPLIB中不同城市规模的数据进行测试,并对比5种算法的解质量,结果证明了该混合遗传算法的有效性。针对基于随机机会约束规划模型的旅行商问题,本文以基于TSPLIB测试算例生成的不确定旅行商问题测试数据对UHGA算法进行性能衡量和算法验证,并给出相应的实验结果分析。