Cómo acomodamos 300 paquetes en 4 camiones en 1.3 segundos

Una corrida completa sobre 300 entregas sintéticas distribuidas en la red vial real de Querétaro. Estos son los números, incluidos los que no favorecen al algoritmo.

La instancia

300 entregas ubicadas sobre nodos reales de la red vial de Querétaro extraída de OpenStreetMap, con dimensiones y pesos por paquete que van de cajas de 20 × 15 × 10 cm y 400 gramos hasta bultos de 80 × 50 × 40 cm y casi 19 kilogramos. Flota de vans tipo Ford Transit con caja de 365 × 139.2 × 164.8 cm y 1,900 kg de carga máxima. Restricciones activas: soporte mínimo, fragilidad y descarga LIFO.

Los resultados

Por ruta: 98, 73, 49 y 80 paquetes, con recorridos de 138.4, 198.9, 98.6 y 83.6 km. La asimetría no es un error: la ruta de 98 entregas cubre la zona densa del centro, donde las paradas están a cientos de metros; la de 73 sale a las zonas periféricas, donde cada cliente cuesta kilómetros.

Por qué la ocupación se queda en 60%

Es la pregunta que hace todo el que ve el diagrama de carga por primera vez. La respuesta es geometría, no ineficiencia. Cuando se exige que cada caja tenga al menos 75% de su base apoyada, que nada pesado descanse sobre un bulto frágil y que los paquetes de la parada 12 salgan sin mover los de la 13, el espacio aprovechable real cae muy por debajo del volumen nominal.

El dato práctico: si su sistema de planeación asume que un vehículo de 8.3 m³ acepta 8.3 m³ de mercancía, está construyendo rutas que el andén no podrá cargar. Nosotros ruteamos con una capacidad efectiva calibrada —alrededor del 51% al 59% del volumen nominal según las restricciones activas— y el resultado son planes que se ejecutan sin correcciones de última hora.

El costo de la geometría

Aquí va el número incómodo. Si se resuelve la misma instancia como CVRP clásico, ignorando la tercera dimensión, la distancia total baja a 431.7 km. Es decir: considerar el acomodo real costó 87.8 km adicionales, un 20% más.

Esa diferencia no es una pérdida del algoritmo: es el precio de la factibilidad. Las rutas de 431 km existen en el papel y no se pueden cargar. Cualquier herramienta que presuma distancias muy inferiores probablemente esté resolviendo un problema más fácil que el que usted tiene en el andén.

Qué falló y cómo lo corregimos

La primera versión del sistema dejaba que el motor de ruteo trabajara con el volumen nominal y confiaba en un mediador para reparar después las rutas incargables. Funcionó, pero caro: en la evaluación formal sobre las instancias de Gendreau, la reparación lograba factibilidad a costa de 13.7% de distancia adicional, y en el peor caso 36.6%.

El cambio fue mover la restricción hacia adelante en lugar de reparar hacia atrás: rutear desde el principio con capacidad efectiva calibrada por variante. En las pruebas de humo, el mediador quedó ocioso —cero reparaciones— y en la variante de solo carga la distancia cayó de 429.6 a 329.3 km. La lección es vieja pero se olvida seguido: en optimización combinatoria conviene pagar la restricción en la función de costo, no en un parche posterior.

Reproducibilidad

Los resultados provienen de una corrida registrada del planificador, con matriz de caminos mínimos sobre la red vial, precio de combustible de $24.50/L y rendimientos reales por unidad. El diagrama de acomodo que se muestra en el demo del sitio son las posiciones exactas calculadas para esos 98 paquetes de la ruta 1, no una ilustración.

Para leer después

La formulación del problema base está en qué es el CVRP, y el detalle de las restricciones tridimensionales en 3L-CVRP. Si quiere probar con sus propios datos, la API recibe una matriz de distancias y una lista de paquetes.