旅行商问题是一个著名的NP-hard问题,最早出现的描述是在1759年欧拉研究的骑士环游问题中,它的问题描述为:对于国际象棋中的64个方格,走访64个方格一次且仅一次,并且最终回到起始点。1954年一些学者为了解决旅行商问题采用线性规划的方法,从而取得了历史性的突破——解决了美国49个城市的巡回问题。后来又有相关的学者提出一种方法叫做分支限界法。但是在解决中等规模或超大规模TSP问题时,近似算法在解决该类问题时虽然效率较高但是无法获得高精度优化解（或者次优解）,智能算法虽然可以获得精度高于近似算法的解,但由于局部最优值的问题以及采用不同的优化策略从而产生不同的问题很难在合理时间内获得这个解。解决任何规模的旅行商问题的都将对各领域产生重要的意义,因为旅行商问题本身就有重要的实际意义和工程背景。基于上述问题,通过查阅文献资料发现遗传算法的全局优化思想在解决超大规模旅行商问题时具有很高的效率,但是遗传算法在解决该类问题时有三个问题较难克服。首先初始解精度如果不够在解决该类问题时由于收敛速度的问题无法在合理的时间内获得一个较好的解。及其由于超大规模旅行商问题城市点较大只能使用局部搜索策略,而搜索半径目前没有统一的标准,大部分采用随机算法,同样优化位置的选择目前也是采用随机策略,这样就会导致算法过分的依赖概率。通过上述的三个问题,本文首先采用的改进凸包算法,通过优化凸包的插值方法来使获得的解更加接近最优解。在解决小规模旅行商问题或在创建中等规模和超大规模初始种群时这种方法都有较强的鲁棒性。然后通过实验证明在遗传算法的局部优化过程中,优先优化获得优良解的区域可以更高的概率的获得优化解而提高算法的效率和精度。本文通过求解TSP实例库中的数据获得仿真实验数据,该实验数据表明本文的混合算法在求解超大规模旅行商问题时在效率和精度上表现较好。