Asignación de envíos de varias plantas o almacenes a varios clientes o puntos de distribución — cuánto en cada ruta para que el coste total de flete sea mínimo, no se superen las capacidades y se cubran las demandas. El problema fundacional de la programación lineal: Hitchcock (1941) y Koopmans (1947).
En pocas palabras
¿Te suena?
- Enviamos semanalmente desde 3-8 plantas o almacenes regionales a 20-100 clientes; qué planta envía a qué cliente se decide normalmente por hábito o la regla 'planta más cercana'.
- Operamos una cooperativa de recogida de leche; flujo diario desde 50-200 granjas productoras a 3-6 plantas de procesado — qué granja va a qué planta viene de la historia.
- Tenemos una cadena textil materia-prima-taller; enviamos hilo y tela desde un almacén central a 30-80 talleres de manufactura — la matriz de costes lleva 5 años sin actualizar.
- Cuando se abre una planta o almacén nuevo, o entra un cliente nuevo, no recalculamos los porcentajes — seguimos con la asignación antigua.
- El precio del combustible o los contratos de flete han cambiado, pero los volúmenes planta-cliente siguen igual.
- El coste total de flete está en 10-20 % del presupuesto anual; la pregunta 'qué ahorraríamos si rediseñamos los flujos' lleva años sin responder.
- Estamos considerando una ampliación de capacidad de planta; la pregunta 'qué supone 1 tonelada extra en ahorro de flete total' no tiene respuesta numérica.
Por qué importa
Cómo se resuelve
Profundidad técnica
Cómo se resuelve
Profundidad técnicaEn una frase: Dada la matriz de coste unitario para pares planta-cliente, las capacidades de planta y la demanda del cliente, un solver de programación lineal calcula en segundos cuánto (x_ij) enviar de cada planta a cada cliente — coste total de flete mínimo, ningún cliente desabastecido, ninguna planta excedida.
Este problema aparece en la literatura de Investigación de Operaciones (disciplina que usa matemáticas e informática para resolver decisiones de negocio) como Problema de Transporte o Problema de Hitchcock, uno de los ejemplos fundacionales de la programación lineal. La solución en tres fases:
1. Modelado. Datos de entrada: orígenes (m plantas o almacenes — cada uno con capacidad semanal s_i en toneladas o palets), destinos (n clientes o puntos de distribución — cada uno con demanda semanal d_j), matriz de costes (c_ij — coste unitario de transporte de planta i a cliente j, TRY por tonelada o palet). Variable de decisión x_ij — cantidad a enviar de planta i a cliente j. Restricciones: envíos totales de cada planta ≤ capacidad (suma sobre j de x_ij ≤ s_i), recepción de cada cliente ≥ demanda (suma sobre i de x_ij ≥ d_j), todas las x_ij ≥ 0. Objetivo: minimizar el coste total de flete. Problema equilibrado: oferta total igual a demanda total; problema desequilibrado: oferta > demanda (capacidad ociosa) o oferta < demanda (subproducción), resuelto añadiendo un origen o destino ficticio (dummy).
2. Decisión asistida por solver. Al ser un LP puro (Linear Programming — minimizar un objetivo lineal bajo restricciones lineales), los solvers LP modernos resuelven miles de pares origen-destino en segundos. Métodos clásicos: Método Símplex (desarrollado a principios de los años 1950 para este problema — el algoritmo LP canónico que encuentra el óptimo recorriendo vértice a vértice); Símplex de Red (la estructura de grafo bipartito lo hace 5-10× más rápido); Regla de la esquina noroeste para solución inicial básica factible, combinada con MODI (Distribución Modificada) / Stepping-Stone para mejora (método manual didáctico); Método de Aproximación de Vogel (VAM) para un mejor punto de partida. En la práctica: media escala (5-50 orígenes × 50-500 destinos) instantánea en solvers LP abiertos, gran escala (cientos-miles) en minutos con símplex de red o métodos de punto interior. El Problema de Asignación es caso especial — orígenes y destinos en igual número, cada origen a un destino (capacidad = demanda = 1, x_ij en {0,1}); el método húngaro es el solver clásico para este caso.
3. Integración de campo. Salida en dos tablas: la matriz de flujos primal (cantidad semanal de envío por par planta-cliente — el plan principal del equipo operativo), y las variables duales (precios sombra para cada origen y destino). Los valores duales son input directo de decisión de inversión: ‘si la capacidad de la planta i aumenta 1 tonelada, ¿cuánto baja el coste total de flete?’ se lee directamente del dual. Práctica de campo: re-resolución semanal o mensual; cambios de precio de combustible, alta de cliente/planta, ventanas de mantenimiento como disparadores. Comité trimestral: flujos reales vs plan, análisis de capacidad marginal, refresco de matriz de costes.
Alternativas
Manual + hoja de cálculo (flujos heredados)
GratisSin licencia
Para quién: Pequeña escala (≤3 plantas, ≤20 clientes), demanda estable
- + Coste cero de software
- + Encaja con la rutina del equipo operativo
- + Cambio inmediato (redirección por teléfono)
- − Flujos no óptimos — típico 10-20 % de sobreflete
- − Sin matriz de costes refrescada los shocks de combustible no entran
- − Capacidad marginal (para inversión) no analizable
- − Al alta de planta/cliente no se rediseña
Hoja de cálculo con complemento LP
GratisCero o licencia baja (en suite ofimática)
Para quién: Media escala (3-8 plantas, 20-100 clientes), decisión mensual periódica
- + Interfaz manejable por el equipo operativo
- + Escala suficiente para el problema clásico
- + Curva de aprendizaje baja
- − Lento o insoluble en matrices grandes (200+ destinos)
- − Visualización de duales débil — sin informe de precio sombra
- − Sin módulo de demanda estocástica
- − Control de versiones débil
Software local de planificación de cadena de suministro
EmpresarialLicencia 200K-1M TRY + 60K-300K TRY/año mantenimiento (precios SMB regionales)
Para quién: Operador medio-grande (5-15 plantas, 100-500 clientes)
- + Interfaz y soporte en idioma local
- + Integración ERP sencilla
- + Plantillas locales de contratos de flete
- − Solver LP suele venir empaquetado — el rendimiento debe probarse
- − Análisis dual limitado
- − Extensiones académicas (multi-periodo, estocástico) limitadas
Plataforma internacional de planificación
EmpresarialLicencia 500K-3M EUR + 150K-700K EUR/año mantenimiento
Para quién: Operador grande (15+ plantas, 500+ clientes, multi-país)
- + Solver LP/MIP maduro, escalable
- + Análisis dual rico, precios sombra, comparación de escenarios
- + Extensiones multi-periodo y estocásticas
- − Licencia alta y despliegue largo (12-24 meses)
- − Personalización a regulación local alarga el proyecto
- − Formación del equipo es un programa amplio
Desarrollo propio sobre solver LP de código abierto
Código abiertoLicencia gratis; 8-16 semanas de desarrollo interno o 400K-1,2M TRY de consultoría
Para quién: Operador con equipo técnico, busca complemento ERP
- + Sin coste de licencia
- + Problema clásico de transporte bien definido en literatura abierta
- + Extensiones multi-periodo, estocásticas, flujo en red abiertas
- − Requiere experiencia IO interna y equipo de datos
- − Hay que construir la interfaz de operación
- − Mantenimiento a cargo del operador
Recomendación
Pregunta en la reunión
- ¿Qué solver impulsa el problema de transporte — símplex puro, símplex de red, punto interior? ¿Tiempo típico para 100 orígenes × 500 destinos?
- ¿Se soporta equilibrado automático (origen/destino ficticio) para problemas desequilibrados? ¿Se genera el informe de capacidad ociosa?
- ¿Se presentan las variables duales (precios sombra) como tabla aparte? ¿Se puede autogenerar el escenario 'capacidad de planta i sube 1 tonelada'?
- Cuando se actualiza la matriz de costes (cambio de combustible, nuevo contrato), ¿el disparador de re-resolución es automático o manual?
- ¿Se soporta planificación multi-periodo (horizonte semanal o mensual)? ¿Hay arrastre de inventario entre periodos?
- ¿Existe módulo dedicado para el caso especial Problema de Asignación (orígenes = destinos, decisión binaria)? ¿Método húngaro soportado?
- ¿Cómo produciría el piloto, en 8-12 semanas de datos reales, un informe de ahorro frente al flujo manual anterior?
- Si terminamos el contrato, ¿en qué formato estándar podemos exportar definiciones origen-destino, historial de matriz de costes y archivo de soluciones?
Detalles técnicos
Nota editorial
En el día a día operativo este problema se llama “plan de flujo”, “reparto de envíos” o “matriz planta-cliente”. El nombre académico es Problema de Transporte, también escrito en algunas fuentes como Problema de Hitchcock o Problema de Hitchcock-Koopmans. Frank Hitchcock definió el problema en forma numérica en su artículo del MIT de 1941; Tjalling Koopmans escribió en 1947 una formulación económica independiente (citada en su Premio Nobel de Economía 1975); George Dantzig desarrolló en 1951 el método Símplex específicamente a partir de este problema. Es el problema fundacional de la programación lineal y el ancestro de la siguiente generación — TSP, VRP, ruteo de vehículos — que construyó sobre él.
La distinción con VRP (#002, #069) es clave: VRP es ruteo de vehículos — una ronda depósito-cliente-cliente-depósito, en qué orden cada vehículo visita qué clientes. El problema de transporte es asignación de flujos: cuántas unidades envía cada planta a cada cliente; no hay ruta, solo cantidad. Los dos son complementarios — primero el problema de transporte decide el flujo semanal, luego VRP decide el ruteo diario. Funcionan en secuencia en la misma cadena. Distinción de la localización (#010): la localización es la decisión de abrir nueva planta/almacén (con coste fijo de apertura); el problema de transporte es asignación de flujo entre instalaciones existentes (sin coste de apertura). Distinción de p-mediana (#074): p-mediana selecciona un número fijo de instalaciones, el problema de transporte toma las existentes como dadas.
El punto más a menudo pasado por alto: variables duales y precios sombra. Los flujos primal (cuántas toneladas de cada planta a cada cliente) es la salida que el profesional lee; las variables duales asignan un precio sombra a cada origen y destino — “si la capacidad de la planta i sube 1 tonelada, ¿cuánto baja el coste total de flete?”, “si la demanda del cliente j sube 1 tonelada, ¿cuánto sube el coste total?” se responden exactamente. Input directo para decisiones de inversión: qué planta gana más con ampliación, qué cliente tiene coste marginal de flete mayor. El profesional suele usar solo el primal y no lee los duales — pérdida crítica para priorización de inversión en capacidad. Segundo punto pasado por alto: el problema desequilibrado. En la realidad rara vez la capacidad total es exactamente la demanda total (sobre o subproducción). El solver añade un origen o destino ficticio — esa fila/columna es el informe de capacidad ociosa; si se pasa por alto, no se entiende a qué corresponde la capacidad ociosa.
Camino paso a paso para una PYME
Fase 1 — Medir primero, planear después. Al menos 6-12 meses de datos: cantidad mensual enviada por par planta-cliente, coste unitario de flete (distancia + tipo de vehículo + contrato), capacidad semanal de planta, demanda semanal de cliente. Construir la matriz de costes como tabla separada — filas plantas, columnas clientes, celdas TRY/tonelada. Crítico: ¿el precio del combustible ha cambiado en los últimos 12 meses — se ha refrescado la matriz de costes? Si no, ya la primera ejecución LP muestra 5-10 % de ahorro.
Fase 2 — Extraer el capital de conocimiento. Listar qué plantas son físicamente imposibles para qué clientes (distancia, ajuste de producto, restricción contractual) — esas restricciones entran al modelo como ‘celdas prohibidas’ (coste alto). Capacidad de planta: ¿capacidad sostenida real o con ventanas de mantenimiento? Demanda de cliente: ¿estable o estacional?
Fase 3 — Piloto. 8-12 semanas. Construir modelo LP para una sub-región (por ejemplo una línea de producto o un conjunto regional de clientes), ejecutar el solver y comparar el resultado en paralelo con la asignación manual actual. La decisión queda con el planificador; el LP da sugerencia. Criterio de éxito por escrito antes del piloto: coste total de flete bajar al menos 10 %, informe de capacidad ociosa o demanda no cubierta claro. Pedir la tabla de variables duales como salida separada — oro para inversión en capacidad.
Fase 4 — Despliegue. En 6-12 meses ampliar a todas las líneas y regiones. Pasar a re-resolución mensual — combustible, nuevo cliente, mantenimiento como disparador. Comité trimestral: flujos reales vs plan, informe de duales (precio sombra), fecha de refresco de matriz de costes.
Riesgos — qué puede salir mal
- La capacidad de planta varía en tiempo real. El modelo LP estático fija la capacidad semanal o mensual; mantenimiento, pérdida de turno o cortes de materia prima la mueven a diario. Solución: cadencia de re-resolución más corta (semanal) y margen de seguridad por debajo de la capacidad media.
- La matriz de costes no se refresca. El combustible subió 20 % pero la matriz lleva 2 años con los números antiguos — el LP optimiza una matriz obsoleta y pierde dinero en la práctica. Solución: refrescar cada 3 meses (combustible + contrato + coste de vehículo).
- Las particularidades del cliente no están modeladas. Algunos clientes tienen ventana horaria, restricción de tamaño de paquete o regla de mezcla de producto — el problema de transporte puro no lleva eso; debe pasarse al VRP o capa de planificación. Un flujo correcto LP puede ser inviable operativamente.
- Dependencia de un único proveedor (lock-in WMS/TMS). Si el software guarda definiciones origen-destino, matriz de costes e historial de soluciones en formato propietario, salir significa perder la memoria de flujos del operador. Cláusula contractual: ’exportación anual del historial de la matriz de flujos y matriz de costes en formato estándar’."
Visión técnica del método de solución
| Enfoque | Escala típica | Tiempo de solución | ¿Garantiza óptimo? |
|---|---|---|---|
| Regla de la esquina noroeste | Solución inicial manual, cualquier escala | minutos (manual) | No — solo solución inicial |
| Método de Aproximación de Vogel (VAM) | Inicio más inteligente | minutos-segundos | No — casi óptimo |
| MODI / Stepping-Stone (manual) | Pequeño (≤10 × ≤10) | horas | Sí (aplicado correctamente) |
| Símplex (general) | Medio (≤500 × ≤500) | segundos | Sí |
| Símplex de Red | Grande (miles de orígenes/destinos) | segundos-minutos | Sí |
| Método de punto interior | Muy grande | minutos | Sí (tolerancia numérica) |
| Método húngaro (asignación) | Matriz cuadrada | rápido | Sí (caso especial) |
Elección de función objetivo:
- Objetivo 1 — Coste total de flete mínimo: Clásico. FMCG, cadenas materia-prima-taller.
- Objetivo 2 — Distancia o combustible mínimo: Operaciones con foco CO₂ o intensivas en combustible.
- Objetivo 3 — Tiempo de servicio ponderado mínimo: Distribución rápida (alimentación, cadena de frío).
- Objetivo 4 — Mezcla ponderada: flete + servicio + penalización: Cartera con penalizaciones contractuales por retraso.
El Problema de Asignación es caso especial del de transporte: número de orígenes = destinos, cada origen a exactamente un destino (capacidad = demanda = 1, x_ij binaria). Asignación personal-tarea, máquina-orden, buque-muelle (sub-capa del BAP en #026), problemas de emparejamiento de nodos tienen esta forma. El método húngaro (Kuhn 1955) resuelve la asignación en O(n³) — mucho más rápido que el símplex general sobre los mismos datos, pero solo para el caso especial de asignación.
Extensión multi-periodo: x_ijt — cantidad de planta i a cliente j en periodo t; capacidad y demanda propias por periodo, con coste de inventario entre periodos. Crece a planificación producción-distribución multi-periodo — mantiene el problema de transporte como núcleo, añade capas de lot-sizing e inventario.
Extensión estocástica: d_j es variable aleatoria; la solución da asignación que no excede capacidad en ningún escenario y minimiza el coste esperado — LP estocástico o MIP basado en escenarios.
Referencias académicas
Listadas en el bloque sources de esta página. Hitchcock (1941) y Koopmans (1947) son los dos artículos fundacionales; Dantzig (1951) desarrolló el método Símplex a través de este problema. Bazaraa-Jarvis-Sherali (2010) y Murty (1992) son referencias de libro de texto modernas. INFORMS y el archivo del European Journal of Operational Research recogen muchos casos de aplicación en cadenas de suministro y redes producción-distribución.
Fuentes
- Hitchcock, F. L. (1941). The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics, 20(1-4), 224-230. Fuente fundacional del problema.
- Koopmans, T. C. (1947). Optimum utilization of the transportation system. Econometrica, 17 (Supplement). Entre las citas del Premio Nobel de Economía 1975.
- Dantzig, G. B. (1951). Application of the Simplex Method to a transportation problem. In Activity Analysis of Production and Allocation, Wiley.
- Bazaraa, M. S., Jarvis, J. J. y Sherali, H. D. (2010). Linear Programming and Network Flows (4ª ed.). Wiley. Libro de texto estándar.
- Murty, K. G. (1992). Network Programming. Prentice Hall. Referencia clásica.
- INFORMS Interfaces — casos de aplicación de LP y cadena de suministro en redes producción-distribución. informs.org/Publications/Interfaces
Glosario
- Problema de Transporte
- Asignación de envíos desde m orígenes con capacidad fija a n destinos con demanda fija, minimizando el coste unitario total de transporte — el problema fundacional de la programación lineal.
- Regla de la Esquina Noroeste
- La heurística clásica más sencilla para generar una solución básica factible inicial del problema de transporte: empezar en la esquina superior izquierda de la matriz de costes, asignar lo máximo posible a la celda actual y desplazarse a la derecha o hacia abajo hasta agotar oferta y demanda.
- MIP
- Modelo de optimización donde parte de las variables de decisión deben ser números enteros (p. ej. número de camiones o de turnos).
Problemas relacionados
¿Dónde Abro el Nuevo Almacén?
Un distribuidor, un operador de comercio electrónico o un fabricante pyme prevé abrir 1–5 nuevos almacenes, sucursales o centros de distribución en los próximos 2–5 años. La decisión: en qué ciudad o región, cuántas instalaciones, de qué tamaño y qué almacenes existentes transfieren qué volumen de pedido o cliente a la nueva instalación. Una mala localización implica 5–10 años de alto coste de transporte, entregas tardías y pérdida de clientes; una buena localización supone 300.000–1,5 M EUR de ahorro anual en el mismo periodo. Cuando la decisión se toma por intuición (por ejemplo 'al lado de la fábrica, los empleados viven cerca') rara vez se acierta — porque coste de transporte, alquiler, impuestos, mano de obra y tiempo de servicio son restricciones que deben equilibrarse a la vez.
¿Qué cabe en un camión o contenedor, y en qué orden se carga?
Dado un camión, contenedor o vehículo de carga de dimensiones fijas, ¿qué disposición de cajas (o pallets) con tamaños, pesos y reglas de apilado distintos da la mayor tasa de utilización? El nombre matemático de esta pregunta es Three-Dimensional Bin Packing Problem (3D-BPP) o Container Loading Problem (CLP). Métodos que resuelven al mismo tiempo volumen, límites de peso, reglas de apilado, distribución del peso (balance) y orden de entrega (multi-drop) se estudian desde los 1990. Incluso un 5% de mejora en utilización aumenta entregas por vehículo de forma material para una pyme.
¿Qué Furgoneta a Qué Cliente, a Qué Hora?
Una flota local de reparto de 5–30 furgonetas planifica sus rutas diarias. Cada cliente tiene una ventana horaria (una tienda recibe entre 09:00 y 12:00; un restaurante solo antes de las 14:00). La decisión: a qué furgoneta asignar cada cliente, en qué orden visitarlos, de modo que todas las ventanas se cumplan, las horas de combustible y conductor sean mínimas, y ninguna furgoneta supere su capacidad. Un repartidor puede planificar a mano 30–50 paradas; por encima, la calidad cae — kilómetros vacíos, entregas tardías, segundas rutas y horas extra del conductor.