Heurística de Inserción

Introducción.

Las heurísticas de inserción son algoritmos constructivos utilizados para resolver el VRP mediante la construcción progresiva de rutas. La idea central consiste en:

  • Iniciar con una ruta parcial.

  • Seleccionar un cliente no visitado.

  • Insertarlo en la posición de la ruta que genere el menor incremento de costo.

El proceso continúa hasta que todos los clientes han sido asignados a alguna ruta, respetando las restricciones del problema.

Estas heurísticas son particularmente útiles cuando se desea construir soluciones de manera gradual, controlando el impacto de cada decisión sobre el costo total.

Las variantes más comunes son:

  1. Inserción más cercana (Nearest Insertion): se selecciona el cliente más cercano a cualquier nodo ya visitado.
  2. Inserción más barata (Cheapest Insertion): se inserta el cliente cuya inserción produce el menor incremento de costo.
  3. Inserción más lejana (Farthest Insertion): se selecciona primero el cliente más lejano al depósito, lo cual suele generar mejores soluciones iniciales.

Suele usarse para VRP la Cheapest Insertion Global como versión muy útil dentro de las heurísticas de inserción y, además, es la que mejor se adapta a un VRP con capacidad y tamaño de flota, porque en cada iteración evalúa todas las rutas y todos los clientes no asignados y elige la inserción que menos incrementa el costo total.

Idea fundamental.

La heurística Cheapest Insertion Global construye las rutas de forma progresiva insertando clientes en las posiciones donde el incremento de costo sea mínimo.

El procedimiento funciona así:

  1. Inicialmente todas las rutas contienen solo el depósito: \((0, 0)\)
  2. Se selecciona un cliente inicial para comenzar la primera ruta.
  3. En cada iteración se evalúan:
  • Todos los clientes no asignados,
  • Todas las rutas existentes,
  • Todas las posiciones posibles dentro de cada ruta
  1. Se calcula el incremento de costo de cada inserción posible.
  2. Se selecciona la inserción que produce el menor aumento de distancia (costo).
  3. El proceso continúa hasta que:
  • Todos los clientes han sido asignados, o
  • Se requiere crear una nueva ruta (si aún hay vehículos disponibles).

Cálculo del costo de inserción

Si un cliente \(k\) se inserta entre dos nodos consecutivos \(i\), \(j\) el incremento del costo está dado por:

\[ \Delta_{ijk} = c_{ik} + c_{kj} - c_{ij} \]

Donde:

  • \(c_{ik}\): distancia (costo) entre \(i\) y \(k\).
  • \(c_{kj}\): distancia (costo) entre \(k\) y \(j\).
  • \(c_{ij}\): distancia (costo) entre \(i\) y \(j\).

Este valor representa el incremento de distancia total de la ruta al insertar el cliente.

Pseudocódigo.

A continuación se presenta el pseudocódigo de la heurística de Inserción Cheapest Insertion Global, incorporando explícitamente las restricciones de capacidad del vehículo \(Q\) y tamaño máximo de la flota \(K\).

Variables

  • \(V\): conjunto de clientes.
  • \(0\): depósito.
  • \(d_i\): demanda del cliente \(i\).
  • \(Q\): capacidad del vehículo.
  • \(R\): conjunto de rutas.
  • \(U\): clientes no asignados.
  • \(c_{ij}\): costo entre \(i\) y \(j\).

Inicialización

Inicialización

  1. Inicializar:
    1. R←∅
    2. U←V
    3. Seleccionar cliente inicial i ∈ U
    4. Crear ruta inicial: r=(0,i,0)
    5. R←{r}
    6. U←U∖{i}
    7. demanda(r) = di

En la inicialización:

  • Se inicia con ruta vacía (sin vértices) \(R \leftarrow \emptyset\).
  • Se asigna a \(U\) el conjunto de vértices no visitados.
  • Se selecciona un vértice \(i \in U\) del conjunto de clientes no visitados.
  • Se crea una ruta inicial \(r = \text{depósito} \rightarrow i \rightarrow \text{depósito}\).
  • Se agrega \(r\) al conjunto de rutas \(R\).
  • Se elimina del conjunto de vértices no visitados \(U\) el vértice visitado \(i\) de la ruta \(r\).
  • Se calcula la demanda para la ruta inicial \(r\).

Iteración

