Modelo TSP

El problema del TSP como un problema lineal (Winston, 2005) consiste en las ciudades 1, 2, 3, ..., N para i ≠ j. Teniendo en cuenta que:

• i = ciudad de origen (i=1,2,3,…,N)
• j = ciudad de destino (j=1,2,3,…,N)
• c_ij = distancia desde la ciudad i hasta la ciudad j
• c_ii = M
• M = número grande que asegura que no habrá viaje a la ciudad i inmediatamente después de dejar la ciudad i
• x _ij = { 1, si la solución al TSP va de la ciudad i a la ciudad j. 0, si no sucede así

De tal manera que la solución al problema se encuentra al resolver:

• Función objetivo: proporciona la distancia total de los arcos incluidos en un tour.
  

  

• Sujeto a las restricciones:
  • Llegada una vez a cada ciudad:
    

    

  • Abandona una vez a cada ciudad:
    

    

  • Restricción que evita que se presenten subtours:
    

    

  • Restricción de variables binarias (1 ó 0) y no negativas: