Comparación de Métodos de Solución para el TSP: Departamento del Magdalena

Solución Exacta (MILP) vs Heurística del Vecino Más Cercano

1. Introducción

El presente trabajo aborda el Problema del Agente Viajero (TSP), uno de los problemas fundamentales de la optimización combinatoria, mediante dos enfoques metodológicos complementarios:

1. Un modelo de Programación Lineal Entera Mixta (MILP), que permite obtener la solución exacta del problema.
   
2. La heurística del vecino más cercano (HVMC), utilizada como método constructivo de tipo greedy.

El objetivo principal consiste en determinar un tour hamiltoniano de costo mínimo que recorra un conjunto de 30 municipios del departamento del Magdalena, visitando cada uno exactamente una vez y retornando al punto de partida.

La comparación entre ambos enfoques se realiza en términos de calidad de la solución, tiempo computacional y estructura de la ruta generada.

El modelo MILP se formuló sobre un grafo completo ponderado \(G(V,A,C)\) e implementó en R mediante los paquetes ompr, ROI y ROI.plugin.symphony. Por su parte, la heurística del vecino más cercano fue desarrollada desde cero siguiendo el paradigma greedy clásico.

La entrada del problema corresponde a una matriz real de distancias en kilómetros entre los municipios. Se fijó como nodo inicial el municipio de Algarrobo, debido a su ubicación estratégica dentro del departamento y con el fin de garantizar consistencia en la comparación entre métodos.

Adicionalmente, este estudio permite evidenciar el compromiso existente entre calidad de solución y esfuerzo computacional, aspecto fundamental en problemas de optimización aplicados a contextos logísticos reales.

2. Planteamiento del problema

El TSP se define sobre un conjunto de municipios \(V = \{1,2,...,n\}\), junto con una matriz de distancias \(C = [c_{ij}]\), donde cada elemento representa el costo de desplazamiento entre dos municipios.

El problema puede interpretarse como la búsqueda de un ciclo hamiltoniano de costo mínimo en un grafo completo ponderado.

El objetivo es encontrar una ruta cerrada que cumpla con las siguientes condiciones:

• Visitar cada municipio exactamente una vez.
  
• Minimizar la distancia total recorrida.
  
• Regresar al nodo inicial.

En este estudio, se fija como nodo inicial el municipio de Algarrobo, decisión que responde a tres criterios fundamentales:

• Estandarización de la comparación: permite evaluar de manera consistente las diferencias entre el modelo exacto y la heurística.
  
• Sensibilidad de la heurística: dado que el vecino más cercano depende del nodo inicial, esta elección influye directamente en la solución generada.
  
• Aplicación práctica: Algarrobo puede interpretarse como un posible nodo logístico dentro del sistema de transporte analizado.

3. Metodología

3.1 Modelo exacto

Se utilizó un modelo de Programación Lineal Entera Mixta basado en la formulación MTZ, el cual permite eliminar subtours mediante variables auxiliares.

La función objetivo es: minimizar el costo total

\[ \min Z = \sum_{i \in V} \sum_{j \in V} c_{ij} x_{ij} \]

Sujeto a:

• Una única entrada por nodo
  
• Una única salida por nodo
  
• Eliminación de subtours

Este modelo garantiza la obtención de la solución óptima global.

3.2 Heurística del vecino más cercano

La heurística del vecino más cercano es un método constructivo de tipo greedy que construye una solución de manera secuencial.

En cada iteración, el algoritmo selecciona el nodo no visitado más cercano al nodo actual, sin considerar el impacto de dicha decisión en etapas futuras. Este comportamiento implica que la calidad de la solución depende del orden en que se construye la ruta.

3.3 Implementación en R

La implementación de la heurística se realizó en R mediante una estructura modular, lo que permite representar de manera clara cada etapa del algoritmo.

3.3.1 Lectura y preparación de datos

library(dplyr)
library(readxl)
distancias_df <- read_excel("Matriz_magdalena.xlsx")
municipios <- toupper(trimws(distancias_df[[1]]))
D <- as.matrix(distancias_df[,-1])

rownames(D) <- municipios
colnames(D) <- municipios

Explicación:

En este bloque se realiza la estructuración de los datos en formato matricial.

Se importa la matriz de distancias desde un archivo externo y se normalizan los nombres de los municipios para evitar inconsistencias en la indexación. Posteriormente, se construye la matriz \(D = [c_{ij}]\), que representa los costos de desplazamiento entre cada par de nodos del grafo completo.

3.3.2 Construcción de la solución

vecino_mas_cercano <- function(D, inicio = 1) {
  n <- nrow(D)
  visitados <- rep(FALSE, n)
  ruta <- numeric(n + 1)
  
  actual <- inicio
  ruta[1] <- actual
  visitados[actual] <- TRUE

Explicación:

Se inicializan las estructuras necesarias para la construcción de la solución: el vector de nodos visitados y la secuencia de la ruta. El algoritmo comienza en el nodo inicial, el cual es marcado como visitado.

3.3.3 Proceso iterativo

  for (k in 2:n) {
    distancias <- D[actual, ]
    distancias[visitados] <- Inf
    
    siguiente <- which.min(distancias)
    
    ruta[k] <- siguiente
    visitados[siguiente] <- TRUE
    actual <- siguiente
  }

Explicación:

En cada iteración se selecciona el nodo no visitado más cercano al nodo actual. Para ello, se excluyen los nodos visitados asignándoles un valor infinito y se elige el mínimo del conjunto restante.

3.3.4 Cierre del ciclo

  ruta[n + 1] <- inicio
  return(ruta)
}