Iteración

  1. Mientras 𝑈 ≠ ∅.

    1. Para cada cliente k ∈ U

    2. Para cada ruta r ∈ R

    3. Para cada arco (i,j) en r

      Calcular costo de inserción: Δ_ijk=c_ik+c_kj−c_ij

    4. Verificar capacidad

      demanda(r) + d_k ≤ Q

    5. Seleccionar inserción a menor costo:

      (i∗,j∗,k∗)=min{Δijk}

    6. Insertar k* en la posición correspondiente:

      rnew = (…,i∗,k∗,j∗,…)

    7. Actualizar la demanda de la ruta:

      demanda(rnew)=demanda(r)+dk∗

    8. Actualizar el conjunto de clientes no asignados:

      U←U∖{k∗}

    9. Si no existe inserción factible y

      ∣R∣<K

      Crear una nueva ruta con el cliente k:

      rnew=(0,k,0)

      Actualizar

      R←R∪{rnew} U←U∖{k}

Durante la iteración:

  • Explora todas las opciones posibles:
    • Cada cliente no asignado \(k\)
    • Cada ruta \(r\)
    • Cada posición dentro de la ruta: arco \((i, j)\)
  • Calcula el costo de ingresar ese cliente en esa posición \(\Delta_{ijk} = c_{ik} + c_{jk} - c_{ij}\)
  • Filtra las intercepciones factibles (que no violen la capacidad del vehículo)
  • Elige la mejor inserción global (La que tenga el menor incremento de costo)
  • Realiza la inserción (Inserta \(k*\) en la mejor posición encontrada)
  • Actualiza el sistema:
    • Demanda de la ruta
    • Elimina cliente de conjunto no visitados \(U\)
  • Si no hay inserciones factibles y hay vehículos, crea nueva ruta con dicho cliente.

Ejemplo heurística de Inserción para problema VRP 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 inmediatamente después del cierre de las mesas de votación, debido a 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 y seguridad son limitados.

Para esta operación se dispone de una flota de \(12\) vehículos oficiales escoltados, cada uno con capacidad máxima de \(1.5\) toneladas, los cuales parten desde Montería, visitan un subconjunto de municipios para recolectar el material electoral y posteriormente regresan al centro de consolidación.

Cada municipio genera una cantidad estimada de material electoral (expresada en peso o número de cajas), por lo que la asignación de municipios a cada vehículo debe respetar la capacidad máxima de transporte. El peso del material electoral por municipio se encuentra disponible en el siguiente enlace: Peso de material electoral por municipio.

Adicionalmente, se dispone de una matriz de distancias en kilómetros entre municipios: Matriz de distancias en km.

Actualmente, las rutas se planifican de forma empírica, lo que genera:

  • mayores distancias recorridas,

  • incremento en los tiempos de consolidación de resultados,

  • mayores costos de combustible,

  • y mayores riesgos de seguridad por recorridos innecesarios.

En consecuencia, se requiere diseñar un modelo de ruteo de vehículos capacitado (Vehicle Routing Problem, VRP) que permita determinar:

  • qué municipios debe atender cada vehículo,

  • el orden óptimo de visita en cada ruta,

  • y minimizar la distancia total recorrida por la flota.

Datos

library(readxl)
library(dplyr)

#Se lee el archivo de Excel que contiene la matriz de distancias entre municipios
distancias_df<- read_excel("C:/Users/000322041/OneDrive - UPB/UPB/Asignaturas_2026_1/Metodos_cuantitativos_logistica_27043/Clases/3_Heuristica_Insercion_VRP/distancias_municipios_cordoba.xlsx")

#Matriz de distancias
municipios <- distancias_df[[1]]  #Extraer la primera columna que contiene los nombres de los municipios
D <- as.matrix(distancias_df[,-1]) #Construir la matriz de distancias eliminando la primera columna
rownames(D) <- municipios #Asignar nombres de filas y columnas a la matriz
colnames(D) <- municipios

#dataframe de demandas
demandas_df <- read_excel("C:/Users/000322041/OneDrive - UPB/UPB/Asignaturas_2026_1/Metodos_cuantitativos_logistica_27043/Clases/3_Heuristica_Insercion_VRP/demanda.xlsx")

#Matriz de demanda
demandas <- demandas_df$demanda #Crear vector de demandas
names(demandas) <- demandas_df$Municipio #Asignar nombres al vector de demandas para acceder por municipio

#Capacidad del vehículo (toneladas)
Q <- 1.5

#Nodo depósito (punto de origen y regreso de las rutas)
deposito <- "Monteria"

#Tamaño de flota (Número máximo de vehículos disponibles)
K <- 12

Función Inserción Cheapest Insertion Global

