The superpermutation problem is: what is the shortest word that contains every permutation of $k$ letters as a substring. This can phrased as a Travelling Salesman Problem, where the nodes of your graph are permutations, and the weight of edges correspond to the number of letters it takes to go from one permutation to another.
I have done some work on the above problem, and came up with some interesting ideas to get lower bounds. I am eager to try applying my methods on other graphs, and am trying to find significant, or at least not completely unmotivated, candidates.
So, my question is: what other mathematically interesting problems are concerned with finding lower bounds for the shortest weighted path in a (graph/family of graphs)?