Una empresa llamada TechRepair que ofrece servicios de mantenimiento y reparación de electrodomésticos y sistemas eléctricos a domicilio en una ciudad, tiene varios técnicos de mantenimiento, cada uno especializado en ciertos tipos de equipos, y utiliza vehículos que los trasladan junto con el equipo necesario para realizar las reparaciones.
La empresa ofrece ventanas de tiempo específicas para que sus clientes puedan agendar sus citas, ya que muchos clientes solo están disponibles en determinados momentos del día. Para TechRepair, es crucial cumplir con los horarios para evitar afectar la disponibilidad del cliente y mejorar la satisfacción del servicio.
El problema central de TechRepair es encontrar una ruta óptima que permita a cada vehículo y técnico:
Minimizar la distancia total recorrida para reducir los costos de transporte y tiempo en carretera.
Cumplir con las ventanas de tiempo establecidas por cada cliente, lo que significa que cada técnico debe llegar en el horario acordado para realizar el mantenimiento.
| Cliente | Ventana de tiempo de servicio (horas) | Tipo de servicio | Tiempo estimado (min) |
|---|---|---|---|
| 1 | 9:00 - 10:00 | Reparación de lavadora | 30 |
| 2 | 9:30 - 11:00 | Mantenimiento eléctrico | 45 |
| 3 | 10:00 - 11:30 | Reparación de aire | 60 |
| 4 | 11:00 - 12:30 | Instalación del horno | 45 |
| 5 | 12:00 - 13:30 | Mantenimiento eléctrico | 30 |
| 6 | 13:00 - 14:30 | Reparación de lavadora | 40 |
| 7 | 14:00 - 15:30 | Reparación de aire | 60 |
| 8 | 15:00 - 16:30 | Mantenimiento eléctrico | 30 |
| 9 | 16:00 - 17:30 | Reparación de aire | 45 |
| 10 | 17:00 - 18:00 | Instalación del horno | 40 |
set.seed(123)library(GA)Aquí se carga la librería GA, que proporciona
herramientas para resolver problemas de optimización usando algoritmos
genéticos.
clientes <- data.frame(
id = 0:10,
inicio_ventana = c(8.0, 9.0, 9.5, 10.0, 11.0, 12.0, 13.0,
14.0, 15.0, 16.0, 17.0),
fin_ventana = c(18.0, 10.0, 11.0, 11.5, 12.5, 13.5, 14.5,
15.5, 16.5, 17.5, 18.0),
tipo_servicio = c("Depósito", "Reparación de lavadora",
"Mantenimiento eléctrico", "Reparación de aire",
"Instalación de horno", "Mantenimiento eléctrico",
"Reparación de lavadora", "Reparación de aire",
"Mantenimiento eléctrico", "Reparación de aire",
"Instalación de horno"),
tiempo_servicio = c(0, 30, 45, 60, 45, 30, 40, 60, 30, 45, 40)
)Se crea un data.frame llamado clientes para almacenar
información sobre los puntos de visita, que incluye:
id: ID del cliente (incluyendo el depósito, con ID
0).
inicio_ventana: La hora en que el cliente está
disponible para el servicio (en horas).
fin_ventana: La hora en que el cliente ya no está
disponible (en horas).
tipo_servicio: El tipo de servicio solicitado por
cada cliente.
tiempo_servicio: El tiempo estimado en minutos para
completar el servicio en cada lugar.
tiempo_viaje <- matrix(
c(0, 15, 25, 35, 45, 55, 65, 75, 85, 95, 105,
15, 0, 10, 20, 30, 40, 50, 60, 70, 80, 90,
25, 10, 0, 15, 25, 35, 45, 55, 65, 75, 85,
35, 20, 15, 0, 20, 30, 40, 50, 60, 70, 80,
45, 30, 25, 20, 0, 25, 35, 45, 55, 65, 75,
55, 40, 35, 30, 25, 0, 20, 30, 40, 50, 60,
65, 50, 45, 40, 35, 20, 0, 25, 35, 45, 55,
75, 60, 55, 50, 45, 30, 25, 0, 20, 30, 40,
85, 70, 65, 60, 55, 40, 35, 20, 0, 25, 35,
95, 80, 75, 70, 65, 50, 45, 30, 25, 0, 20,
105, 90, 85, 80, 75, 60, 55, 40, 35, 20, 0),
nrow = 11, byrow = TRUE
)Se define una matriz tiempo_viaje que contiene los
tiempos de viaje en minutos entre cada par de puntos. Cada fila y
columna representan un cliente o el depósito, y los valores en la matriz
indican el tiempo necesario para desplazarse entre ellos.
evaluar_ruta <- function(ruta) {
tiempo_total <- 0
tiempo_actual <- 480
penalizacion <- 1000
for (i in 1:(length(ruta) - 1)) {
cliente <- ruta[i]
siguiente_cliente <- ruta[i + 1]
tiempo_actual <- tiempo_actual + tiempo_viaje[cliente + 1, siguiente_cliente + 1]
tiempo_inicio_servicio <- clientes$inicio_ventana[siguiente_cliente + 1] * 60
tiempo_fin_servicio <- clientes$fin_ventana[siguiente_cliente + 1] * 60
tiempo_servicio <- clientes$tiempo_servicio[siguiente_cliente + 1]
if (tiempo_actual < tiempo_inicio_servicio) {
tiempo_total <- tiempo_total + (tiempo_inicio_servicio - tiempo_actual)
tiempo_actual <- tiempo_inicio_servicio
} else if (tiempo_actual > tiempo_fin_servicio) {
tiempo_total <- tiempo_total + penalizacion
}
tiempo_actual <- tiempo_actual + tiempo_servicio
tiempo_total <- tiempo_total + tiempo_viaje[cliente + 1, siguiente_cliente + 1] + tiempo_servicio
}
return(tiempo_total)
}La función evaluar_ruta calcula el costo total (en
minutos) de una ruta específica considerando los tiempos de viaje y los
tiempos de servicio. Además, aplica penalizaciones si el técnico llega
fuera de las ventanas de tiempo permitidas.
Pasos dentro de evaluar_ruta:
tiempo_total: Inicializamos el tiempo total de la
ruta en 0.
tiempo_actual: Empieza en 480 minutos (8:00
a.m.).
penalizacion: Valor de penalización por incumplir
ventanas de tiempo.
Recorrido de clientes en la ruta:
Se calcula el tiempo de viaje desde el cliente actual hasta el
siguiente
(tiempo_actual + tiempo_viaje[cliente + 1, siguiente_cliente + 1]).
Se verifica si el técnico llega dentro de la ventana de tiempo del cliente; si no, se acumula una penalización.
Se añade el tiempo_servicio y el tiempo de viaje al
tiempo_total.
Al finalizar, la función retorna el tiempo_total de
la ruta.
ga_result <- ga(
type = "permutation",
fitness = function(ruta) -evaluar_ruta(c(0, ruta, 0)),
lower = 1, upper = 10,
popSize = 50,
maxiter = 100,
pmutation = 0.2
)La función ga ejecuta el algoritmo genético para
encontrar la ruta óptima:
type = "permutation": Se indica que es un problema
de permutación (debe recorrer clientes en un orden específico).
fitness = function(ruta) -evaluar_ruta(c(0, ruta, 0)):
Se define la función de aptitud, invocando evaluar_ruta en
una ruta que comienza y termina en el depósito (cliente 0). Se usa
-evaluar_ruta(...) porque el GA busca maximizar la aptitud,
y queremos minimizar el tiempo_total.
lower y upper: Definen los límites de
los clientes (1 a 10).
popSize = 50: Define el tamaño de la población del
GA (50 rutas).
maxiter = 100: Número máximo de iteraciones para la
optimización.
pmutation = 0.2: Tasa de mutación, que permite
cierta variabilidad para explorar soluciones.
mejor_ruta <- c(0, ga_result@solution, 0)
tiempo_total <- -ga_result@fitnessValue
cat("Mejor ruta encontrada:", mejor_ruta, "\n")## Mejor ruta encontrada: 0 2 3 4 5 8 9 10 7 6 1 0cat("Tiempo total de la ruta:", tiempo_total, "minutos\n")## Tiempo total de la ruta: 4845 minutosUna vez completado el GA, el código, se extrae la mejor solución
(ga_result@solution), agregando el depósito al inicio y
final de la ruta. Muestra el tiempo total de la ruta en minutos,
invirtiendo el signo (-ga_result@fitnessValue) para obtener el
valor positivo del tiempo mínimo.