| Ruta | Secuencia |
|---|---|
| Depósito | 1 |
| Cliente_1 | 1 |
| Cliente_4 | 4 |
| Cliente_3 | 3 |
| Cliente_5 | 5 |
| Cliente_2 | 2 |
| Depósito | 1 |
Algoritmo Genetico VRP
Optimización Inteligente de Rutas con Algoritmos Genéticos y OSRM
Este proyecto implementa una solución al clásico Problema de Ruteo de Vehículos (VRP) utilizando un algoritmo genético personalizado, adaptado para trabajar con distancias reales calle a calle gracias a la integración con OSRM (Open Source Routing Machine). A diferencia de los enfoques tradicionales que usan distancias euclidianas o heurísticas genéricas, esta implementación utiliza datos reales de vialidad urbana, lo que la vuelve aplicable a escenarios logísticos reales, especialmente en entornos urbanos complejos.
El sistema incluye:
Algoritmo genético diseñado desde cero en R.
Cálculo dinámico de rutas utilizando OSRM.
Visualización interactiva con Leaflet
Este proyecto puede ser extendido fácilmente a entornos de logística urbana, planificación de entregas o simulaciones de movilidad. Ideal como base para prototipos de optimización logística urbana, para empresas de última milla o investigadores en inteligencia computacional.
Tecnologias Utilizadas
Este proyecto combina herramientas estadísticas, geográficas y web para construir una solución integral al problema de ruteo de vehículos. A continuación se detallan las tecnologías principales empleadas:
R y su ecosistema
El lenguaje R fue utilizado para toda la lógica computacional del algoritmo genético, el procesamiento de datos y la generación de rutas. Se eligió por su potencia en análisis numérico y su facilidad para trabajar con datos geoespaciales.
dplyryreadxl: para manipulación de datos y carga de archivos.osrm: para interactuar con el servicio de rutas y obtener distancias reales calle a calle.sf: para manejar datos espaciales.
RColorBrewer: para generar paletas de colores legibles en las visualizaciones.
OSRM (Open Source Routing Machine)
OSRM es un motor de enrutamiento rápido basado en OpenStreetMap. Fue usado para:
Calcular matrices de distancia realistas entre puntos.
Obtener rutas optimizadas calle a calle para cada segmento del recorrido.
Realizar consultas a través de su API pública directamente desde R y JavaScript.
Esto permitió evitar simplificaciones geométricas y trabajar con condiciones viales reales, esenciales para simular entornos urbanos como el de Bogotá.
Leaflet
Leaflet es una biblioteca liviana y poderosa para mapas interactivos. Se integró directamente en el documento Quarto para:
Visualizar de forma interactiva las rutas calculadas.
Mostrar marcadores con información relevante de cada cliente.
Descripción Del Algoritmo Genético
Representación de la solución
La representación de las soluciones utilizadas para el algoritmo genético fue la de un vector de secuencia donde cada ubicación o cliente esta representada por un número, siendo el depósito o punto de salida en 1 la secuencia entonces se lee de izquierda a derecha. En el caso del ejemplo anterior se comienza en el depósito (1), visita a los clientes (4, 3, 5, 2) en ese orden, y regresa al depósito (1) al final.
Función objetivo (basada en distancia)
En este caso la función objetivo busca minizar las distancias recorridas, cumpliendo con la restricción de demanda de los clientes y respetando la capacidad del vehiculo.
\[min \space z = \sum_{i\in I}\sum_{j\in J} x_{ij}c_{ij}\]
Esta es la versión mas simple de este problema que tiene en cuenta el costo como distancia recorrida, el problema se puede complejizar aun mas si se agregan otros factores como varios vehículos, tanqueo de combustible, etc.
Función de selección.
La selección por torneo busca seleccionar al azar individuos de la población, esto implica realizar torneo de estos individuos para escoger los que serán utilizados para el cruzamiento.
#Función de selección por torneos
selector <- function(){
muestra = sample(1:tampo, m)
EV[muestra]
mejor <- which.min(EV[muestra])
posi <- muestra[mejor]
return(poblacion[posi,])
}En este caso de los individuos seleccionados para el torneo se escoge el que minimice las distancias, es decir al mejor individuo.
Cruzamiento
Para el cruzamiento se establece unos puntos de cortes en cruce uno de los padres y intercambian estos genes en la decendencia para generar un individuo nuevo con un valor de solución diferente, este individuo se ingresa en la población en caso de que sea mejor que la peor solución de esa generación
#Función de cruzamiento
cruzamiento=function(pa,ma){
corte1 <- sample(1:(n-1),1)
excluir <- c(corte1-1,corte1,corte1+1)
conj <- setdiff(1:(n-1),excluir)
corte2 <- sample(conj,1)
pc <- c(corte1,corte2)
extr_iz1 <- pa[1:min(pc)]
extr_dere1 <- pa[-(1:max(pc))]
vector_temp1 <- c(extr_iz1,extr_dere1)
cont <- 0
for(i in 1:n){
cont[i] <- sum(ma[i]==vector_temp1)
pos1 <- which(cont==0)
extr_cent1 <- c(ma[pos1])
}
hijo1 <- c(extr_iz1,extr_cent1,extr_dere1)
extr_iz2 <- ma[1:min(pc)]
extr_dere2 <- ma[-(1:max(pc))]
vector_temp2 <- c(extr_iz2,extr_dere2)
cont <- 0
for(i in 1:n){
cont[i] <- sum(pa[i]==vector_temp2)
pos2 <- which(cont==0)
extr_cent2 <- c(pa[pos2])
}
hijo2 <- c(extr_iz2,extr_cent2,extr_dere2)
if(runif(1)<0.5){
hijo_select <- hijo1
}else{
hijo_select <- hijo2
}
return(hijo_select)
}este proceso genera dos hijos de los cuales al azar se selecciona uno para evaluar si agregarlo a la población.
Mutación
Esta función se aplica para conseguir diversidad genética en la población esto se realiza con una tasa de probabilidad baja para evitar una búsqueda aleatoria de las soluciones
#Función de mutación
mutacion <- function(hijo){
cambio <- sample(1:n,2,replace = F)
provi <- hijo[cambio[1]]
hijo[cambio[1]] <- hijo[cambio[2]]
hijo[cambio[2]] <- provi
return(hijo)
}Evolución de soluciones
Para ejemplificar este problema se usaron 30 puntos de coordenadas de clientes ficticios generados al azar en la ciudad de Médellin, Colombia, ademas de un punto aleatorio de almacen o bodega, se establecio un tamaño de población de 20 individuos, una capacidad ficticia de 100 unidades al vehiculo, unas demandas ficticias tambien, se seleccionan 4 indivuos para la selección por torneo, se prueban con 100 generaciones, una tasa de cruzamiento de 0.8 y una de mutación de 0.2.
En la gráfica se logra observar como con el paso de las generaciones el valor objetivo de las soluciones va disminuyendo, iniciando en soluciones de aproximadamente 30 km de recorrido y reduciendose a 22km aproximadamente en las ultimas generaciones, lo cual muestra una eficacia para generar buenas rutas sin necesidad de realizar una búsqueda exhaustiva de soluciones.
Visualización de los resultados
El siguiente mapa muestra las rutas generadas diferenciadas por colores, estas rutas están establecidas en calles reales de la ciudad, tomadas de OpenStreet. Este mapa es interactivo por lo que pulsando sobre las rutas se pueden ver de cuál es el punto de salida y cuál es el punto de llegada así mismo como los id de los lugares colocando el cursor sobre los puntos.
Estas rutas se pueden ver de mejor manera en la siguiente tabla.
| Ruta | Secuencia | Paradas |
|---|---|---|
| 1 | 4 → 14 → 9 → 3 → 1 | 4 |
| 2 | 7 → 20 → 2 → 26 → 29 → 30 → 1 | 6 |
| 3 | 19 → 18 → 16 → 12 → 8 → 31 → 1 | 6 |
| 4 | 21 → 28 → 15 → 23 → 17 → 1 | 5 |
| 5 | 22 → 6 → 10 → 27 → 13 → 11 → 1 | 6 |
| 6 | 24 → 25 → 5 → 1 | 3 |
Posibles extensiones.
Implementar librerías que visualizan las distancias por calles con datos reales para aproximar la solución de este tipo de problemas puede ser útil para compañías con trabajos logísticos o de distribución; estas enfrentan este tipo de desafíos a diario, por lo cual una herramienta que en cuestión de segundos genere rutas que minimicen las distancias es algo que impacta positivamente en la productividad de las tareas. Sin embargo, aún quedan muchos elementos por analizar que ya se deben llevar a cabo según las necesidades específicas de cada compañía y los respectivos retos y desafíos que enfrente. También existen muchas posibles expansiones de estas implementaciones; podría ser incluir variantes del problema de VRP, por ejemplo, con ventanas de tiempo, múltiples vehículos, varios depósitos o incluso incluir elementos como el tráfico según la hora del día. También incorporar consumo de combustible o emisiones; esta área cuenta con mucho espacio para investigar y desarrollar herramientas útiles para la industria.