Como resolver um problema de Vendedor ambulante em python? Não encontrei nenhuma biblioteca, deve haver uma maneira de usar funções scipy para otimização ou outras bibliotecas.

Minha solução de força bruta hacky-extremelly-preguiçoso-pitônica é:

tsp_solution = min( (sum( Dist[i] for i in izip(per, per[1:])), n, per) for n, per in enumerate(i for i in permutations(xrange(Dist.shape[0]), Dist.shape[0])) )[2]

onde Dist (numpy.array) é a matriz de distância. Se o Dist for muito grande, isso levará uma eternidade.

Sugestões?