He encontrado una página de un profesor de la Universidad de Murcia con un reto interesante, al menos para la implementación de algoritmos de búsqueda en la asignatura de Inteligencia Artificial.
El reto consiste en, dado un mapa de carreteras comarcales y nacionales y de pueblos de España, encontrar una ruta que, empezando y terminando en Murcia, pase por todos los pueblos y recorra el menor número posible de kms, aunque para mí la restricción más interesante es que tarde ménos de 1 minuto en calcularse.
Más detalles (incluido el fichero con el grafo de las carreteras) en la propia página:
http://dis.um.es/~ginesgm/retoviajante.html
Ánimo.