Se garantiza que la solución corresponda a un ciclo hamiltoniano al regresar al nodo inicial.

3.3.5 Ejecución del algoritmo

municipios <- toupper(trimws(municipios))
inicio_alg <- which(municipios == "ALGARROBO")


ruta_indices <- vecino_mas_cercano(D, inicio_alg)
ruta_municipios <- municipios[ruta_indices]

Explicación:

Se fija el nodo inicial en Algarrobo y se ejecuta el algoritmo, obteniendo la secuencia de municipios recorridos. Previo a esto, los nombres de los municipios se normalizan (convertidos a mayúsculas y sin espacios extra) para asegurar que coincidan correctamente en la matriz y evitar errores al identificar el nodo inicial.

3.3.6 Cálculo de la distancia total

calcular_distancia <- function(D, ruta) {
  total <- 0
  for (i in 1:(length(ruta)-1)) {
    total <- total + D[ruta[i], ruta[i+1]]
  }
  return(total)
}

distancia_total <- calcular_distancia(D, ruta_indices)

coords_df <- read_excel("Coordenadas_Magdalena.xlsx")
coords_df$Municipio <- toupper(trimws(coords_df$Municipio))

ruta_coords <- coords_df %>%
  slice(match(ruta_municipios, Municipio)) %>%
  mutate(orden = 1:n())

Explicación:

Se evalúa la función objetivo sobre la solución generada, calculando la distancia total recorrida como la suma de los costos entre nodos consecutivos.

Posteriormente, se incorporan las coordenadas de cada municipio desde un archivo externo y se normalizan sus nombres para asegurar coincidencia con la matriz de distancias. Esto permite construir la ruta ordenada con la secuencia de municipios y sus posiciones geográficas, necesaria para la representación visual en mapas.

4. Resultados

4.1 Justificación de la evaluación

Dado que la heurística del vecino más cercano no garantiza la obtención de la solución óptima, su desempeño debe evaluarse mediante comparación con un valor de referencia.

En este caso, la solución óptima obtenida mediante el modelo MILP se utiliza como punto de referencia, permitiendo cuantificar la calidad de la solución heurística.

4.2 Solución exacta

El modelo MILP permitió obtener la solución óptima global del problema, con un valor de:

\[ Z_{opt} = 1061.56 \text{ km} \]

y un tiempo de cómputo de 212 segundos.

4.3 Solución heurística

La heurística generó una solución factible con un valor de:

\[ Z_{h} = 1187.73 \text{ km} \]

El tiempo de ejecución fue despreciable, lo cual evidencia su eficiencia computacional.

4.4 Representación espacial de las soluciones

Modelo exacto

La solución óptima presenta una trayectoria espacialmente coherente, con un recorrido compacto que evita desplazamientos innecesarios.

Heurística

La heurística muestra un comportamiento típico de los métodos greedy, con decisiones locales que generan saltos largos en etapas posteriores.

Comparación espacial

La solución exacta presenta una distribución más uniforme, mientras que la heurística evidencia menor eficiencia espacial.

4.5 Evaluación de la heurística

\[ \text{Desviación relativa} = \frac{Z_h - Z_{opt}}{Z_{opt}} \]

Sustituyendo valores:

\[ \frac{1187.73 - 1061.56}{1061.56} = \frac{126.17}{1061.56} \approx 0.1188 \approx 11.88\% \]

Esto indica que la solución heurística supera en aproximadamente un 11.88% el valor óptimo.

4.6 Comparación de métodos

Con el fin de sintetizar los resultados obtenidos, se presenta una comparación entre el modelo exacto y la heurística del vecino más cercano.

Comparación de métodos de solución para el TSP

Método	Distancia..km.	Tiempo	Desviación.relativa
Modelo exacto (MILP)	1061.56	212 s	0%
Vecino más cercano	1187.73	≈ 0 s	11.88%

4.7 Análisis de resultados

Se identifican tramos de alto costo que explican la diferencia observada:

• EL RETÉN → PLATO: 200.88 km
• EL BANCO → ALGARROBO: 191.98 km

Estos evidencian el impacto de decisiones locales sobre la solución global.

5. Conclusiones

El modelo exacto permitió obtener la solución óptima del problema, mientras que la heurística generó soluciones rápidas pero con una desviación del 11.88%.

Los resultados evidencian el compromiso entre calidad de solución y eficiencia computacional, así como la influencia del nodo inicial en la estructura del recorrido.

La heurística constituye una herramienta útil en contextos prácticos, aunque presenta limitaciones en términos de optimalidad.

Material complementario

Con el fin de garantizar la reproducibilidad del estudio, se anexan como material complementario:

1. código completo en R tsp_vs_hvc utilizado para la formulación e implementación del modelo MILP.

2. matriz de distancias en formato Excel correspondiente a los municipios del Magdalena matriz_distancia

3. archivo de coordenadas geográficas empleado para la visualización de la ruta óptima coordenadas

Estos archivos permiten replicar los resultados reportados en el presente informe y verificar la consistencia computacional del modelo implementado.