El problema del vendedor viajero puede considerarse un problema NP-duro. Para resolver mejor la mejor solución, se utilizaron muchos algoritmos heurísticos, como el recocido simulado, la optimización por colonias de hormigas, la búsqueda tabú y el algoritmo genético. Sin embargo, estos algoritmos o bien son propensos a caer en la optimización local o tienen un rendimiento de convergencia bajo o deficiente. Este artículo propone un nuevo algoritmo basado en el recocido simulado y la programación genética para resolver mejor el problema. En el algoritmo, utilizamos el recocido simulado para aumentar la diversidad de la población de Programación de Expresión Génica (GEP) y mejorar la capacidad de búsqueda global. Los resultados de los experimentos comparativos, utilizando seis instancias de referencia, muestran que el algoritmo propuesto supera a otros algoritmos heurísticos bien conocidos en términos de la mejor solución, la peor solución, el tiempo de ejecución del algoritmo, la tasa de diferencia entre la mejor solución y la solución óptima conocida, y la velocidad de convergencia de los algoritmos.