cheapest_insertion <- function(D, demandas, Q, K, deposito){
  
  clientes <- setdiff(rownames(D), deposito)
  no_asignados <- clientes
  
  rutas <- list()
  demanda_ruta <- c()
  
  # Ruta inicial
  i <- no_asignados[1]
  rutas[[1]] <- c(deposito, i, deposito)
  demanda_ruta <- c(demandas[i])
  
  no_asignados <- setdiff(no_asignados, i)
  
  while(length(no_asignados) > 0){
    
    mejor_delta <- Inf
    mejor_cliente <- NULL
    mejor_ruta <- NULL
    mejor_pos <- NULL
    
    for(k in no_asignados){
      
      for(r in 1:length(rutas)){
        
        ruta <- rutas[[r]]
        
        if(demanda_ruta[r] + demandas[k] <= Q){
          
          for(pos in 1:(length(ruta)-1)){
            
            i <- ruta[pos]
            j <- ruta[pos+1]
            
            delta <- D[i,k] + D[k,j] - D[i,j]
            
            if(delta < mejor_delta){
              
              mejor_delta <- delta
              mejor_cliente <- k
              mejor_ruta <- r
              mejor_pos <- pos
              
            }
          }
        }
      }
    }
    
    if(!is.null(mejor_cliente)){
      
      ruta <- rutas[[mejor_ruta]]
      
      ruta <- append(ruta, mejor_cliente, after = mejor_pos)
      
      rutas[[mejor_ruta]] <- ruta
      
      demanda_ruta[mejor_ruta] <- demanda_ruta[mejor_ruta] + demandas[mejor_cliente]
      
      no_asignados <- setdiff(no_asignados, mejor_cliente)
      
    } else {
      
      if(length(rutas) < K){
        
        nuevo <- no_asignados[1]
        
        rutas[[length(rutas)+1]] <- c(deposito, nuevo, deposito)
        
        demanda_ruta <- c(demanda_ruta, demandas[nuevo])
        
        no_asignados <- setdiff(no_asignados, nuevo)
        
      } else {
        
        stop("No es posible asignar todos los clientes con la flota disponible")
        
      }
    }
  }
  
  return(rutas)
}

Ejecutar algoritmo

#Se ejecuta la función y se obtienen las rutas resultantes.
rutas <- cheapest_insertion(D, demandas, Q, K, deposito)
rutas

Cantidad de rutas

length(rutas)

Cargas de cada ruta

sapply(rutas, function(r) sum(demandas[r]))

Costo de las rutas

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

distancias <- sapply(rutas, distancia_ruta, D)
distancia_total <- sum(distancias)

Resumen de resultados

data.frame(
  Ruta = 1:length(rutas),
  Distancia_km = sapply(rutas, distancia_ruta, D),
  Carga = sapply(rutas, function(r) sum(demandas[r]))
)

Mapa

#Datos
library(readxl)
library(dplyr)
library(leaflet)

#Se lee el archivo de coordenadas geográficas de los municipios.
coords_df <- read_excel("C:/Users/000322041/OneDrive - UPB/UPB/Asignaturas_2026_1/Metodos_cuantitativos_logistica_27043/Clases/3_Heuristica_Insercion_VRP/coordenadas.xlsx")
coords_df$Municipio <- toupper(trimws(coords_df$Municipio)) #Estandarizan los nombres de los municipios
municipios <- toupper(trimws(municipios)) #Estandarizan los nombres del vector municipios


#Preparación de rutas 

#lapply aplica una función a cada ruta para convertirla en coordenadas.
rutas_coords <- lapply(rutas, function(ruta){ #contiene las rutas generadas por Clarke & Wright.
  
  ruta_municipios <- toupper(ruta) #Convierte los nombres de los municipios de la ruta a mayúsculas para garantizar coincidencia con coords_df.
  
  coords_df %>%
    slice(match(ruta_municipios, Municipio)) #Encuentra la posición de cada municipio de la ruta dentro del dataframe de coordenadas. Slece Selecciona esas filas en ese mismo orden.
  
})

#Paleta de colores
colores <- colorFactor(rainbow(length(rutas)), domain = 1:length(rutas)) #Se genera una función de colores para diferenciar rutas. rainbow() crea colores distintos, length(rutas) define cuántos colores se necesitan. 

#Crear mapa: Se crea un mapa interactivo vacío.
mapa <- leaflet() %>%
  addTiles()

#Dibujar cada ruta
for(i in 1:length(rutas_coords)){ #Se recorre cada ruta generada por el algoritmo.
  
  ruta_df <- rutas_coords[[i]] #Se obtiene el dataframe de coordenadas de la ruta i.
  
  mapa <- mapa %>%
    addPolylines(
      lng = ruta_df$longitud,
      lat = ruta_df$latitud,
      color = colores(i),
      weight = 4
    ) %>%
    
    addCircleMarkers(
      lng = ruta_df$longitud,
      lat = ruta_df$latitud,
      radius = 5,
      color = colores(i),
      popup = paste("Vehículo", i, "<br>", ruta_df$Municipio)
    )
}

mapa