Heurística de ahorro de Clarke & Wright

Introducción.

La heurística de ahorros de Clarke y Wright es un algoritmo constructivo para resolver el Vehicle Routing Problem (VRP). Su objetivo es reducir el costo total de las rutas combinando clientes en un mismo recorrido cuando hacerlo genera un ahorro en distancia o costo de transporte.

Existen dos versiones generales de la heurística. La versión paralela del algoritmo construye todas las rutas simultáneamente, evaluando las posibles combinaciones de clientes según el ahorro que producen, mientras que la versión secuencial que construye las rutas una a la vez. En este apartado se tratará la versión paralela, al ser la versión más usada.

Idea fundamental.

Inicialmente se considera que cada cliente es atendido por un vehículo independiente, si se representa el depósito por \(0\), y los clientes por \(i\), la solución inicial está formada por \(n\) rutas de la forma:

\[ (0, i ,0) \]

Esto es:

Cada vehículo sale del depósito \(\rightarrow\) atiende a un cliente \(\rightarrow\) regresa al depósito.

Corresponde a una solución “factible”, pero “ineficiente”, ya que el número de rutas es igual al número de clientes. La heurística busca fusionar rutas cuando hacerlo reduce el costo total.

Cálculo del ahorro.

Para cada par de clientes \(i, j\) se calcula el ahorro \(S_{ij}\) de visitarlos en una misma ruta:

\[ S_{ij} = c_{0i} + c_{oj} - c_{ij} \]

Donde:

  • \(c_{0i}\): costo entre el cliente \(i\) y el depósito.
  • \(c_{0j}\): costo entre el cliente \(j\) y el depósito.
  • \(c_{ij}\): costo entre los cliente \(i\) y \(j\).

El valor \(S_{ij}\) representa la reducción en costo al unir los clientes \(i\) y \(j\) en una misma ruta en lugar de atenderlos por separado. Un ahorro grande indica que es conveniente unir esos clientes.

Pseudocódigo.

A continuación se presenta el pseudocódigo de la heurística de ahorros de Clarke y Wright en su versión paralela, 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 \in V\)
  • \(Q\): capacidad de vehículo.
  • \(K\): tamaño de flota.
  • \(R\): conjunto de rutas.
  • \(c_{ij}\): costo entre \(i\) y \(j\).

Inicialización

Inicialización

  1. Inicializar:

    1. R ← ∅

    2. Para cada cliente i ∈ V.

      Crear ruta r_i = (0,i,0)

      demanda(r_i) = d_i

      R ← R ∪ {r_i}

    3. Calcular ahorros:

      S_ij = c_(i0) + c_(0j) − c_(ij) ∀ i ≠ j

    4. Crear lista L con todos los pares (i,j)

    5. Ordenar L de mayor a menor según S_ij.

  • \(R\) representa el conjunto de rutas actuales.
  • Cada cliente inicia en una ruta individual.
  • \(L\) es la lista ordenada de ahorros.

Iteración

Iteración

  1. Para cada par (i,j) ∈ L hacer:

    1. Sea r_i la ruta que contiene al cliente i

    2. Sea r_j la ruta que contiene al cliente j

    3. Si r_i ≠ r_j entonces:

      1. Verificar que i sea extremo de r_i

      2. Verificar que j sea extremo de r_j

      3. Verificar capacidad: demanda(r_i) + demanda(r_j) ≤ Q

      4. Verificar tamaño de flota: |R| − 1 ≥ K

    4. Si todas las condiciones se cumplen

      1. Fusionar rutas: r_new = r_i ⊕ r_j

      2. Demanda nueva: demanda(r_i) + demanda(r_j)

      3. R ← (R  {r_i,r_j}) ∪ {r_new}

Durante la iteración:

  • Se revisan los pares de clientes según el orden de mayor ahorro.

  • Solo se fusionan rutas si se cumplen las condiciones:

    • Los clientes están en rutas distintas
    • Ambos son extremos de sus rutas-
    • No se viola la capacidad del vehículo
    • No se reduce el número de rutas por debajo del tamaño de flota permitido

Finalización

Finalización

  1. Terminar cuando

    1. Se hayan evaluado todos los pares de L, o
    2. No existan fusiones factibles adicionales.

  2. El conjunto R contiene todas las rutas finales

Ejemplo 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/2.Heuristica_ahorros_Clarke_Wright/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/2.Heuristica_ahorros_Clarke_Wright/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 Ahorros de Clarke & Wright

