Heurística del vecino más cercano

Introducción.

La heurística del vecino más cercano corresponde a un método constructivo: procedimiento iterativo que, en cada paso, añade un elemento hasta completar una solución. Usualmente son métodos deterministas y están basados en seleccionar, en cada iteración, el elemento con mejor evaluación.

La heurística del vecino más cercano trata de construir un Ciclo Hamiltoniano de bajo costo basado en el vértice más cercano a uno dado. El algorítmo se le debe a Rosenkrantz, Stearns y Lewis en 1977.

Pseudocódigo.

Sea:

  • \(V= \{1,2,...,n \}\) el conjunto de vértices (ciudades) a visitar.
  • \(c_{ij}\) el costo de ir desde el vértice \(i \in V\) al vértice \(j \in V\).
  • Puede haber un vértice inicial fijo \(i_0 \in V\)

Inicialización

Inicialización

  1. Inicializar:
    1. t ← i₀
    2. W ← V \ {i₀}
    3. Ruta ← [i₀]

Asigno a \(t\) el vértice actual, \(W\) representa el conjunto de vértices no visitados y \(Ruta\) la secuencia construída.

Iteración

Iteración

  1. Mientras W ≠ ∅ hacer:
    1. Encontrar j ∈ W tal que: c(t,j) = min { c_(t,k) : k ∈ W}.
    2. Añadir j a Ruta.
    3. W ← W \ {j}
    4. t ← j

Mientras queden vértices sin visitar (\(W \ne \emptyset\)):

  1. Encontrar el vértice \(j\) tal que ir de \(t\) a \(j\) cueste lo mínimo (\(c_{tj} = min(c_{tk});~~k \in W\)).

  2. Añadir el vértice encontrado (mínimo costo) a la ruta.

  3. Sacar del conjunto \(W\) el vértice \(j\) encontrado en literal a.

  4. Asigno a \(t\) el vértice \(j\) encontrado en litral a.

Para TSP

Cerrar ruta

  1. Regresar al nodo inicial i₀.

Ejemplo problema TSP en R

Durante las jornadas electorales en el Departamento de Córdoba, la Registraduría Nacional del Estado Civil debe realizar la recolección del material electoral sensible (urnas, formularios, actas y votos físicos) desde todos los municipios hacia el centro de consolidación ubicado en Montería.

Este proceso debe efectuarse después del cierre de las mesas de votación, ya que:

  • El material es confidencial y de alto valor legal.

  • Debe llegar lo más rápido posible al centro de cómputo departamental.

  • Se busca minimizar riesgos de pérdida, manipulación o retrasos.

  • Los recursos de transporte son limitados.

Para este proceso se dispone de un vehículo oficial escoltado, el cual parte desde Montería, debe visitar cada municipio para recoger el material y regresar a Montería.

Actualmente, las rutas se planifican de forma empírica, lo que genera mayores distancias recorridas,aumento en tiempos de consolidación de resultados, mayores costos de combustible y riesgos de seguridad por recorridos innecesarios.

Para lo anterior se dispone de una matriz de distancias entre municipios que se peude ver en el siguiente enlace: Matriz de distancias en km.

Datos

#Leer excel
library(readxl)
distancias_df <-  read_excel("C:/Users/000322041/OneDrive - UPB/UPB/Asignaturas_2026_1/Metodos_cuantitativos_logistica_27043/Clases/1_Heuristica_del_vecino_mas_cercano/distancias_municipios_cordoba.xlsx")

#Convertir a matriz numérica (para poder operar)
municipios <- distancias_df[[1]]  #Extraigo nombres de la primera columna
D <- as.matrix(distancias_df[,-1]) #Quito primera columna de nombres
rownames(D) <- municipios #Coloco nombres a filas de la matriz
colnames(D) <- municipios #Coloco nombres a columna de la matriz

Función para vecino más cercano

