旅行商问题(’Traveling Salesman Problem, TSP)又称为推销员问题、货郎担问题,简称为TSP问题。该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,再回到原点的最小路径成本。如何找到在拜访每个地方一次后再回到起点的最短路径,规则虽然简单,但在地点数目增多后求解的时间迅速的增加。多年来全球数学家绞尽脑汁,试图找到一个高效的算法--能快速找到最优或近似最优的解。近几年,研究人员试图运用各种方法对TSP进行求解,但是,由于对TSP特性的认识的加深,试图使用精确算法求解TSP的研究基本销声匿迹,取而代之的是各种近似方法；试图使用单一方法求解TSP问题的研究在减少,而使用多种方法结合的研究逐渐占据研究的主流。针对该问题,本文研究不同的算法求解旅行商问题的优缺点,根据此引入了一种新的运算方式：基因片段插入。同时借鉴于粒子群优化算法的思想和郭涛算法,将分别考虑三种方法求解旅行商问题的新算法。首先是将基因片段插入方法和类粒子群优化算法相结合,通过若干次的迭代,可得到最优解或近似最优解。其次是基于基因片段插入的旅行商问题的演化算法研究,随机从其它个体选取一个基因片段,插入到当前进化的个体。通过若干次的迭代,可得到最优解或近似最优解。实验表明,此方法优于前面的算法。最后是将基因片段插入方法和郭涛算法相结合,对某个个体进行进化时,先利用郭涛算法对此个体中的基因片段进行翻转,后随机从其它个体选取一个基因片段,正向或反向插入到当前的个体中。从实验数据看,此算法是三种算法中最优的,它可较快找到最优解或近似最优解。