clarke_wright <- function(D, demandas, Q, K, deposito){
  
  clientes <- setdiff(rownames(D), deposito) #Se construye un vector con todos los clientes, eliminando el depósito.
  
  #Rutas iniciales
  rutas <- list() #lista donde se guardarán las rutas
  demanda_ruta <- c() #demanda total transportada en cada ruta
  
  #Se crea una ruta inicial por cada cliente:
  for(i in clientes){
    rutas[[length(rutas)+1]] <- c(deposito, i, deposito) #Agregar un nuevo elemento al final de una lista
    demanda_ruta <- c(demanda_ruta, demandas[i])
  }
  
  # Calcular ahorros
  ahorros <- data.frame() #Se crea un dataframe vacío donde se guardarán los ahorros
  
  for(i in clientes){
    for(j in clientes){ #Se comparan todos los pares de clientes
      
      if(i < j){ #Evita duplicar pares:
        
        s <- D[i,deposito] + D[deposito,j] - D[i,j] #Fórmula del ahorro de Clarke & Wright.
        
        ahorros <- rbind(ahorros, #Se guarda, apila por filas, cliente i, cliente j, Ahorro
                         data.frame(i=i,
                                    j=j,
                                    ahorro=s))
      }
    }
  }
  
  # Ordenar ahorros
  ahorros <- ahorros[order(-ahorros$ahorro),] #Los ahorros se ordenan de mayor a menor.
  
  #Función para encontrar la ruta de un cliente. Busca en todas las rutas si el cliente aparece. Si lo encuentra retorna el índice de la ruta. Si no lo encuentra retorna NULL.
  
  encontrar_ruta <- function(cliente){
    
    for(k in 1:length(rutas)){
      if(cliente %in% rutas[[k]]){
        return(k)
      }
    }
    
    return(NULL)
  }
  
  # Algoritmo principal
  for(k in 1:nrow(ahorros)){ #Se recorren los pares de clientes según el orden de ahorro.
    
    if(length(rutas) <= K){ #Si ya se tiene un número de rutas menor o igual al número de vehículos, se detiene el algoritmo.
      break
    }
    
    #Clientes a evaluar: se toman los clientes del par actual.
    i <- ahorros$i[k] 
    j <- ahorros$j[k]
    
    ri <- encontrar_ruta(i) #Identificar rutas: se identifica donde está y donde está j. Con la función creada.
    rj <- encontrar_ruta(j)
    
    if(ri != rj){ #Solo se pueden fusionar rutas si los clientes están en rutas diferentes.
      
      ruta_i <- rutas[[ri]] #Se extraen las rutas.
      ruta_j <- rutas[[rj]]
      
      #Posiciones: se verifica si el cliente está al inicio de la ruta o al final de la ruta, esto es necesario porque Clarke & Wright solo permite fusionar extremos de rutas.
      i_inicio <- ruta_i[2] == i
      i_final  <- ruta_i[length(ruta_i)-1] == i
      
      j_inicio <- ruta_j[2] == j
      j_final  <- ruta_j[length(ruta_j)-1] == j
      
      #Verificar capacidad: solo se fusionan rutas si la demanda total no supera la capacidad del vehículo.
      if(demanda_ruta[ri] + demanda_ruta[rj] <= Q){
        
        nueva_ruta <- NULL
        
        # 1: i final + j inicio
        if(i_final & j_inicio){
          nueva_ruta <- c(ruta_i[-length(ruta_i)], ruta_j[-1])
        }
        
        # 2: j final + i inicio
        else if(j_final & i_inicio){
          nueva_ruta <- c(ruta_j[-length(ruta_j)], ruta_i[-1])
        }
        
        # 3: i inicio + j inicio (invertir i)
        else if(i_inicio & j_inicio){
          nueva_ruta <- c(rev(ruta_i[-1]), ruta_j[-1])
        }
        
        # 4: i final + j final (invertir j)
        else if(i_final & j_final){
          nueva_ruta <- c(ruta_i[-length(ruta_i)], rev(ruta_j[-length(ruta_j)]))
        }
        
        if(!is.null(nueva_ruta)){ #Si la unión fue válida.
          
          rutas[[ri]] <- nueva_ruta #Se actualiza la ruta.
          
          demanda_ruta[ri] <- demanda_ruta[ri] + demanda_ruta[rj] #Se suma la demanda de ambas rutas.
          
          rutas[[rj]] <- NULL #Se elimina la ruta que fue fusionada.
          demanda_ruta <- demanda_ruta[-rj] #Se elimina la demanda asociada.
        }
      }
    }
  }
  
  return(rutas) #La función devuelve la lista de rutas generadas.
}

Ejecutar algoritmo

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

Cantidad de rutas

length(rutas)

Cargas de cada ruta

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/2.Heuristica_ahorros_Clarke_Wright/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