#Defino función llamada "vecino_mas_cercano" con parámetros de entrada D: matriz de distancias e inicio = 1 (nodo inicial)
vecino_mas_cercano <- function(D, inicio = 1) {
  
  n <- nrow(D) #Obtengo el número de vértices
  visitados <- rep(FALSE, n) #Creo un vector de visitados de tamaño n, con cada componente igual a FALSE
  ruta <- numeric(n + 1) #Creo un vector numérico vació en donde se va a guardar la ruta que se irá creando
  
  actual <- inicio #Defino el nodo actual desde el cual se buscará el vecino más cercano
  ruta[1] <- actual #El primer elemento de la ruta es el nodo inicial
  visitados[actual] <- TRUE #Marca el nodo inicial como visitado.
  
#Ciclo que se ejecuta n-1 veces (nodo inicial no incluído), en cada iteración agrego un nodo a la ruta
  for (k in 2:n) {

#Extrae la fila de la matriz correspondiente al nodo actual.Es decir, obtiene las distancias desde el nodo actual hacia todos los demás.    
    distancias <- D[actual, ]
    
#A todos los nodos ya visitados se les asigna distancia infinita (Inf). Esto evita que el algoritmo vuelva a elegirlos.
    distancias[visitados] <- Inf
    
#Encuentra el índice del nodo con menor distancia.
    siguiente <- which.min(distancias)
    
#Agrega el nuevo nodo a la ruta.
    ruta[k] <- siguiente
    
#Marca ese nodo como visitado.
    visitados[siguiente] <- TRUE
    
#El nodo recién agregado pasa a ser el nodo actual.
    actual <- siguiente
  }
  
# Cerrar ciclo. Una vez visitados todos los nodos, se regresa al nodo inicial.
  ruta[n + 1] <- inicio

#Devuelve el vector con los índices del recorrido completo
  return(ruta)
}

Ejecución del algoritmo

#Ejecuto la  función "vecino_mas_cercano"
ruta_indices <- vecino_mas_cercano(D, inicio = 1)

#Transformo la ruta de índices en nombres reales de municipios.
ruta_municipios <- municipios[ruta_indices]

Distancia total

#Función para calcular la distancia total de la solución
calcular_distancia <- function(D, ruta) {
  #Inicio variable acumuladora de kilómetros en ceros
  total <- 0
  #Creo ciclo un bucle que recorre todos los pares consecutivos de la ruta.
  for (i in 1:(length(ruta)-1)) {
    total <- total + D[ruta[i], ruta[i+1]]
  }
  return(total)
}

distancia_total <- calcular_distancia(D, ruta_indices)

Mapa del resultado

library(readxl)
library(dplyr)
library(leaflet)

#Coordenadas

coords_df <- read_excel("C:/Users/000322041/OneDrive - UPB/UPB/Asignaturas_2026_1/Metodos_cuantitativos_logistica_27043/Clases/1_Heuristica_del_vecino_mas_cercano/coordenadas.xlsx")

# Normalizar nombres (MUY IMPORTANTE para que coincidan)
coords_df$Municipio <- toupper(trimws(coords_df$Municipio))
municipios <- toupper(trimws(municipios))

#Recorrido en orden
ruta_municipios <- municipios[ruta_indices]

ruta_coords <- coords_df %>%
  slice(match(ruta_municipios, Municipio))

#Mapa
mapa <- leaflet(ruta_coords) %>%
  addTiles() %>%
  
  # Agregar marcadores
  addCircleMarkers(
    lng = ~longitud,
    lat = ~latitud,
    radius = 6,
    popup = ~Municipio
  ) %>%
  
  # Dibujar recorrido
  addPolylines(
    lng = ~longitud,
    lat = ~latitud,
    weight = 4
  )

#Mapa con orden de visitas
ruta_coords$Orden <- 1:nrow(ruta_coords)

mapa2<-leaflet(ruta_coords) %>%
  addTiles() %>%
  addCircleMarkers(
    lng = ~longitud,
    lat = ~latitud,
    radius = 6,
    popup = ~paste0(Orden, ". ", Municipio)
  ) %>%
  addPolylines(
    lng = ~longitud,
    lat = ~latitud,
    weight = 4
  )

Evaluación de la heurística

Para medir la calidad de una heurística existen diversos procedimientos,entre los que se encuentran los siguientes:

Comparación con la solución óptima

Aunque normalmente se recurre al algoritmo aproximado por no existir un método exacto para obtener el óptimo, o por ser este computacionalmente muy costoso, en ocasiones puede que dispongamos de un procedimiento que proporcione el óptimo para un conjunto limitado de ejemplos (usualmente de tamaño reducido o instancias pequeñas). Este conjunto de ejemplos puede servir para medir la calidad del método heurístico.

