Si ha leído el artículo sobre el TSP, ya sabe cómo ordenar entregas para minimizar la distancia. Pero en la práctica, sus clientes no le esperan a cualquier hora. Una boda a las 14h, un almuerzo de empresa a las 12h en punto, una consulta médica cerrada entre 12h30 y 14h. Para eso sirve precisamente el VRPTW, el Vehicle Routing Problem with Time Windows. Toma el relevo cuando el TSP llega a sus límites.
Del TSP al VRPTW: la evolución natural
El TSP minimiza la distancia, punto. Supone que todas las direcciones son accesibles en cualquier momento. Una simplificación útil para entender el problema, pero que no refleja su realidad diaria.
El VRPTW añade dos ingredientes esenciales:
- Varios vehículos potenciales (la V de VRP): puede tener 1, 2, 5 repartidores en paralelo
- Franjas horarias por cliente (el TW de Time Windows): cada dirección tiene una franja
[apertura, cierre]
De repente, lo que era un problema de geometría pura se convierte en un problema temporal. El orden óptimo ya no es solo «el más corto», es «el más corto que respeta todas las franjas».
Un ejemplo concreto
Imaginemos un día típico de catering: 6 entregas, salida del almacén a las 10h00.
| Cliente | Dirección | Franja | Tiempo en sitio |
|---|---|---|---|
| A | Sol | 11h45 a 12h00 | 5 min |
| B | Atocha | 11h00 a 11h30 | 5 min |
| C | Chamartín | 12h00 a 12h15 | 5 min |
| D | Moncloa | 12h30 a 13h00 | 5 min |
| E | Retiro | 11h30 a 12h00 | 5 min |
| F | Chueca | 13h00 a 13h30 | 5 min |
El TSP quizás le diría: «pase por A, B, C, D, E, F en este orden, es lo más corto». Pero si llega a A a las 12h05 cuando había que estar entre 11h45 y 12h00, llega tarde. El cliente no está contento. Pierde el contrato.
El VRPTW encuentra un orden que:
- Visita cada dirección dentro de su franja
- Minimiza la distancia y el tiempo total entre todos los órdenes factibles
- Le avisa por adelantado si algunas franjas son inalcanzables (en cuyo caso necesita otro vehículo o adelantar la salida)
El resultado EDF en este ejemplo
OptiRoad ordena las paradas por hora de cierre creciente y luego simula el día a partir de la salida a las 10h00. El orden obtenido es: B (Atocha), después E (Retiro), A (Sol), C (Chamartín), D (Moncloa) y por último F (Chueca). Este es el planning detallado que aparece en pantalla:
| Parada | Llegada | Inicio de servicio | Salida |
|---|---|---|---|
| B | 10h18 | 11h00 | 11h05 |
| E | 11h25 | 11h30 | 11h35 |
| A | 11h50 | 11h50 | 11h55 |
| C | 12h05 | 12h05 | 12h10 |
| D | 12h30 | 12h30 | 12h35 |
| F | 13h00 | 13h00 | 13h05 |
En B llega muy pronto (10h18): el vehículo espera hasta la apertura a las 11h00 y luego entrega. Cada franja se respeta desde la primera parada hasta la última. Un orden puramente de «distancia más corta» tipo TSP nunca garantizaría este resultado.
Por qué es más difícil que el TSP
El TSP ya es NP-difícil (véase el artículo TSP). El VRPTW lo es aún más, porque hay que simular el flujo temporal de la ruta para validar cada solución candidata:
- En cada parada, se calcula la hora de llegada prevista
- Si llega antes de la apertura, espera (tiempo perdido)
- Si llega después del cierre, la solución no es válida (rechazada)
- El tiempo de servicio se suma a la hora de salida hacia la siguiente
El solver no puede limitarse a optimizar la distancia bruta. Tiene que construir el planning detallado del día para cada orden probado.
¿Franja dura o franja blanda?
En teoría existen dos familias de franjas horarias. Una franja dura debe respetarse: una solución que la incumple se rechaza sin más, como una cita médica o una ceremonia que sencillamente no se mueven. Una franja blanda tolera el retraso, pero a costa de una penalización que el solver intenta minimizar.
OptiRoad trata las franjas como duras para juzgar si una ruta es factible. La diferencia es que, en lugar de romper en silencio una franja para ahorrar unos kilómetros, OptiRoad señala la parada como retrasada antes incluso de salir. Usted decide: avisar al cliente, añadir un vehículo o adelantar la hora de salida. Nota: el indicador strict puesto en una franja es un dato semántico que se muestra en el planning (la gestión más avanzada llegará más adelante).
Los enfoques para resolver el VRPTW
1. Earliest Deadline First (EDF)
En cada paso, se elige el cliente cuya franja se cierra antes entre los aún alcanzables. Simple, rápido, da excelentes resultados en la práctica. Es el enfoque usado por OptiRoad.
2. Insertion heuristics
Se parte de una ruta vacía, se insertan los clientes uno a uno buscando la posición que minimiza el coste total respetando las franjas. Buena calidad, cálculo más largo.
3. Metaheurísticas (recocido simulado, tabú, genético)
Para instancias muy grandes (cientos de paradas, multi-vehículo complejo). Dan soluciones cerca del óptimo pero requieren tiempo de cálculo.
4. Programación por restricciones
Enfoque académico muy potente pero pesado de implementar, reservado para casos específicos.
El tiempo de servicio lo cambia todo
Se olvida a menudo, pero el tiempo que se pasa en cada parada (el tiempo de servicio) retrasa todas las llegadas siguientes. Cinco minutos multiplicados por quince entregas son más de una hora que se desplaza a lo largo de la jornada. Ignorar ese tiempo da un planning que se sostiene sobre el papel pero se retrasa en la vida real.
Por eso OptiRoad resuelve el tiempo de servicio parada por parada, siguiendo una prioridad clara: gana el valor introducido manualmente en la parada, si no el del contacto correspondiente en su agenda de direcciones (emparejado por coordenadas), si no el valor por defecto de su cuenta (5 minutos). Así, cada hora estimada de llegada ya incluye el tiempo realmente pasado en el sitio.
Cómo implementa OptiRoad el VRPTW
Cuando activa «Franjas horarias» en el panel (plan Pro o Business), esto es lo que hace OptiRoad:
- Ordena los clientes por franja de cierre creciente (con prioridad especial para paradas marcadas
priority: high) - Construye la ruta por inserción EDF: en cada paso, toma el siguiente cliente que respeta la franja actual y minimiza el desvío
- Simulación del planning: a partir de la hora de salida, calcula para cada parada:
- hora de llegada prevista (teniendo en cuenta la distancia)
- hora de inicio de servicio (= max(llegada, apertura))
- hora de salida (= inicio + tiempo de servicio)
- Detección de retrasos: si la llegada prevista supera el cierre, la parada se marca
late: trueen la respuesta, está avisado antes de salir - Sin 2-opt cuando VRPTW está activo: el orden EDF prima sobre la optimización de distancia, para no romper las restricciones temporales
El resultado en la app: una tabla resumen clara que muestra la hora de llegada prevista en cada cliente, los retrasos en rojo, y la duración real total del día (incluyendo tiempos de espera).
Cuándo usar VRPTW vs TSP simple
- TSP: ruta de reparto clásica sin restricción horaria fuerte (e-commerce, correo, etc.). Llega cuando llega.
- VRPTW: en cuanto al menos algunos clientes tienen una franja impuesta. Catering, floristerías (ceremonias), asistencia a domicilio (franjas médicas), intervenciones técnicas con cita.
OptiRoad cambia automáticamente a VRPTW en cuanto define al menos una franja en su ruta.
¿Y el multi-vehículo?
El VRPTW puede combinarse con multi-vehículo: varios repartidores en paralelo, cada uno con su propia ruta optimizada. OptiRoad gestiona este caso en el plan Business con el algoritmo Clarke-Wright Savings para repartir las paradas entre vehículos, luego EDF y simulación por vehículo. Será el tema de un próximo artículo.
En la práctica: lo que cambia para usted
En una ruta típica con franjas horarias (entregas de catering, por ejemplo):
- Sin VRPTW: del 30 al 50% de las entregas corren riesgo de estar fuera de franja, llama a los clientes para retrasar, se estresa.
- Con VRPTW: 100% de entregas dentro de las franjas o alerta antes de la salida. El día transcurre como previsto.
Y cuando sabe por adelantado que una entrega llegará tarde, puede actuar. El simple hecho de saberlo por adelantado vale a menudo más que el ahorro de kilómetros.
Para ir más lejos
El VRPTW está disponible en planes Pro y Business. El plan Free incluye el TSP simple (sin franjas), suficiente para validar la calidad del algoritmo. Para activar las franjas, pase a Pro y active el toggle «Franjas horarias» en OptimizePanel.
¿Quiere profundizar en multi-vehículo (VRP con Clarke-Wright Savings)? Es el próximo artículo.
Preguntas frecuentes
¿Qué pasa si una franja no se puede cumplir?
La parada afectada se señala como retrasada antes de la salida, nunca se descubre ya en la carretera. Usted mantiene el control: avisar al cliente, añadir un vehículo para repartir la carga, o adelantar la hora de salida para que la franja vuelva a ser alcanzable.
¿Puedo mezclar paradas con y sin franja?
Sí. Las paradas sin franja no están sujetas a ninguna hora concreta: OptiRoad las coloca libremente alrededor de las que sí tienen restricción, allí donde encajan mejor sin perturbar las franjas impuestas. Así que no tiene que definir una franja para cada entrega.
¿El VRPTW gestiona varios vehículos?
Sí, en el plan Business. OptiRoad reparte primero las paradas entre los vehículos con el algoritmo Clarke-Wright Savings, y luego aplica el EDF y la simulación de planning a cada ruta por separado. Cada repartidor obtiene así su propio itinerario optimizado y respetuoso con las franjas.
¿Qué plan incluye las franjas horarias?
Las franjas horarias están disponibles en los planes Pro y Business. El plan Free se limita al TSP simple, sin restricción temporal: perfecto para probar la calidad de la optimización en rutas pequeñas, pero no adaptado a los oficios con franjas impuestas.