En la web de Princeton sobre el Problema de Viajante de Comercio, se reta a la comunidad científica a resolver el mayor problema TSP conocido hasta la fecha con 1.904.711 ciudades de todo el mundo.
El mejor resultado (a fecha de esta noticia) ha sido encontrado por Keld Helsgaun usando una variante de su algoritmo heurístico LKH. Su resultado de longitud total 7,516,353,779 fue encontrado el 23 de diciembre de 2003. Anteriormente, los mejores resultados encontrados fueron el de Helsgaun (16 Sept. 2003) con un valor de 7,517,285,610 y el de Hung Dinh Nguyen, Ikuo Yoshihara, Kunihito Yamamori, and Moritoshi Yasunaga (2 Junio 2003) con un resultado de 7,518,425,642 obtenidos a través de una combinación de iteraciones Lin-Kernighan y Algoritmos Genéticos.
La competición sigue abierta… ¿te animas?