Problema del Viajero

Problema del viajero

Se busca minimizar las distancias. El viajero debe salir de un origen, pasar por todos los nodos solo una vez y volver a su origen. Tiene aplicaciones en logística, la industria automotriz, para medidas de seguridad, entre otros usos. Las variables de decisión son las aristas del grafo. $x_{ij}$ donde x es 1 si hago el viaje de i a j y 0 en caso contrario la función objetivo será

${\sum }_{i,j}{x}_{ij}\cdot d_{ij}$ donde d es la distancia entre cada lugar las restricciones son que solo se puede llegar a un lugar una sola vez:

${\sum }_i{x}_{ij}=1\forall j\ne i$ y solo se puede salir de un lugar una sola vez ${\sum }_j{x}_{ji}=1\forall i\ne i$ Para eliminar el problema de subtours se resuelve creando variables de decisión adicionales $u_j$ que valdrá un numero entero correspondiente al orden de lugares a los que llego, es decir, el primer destino j al que llegue tendrá la variable $u_j=1$ Se arma la restricción $u_i-uj+n\cdot x_{ij}\le n-1$ donde n es la cantidad de nodos o destinos.