Normalmente se mide, para cada uno de los ejemplos, la desviación porcentual de la solución heurística frente a la óptima, calculando posteriormente el promedio de dichas desviaciones. Si llamamos \(c_h\) al costo de la solución del algoritmo heurístico y \(c_{opt}\) al coste de la solución óptima de un ejemplo dado, en un problema de minimización la desviación porcentual o GAP viene dada por la expresión:

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

Donde:

  • \(Z_h\): valor de \(Z\) de la solución heurística.
  • \(Z_{opt}\):valor de \(Z\) para la solución óptima.

Interpretación:

  • Si la \(\text{Desviación relativa} = 0\) la heurística encontró el óptimo.
  • Si la \(\text{Desviación relativa} > 0\) la heurística obtuvo una solución peor que el óptimo.
  • Mientras más pequeño sea el valor, mejor la heurística.

Si se utilizan \(n\) instancias:

\[ \text{Desviación promedio} = \frac{1}{n} \sum_{i=1}^n \frac{Z_{h_i}-Z_{opt_i}}{Z_{opt_i}} \]

Para problemas de maximización:

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

Interpretación:

  • Si la \(\text{Desviación relativa} = 0\) la heurística encontró el óptimo.
  • Si la \(\text{Desviación relativa} > 0\) la heurística obtuvo una solución peor que el óptimo.
  • Mientras más pequeño sea el valor, mejor la heurística.

Si se utilizan diferentes instancias:

\[ \text{Desviación promedio} = \frac{1}{n} \sum_{i=1}^n \frac{Z_{opt_i} - Z_{h_i} }{Z_{opt_i}} \]

Este mismo procedimiento se puede llevar a cabo comparando la heurística con un método exacto trucando, es decir, cuando establecemos a un método exacto, un límite de iteraciones, un límite de tiempo, de GAP, o de nodos.

Comparación con cotas (bounds).

En ocasiones el óptimo del problema no está disponible ni siquiera para un conjunto limitado de ejemplos. Un método alternativo de evaluación consiste en comparar el valor de la solución que proporciona la heurística con una cota del problema (inferior si es un problema de minimización y superior si es de maximización). Obviamente la bondad de esta medida dependerá de la bondad de la cota (cercanía de ésta al óptimo), por lo que, de alguna manera, tendremos que tener información de lo buena que es dicha cota. En caso contrario la comparación propuesta no tiene demasiado interés. Las cotas pueden provenir de:

  • Relajación lineal.
  • Relación lagranjiana.
  • Branch and bound.

Para minimización se calcula un GAP respecto a la cota así:

\[ GAP = \frac{Z_{heur}-LB}{LB} \]

Dónde:

  • \(Z_{heur}\): valor de \(Z\) de la solución heurística.
  • \(LB\): cota inferior del problema (lower bound).

Interpretación

  • \(GAP=0\): la solución heurística coincide con la cota.
  • \(GAP\) pequeño: solución cercana a la cota.
  • \(GAP\) grande: solución alejada de la cota.

Para maximización se calcula un GAP respecto a la cota así:

\[ GAP = \frac{UB - Z_{heur}}{UB} \]

Donde:

  • \(UB\): cota superior.
  • \(Z_{heur}\): valor de \(Z\) de la solución heurística.

Comparación con otras heurísticas.

Se ejecutan varios algoritmos heurísticos sobre el mismo conjunto de instancias y se comparan según:

  • Valor de la función objetivo \(Z\).
  • Tiempo computacional.
  • Estabilidad de los resultados (cuando se tienen elementos aleatorios).

Evaluación del TSP del Departamento de Córdoba.

Para la evaluación de la Heurística del vecino más cercano para resolver el TSP que recorre el departamento de Córdoba se tiene la siguiente solución truncada:

  • \(Z_{opt}= 1018.330\) para una solución con límite de tiempo en \(3600~s\).
  • \(Z_{h} = 1198.81\)

Al ser un problema de minimización se tiene:

\[\begin{align} \text{Desviación relativa}&= \frac{Z_h - Z_{opt}}{Z_{opt}}\\ \text{Desviación relativa}&= \frac{1198.81- 1018.330}{1018.300}\\ \text{Desviación relativa}&=0.1772366 \end{align}\]

\(\text{Desviación relativa} = 0.1772366 > 0\) la heurística obtuvo una solución peor que el óptimo exacto truncado. La solución fue aproximadamente \(17.72\%\) peor. Con uan diferencia en tiempo de \(3600~s\) a \(1~s\)