旅行商问题是一个实用背景广泛,并且有着重要理论价值的组合优化难题,该问题的一个显著特点是描述简单,但很难得到最优解。因为旅行商问题在工程技术领域的应用十分广泛,所以具有很高的研究价值。由于旅行商问题的时间复杂度很大,精确算法只能求解规模很小的旅行商问题,所以当求解规模较大的旅行商问题时,常常采用近似算法,遗传算法是一种常见的求解旅行商问题的近似算法。因为字符编码在求解旅行商问题时,拥有信息表达简单、直观的特点,所以目前在解决旅行商问题时,一般使用的都是字符型编码的遗传算法。但是字符型编码由于其自身的特点,在求解旅行商问题时存在会产生非法染色体、计算效率低的缺点,其效果并不是很理想。本研究提出了一种新的求解旅行商问题的遗传算法编码方式,将其与字符型编码进行比较,证明其在交叉的时候不会产生非法的染色体,并且实验结果表明其能更快的找到最优解,这两个优点足以证明这种新的编码方式更适合求解旅行商问题。