Métodos cuantitativos aplicados a la logística

Los métodos cuantitativos constituyen herramientas fundamentales para optimizar operaciones en el sector del transporte y la logística. Estas técnicas matemáticas y algorítmicas permiten tomar decisiones basadas en datos, reducir costes operativos y mejorar la eficiencia de las cadenas de suministro.

En un entorno empresarial cada vez más competitivo, las empresas de transporte necesitan maximizar recursos. Minimizar tiempos de entrega. Optimizar rutas. Los métodos cuantitativos ofrecen soluciones precisas a estos desafíos mediante modelos matemáticos que simulan situaciones reales y predicen resultados.

Modelos: conceptos y tipologías

Concepto de modelo

Un modelo es una representación simplificada de un sistema real que permite analizar su comportamiento y predecir resultados. En logística, los modelos ayudan a comprender relaciones complejas entre variables como demanda, capacidad, costes y tiempo.

Ejemplo práctico: Una empresa de mensajería utiliza un modelo para determinar el número óptimo de vehículos necesarios durante diferentes períodos del día, considerando la demanda variable y los costes de mantenimiento de flota.

Tipologías de modelos

  • Modelos deterministas: las variables toman valores conocidos y fijos. Una empresa de transporte de mercancías peligrosas utiliza estos modelos para calcular rutas exactas con restricciones específicas de velocidad y paradas obligatorias.
  • Modelos estocásticos: incorporan incertidumbre mediante variables aleatorias. Los centros de distribución emplean estos modelos para gestionar inventarios cuando la demanda fluctúa impredeciblemente.
  • Modelos estáticos: analizan situaciones en un momento específico. Útiles para determinar la ubicación óptima de almacenes en una red logística.
  • Modelos dinámicos: consideran cambios temporales. Fundamentales para planificar rutas de transporte público que deben adaptarse a patrones de demanda horarios.

Sistemas: concepto, principios y aplicaciones

Concepto de sistema

Un sistema logístico es un conjunto interrelacionado de elementos que trabajan coordinadamente para cumplir objetivos específicos. Incluye recursos humanos, tecnológicos, infraestructuras y procesos que facilitan el flujo de mercancías desde origen hasta destino.

Principios fundamentales

  • Holismo: el rendimiento del sistema completo supera la suma de sus partes individuales. En una cadena de suministro, la coordinación entre proveedores, almacenes y transportistas genera eficiencias superiores a la optimización aislada de cada elemento.
  • Sinergia: la interacción efectiva entre componentes amplifica resultados. Un sistema de gestión de flotas integrado con GPS y software de optimización de rutas produce mejores resultados que cada herramienta por separado.
  • Jerarquía: los sistemas logísticos operan en múltiples niveles. Desde decisiones estratégicas de ubicación de centros hasta operativas de secuenciación de entregas.

Aplicaciones en transporte y logística

Los sistemas se aplican en múltiples áreas. Gestión de inventarios para mantener niveles óptimos de stock. Planificación de rutas para minimizar distancias y tiempos. Asignación de recursos para optimizar uso de vehículos y conductores. Monitorización en tiempo real para controlar operaciones y detectar incidencias.

Métodos: concepto, importancia y utilidad

Concepto de método

Los métodos cuantitativos son procedimientos sistemáticos que utilizan técnicas matemáticas, estadísticas y algorítmicas para resolver problemas complejos. Transforman datos en información útil para la toma de decisiones.

Importancia estratégica

En el sector logístico, estos métodos permiten cuantificar impactos de decisiones antes de implementarlas. Reducen incertidumbre. Mejoran precisión en predicciones. Optimizan recursos limitados. Facilitan comparación objetiva entre alternativas.

Utilidad práctica

  • Reducción de costes: algoritmos de optimización pueden reducir costes de transporte hasta un 20% mediante mejor planificación de rutas.
  • Mejora del servicio: modelos predictivos ayudan a anticipar demanda y ajustar capacidad, reduciendo tiempos de espera.
  • Gestión de riesgos: análisis cuantitativo identifica vulnerabilidades en cadenas de suministro y desarrolla estrategias de contingencia.

Algoritmo: concepto, tipología y uso

Concepto de algoritmo

Un algoritmo es una secuencia finita de instrucciones precisas que resuelve problemas específicos. En logística, los algoritmos procesan grandes volúmenes de datos para encontrar soluciones óptimas o aproximadas en tiempo razonable.

Tipología de algoritmos

  • Algoritmos exactos: garantizan la solución óptima. El algoritmo de Dijkstra encuentra el camino más corto entre dos puntos en una red de transporte, asegurando la ruta de menor coste.
  • Algoritmos heurísticos: ofrecen buenas soluciones en tiempo reducido sin garantizar optimalidad. El algoritmo del vecino más cercano para el problema del viajante comercial encuentra rutas eficientes para repartidores.
  • Algoritmos metaheurísticos: combinan estrategias de búsqueda para explorar espacios de soluciones complejos. Los algoritmos genéticos optimizan configuraciones de almacenes y rutas simultáneamente.

Uso en aplicaciones logísticas

Los algoritmos se implementan en sistemas de gestión empresarial. Optimizan rutas diarias de reparto. Asignan pedidos a vehículos considerando capacidades y restricciones. Programan mantenimiento preventivo de flotas. Balancean cargas de trabajo entre centros de distribución.

Teoría de grafos

Introducción a los grafos

La teoría de grafos proporciona herramientas matemáticas para modelar y resolver problemas de redes en logística. Un grafo representa relaciones entre elementos mediante nodos y aristas, facilitando el análisis de conectividad, flujos y optimización de trayectorias.

Definición, representación y topología

  • Definición: un grafo G = (V, E) consiste en un conjunto V de vértices (nodos) y un conjunto E de aristas que conectan pares de vértices.
  • Representación: los grafos se representan visualmente mediante diagramas o matemáticamente usando matrices de adyacencia y listas de adyacencia.
  • Topología: describe propiedades estructurales como conectividad, centralidad y densidad que influyen en la eficiencia de redes logísticas.

Ejemplos de aplicación

  • Redes de transporte: cada intersección es un nodo, cada carretera una arista. Los pesos representan distancias, tiempos o costes de tránsito.
  • Cadenas de suministro: proveedores, almacenes y clientes son nodos conectados por flujos de mercancías.
  • Redes de distribución: centros de distribución conectados por rutas de transporte con capacidades limitadas.

Pseudocódigo: conceptos básicos, operadores condicionales y estructura

El pseudocódigo facilita el diseño de algoritmos antes de su implementación. Utiliza sintaxis simplificada que combina lenguaje natural con estructuras lógicas.

Estructura básica:

ALGORITMO nombre_algoritmo
ENTRADA: descripción de datos de entrada
SALIDA: descripción de resultados esperados
INICIO
    instrucción_1
    instrucción_2
    ...
    instrucción_n
FIN

Operadores condicionales:

SI condición ENTONCES
    instrucciones_si_verdadero
SINO
    instrucciones_si_falso
FIN_SI

Ejemplo aplicado: algoritmo para asignar pedidos a vehículos

ALGORITMO asignar_pedidos
ENTRADA: lista_pedidos, lista_vehiculos
SALIDA: asignaciones_optimizadas
INICIO
    PARA cada pedido EN lista_pedidos HACER
        mejor_vehiculo = NULL
        menor_coste = INFINITO
        PARA cada vehiculo EN lista_vehiculos HACER
            SI vehiculo.capacidad >= pedido.peso ENTONCES
                coste = calcular_coste(vehiculo, pedido)
                SI coste < menor_coste ENTONCES
                    menor_coste = coste
                    mejor_vehiculo = vehiculo
                FIN_SI
            FIN_SI
        FIN_PARA
        asignar(pedido, mejor_vehiculo)
    FIN_PARA
FIN

Problemas de caminos

Árbol parcial mínimo

Un árbol parcial mínimo conecta todos los nodos de un grafo con el mínimo coste total de aristas. En logística, esto permite diseñar redes de distribución que conecten todos los puntos con la inversión mínima en infraestructura.

Aplicación práctica: una empresa de distribución necesita conectar 10 almacenes regionales. El árbol parcial mínimo determina qué conexiones directas establecer para minimizar costes de comunicación manteniendo conectividad completa.

Algoritmo de Prim

El algoritmo de Prim construye el árbol parcial mínimo añadiendo iterativamente la arista de menor peso que conecta el árbol parcial con un nuevo nodo.

Pseudocódigo:

ALGORITMO Prim
ENTRADA: grafo G = (V, E), nodo_inicial
SALIDA: arbol_minimo
INICIO
    arbol_minimo = {nodo_inicial}
    aristas_candidatas = aristas_adyacentes(nodo_inicial)
    MIENTRAS arbol_minimo ≠ V HACER
        arista_minima = encontrar_minima(aristas_candidatas)
        AÑADIR arista_minima A arbol_minimo
        AÑADIR nuevo_nodo A arbol_minimo
        ACTUALIZAR aristas_candidatas
    FIN_MIENTRAS
FIN

Ejemplo: diseño de red de fibra óptica entre centros logísticos. El algoritmo selecciona conexiones que minimizan longitud total de cable necesario.

Algoritmo de Kruskal

Kruskal ordena todas las aristas por peso creciente y las añade al árbol si no crean ciclos.

Pseudocódigo:

ALGORITMO Kruskal
ENTRADA: grafo G = (V, E)
SALIDA: arbol_minimo
INICIO
    ORDENAR E por peso creciente
    arbol_minimo = conjunto_vacio
    PARA cada arista e EN E HACER
        SI añadir e NO crea ciclo ENTONCES
            AÑADIR e A arbol_minimo
        FIN_SI
    FIN_PARA
FIN

Ventaja: eficiente para grafos dispersos. Útil cuando se diseñan redes con pocas conexiones relativas al número de nodos.

Camino más corto

El problema del camino más corto encuentra la ruta de menor coste entre dos nodos. Fundamental para sistemas de navegación y optimización de rutas de reparto.

Algoritmo de Dijkstra

Dijkstra calcula distancias mínimas desde un nodo origen a todos los demás nodos del grafo.

Pseudocódigo:

ALGORITMO Dijkstra
ENTRADA: grafo G, nodo_origen
SALIDA: distancias_minimas, caminos_optimos
INICIO
    PARA cada nodo v EN V HACER
        distancia[v] = INFINITO
        predecesor[v] = NULL
    FIN_PARA
    distancia[nodo_origen] = 0
    nodos_no_visitados = V
    
    MIENTRAS nodos_no_visitados ≠ vacio HACER
        u = nodo con distancia[u] minima EN nodos_no_visitados
        REMOVER u DE nodos_no_visitados
        PARA cada vecino v DE u HACER
            nueva_distancia = distancia[u] + peso(u,v)
            SI nueva_distancia < distancia[v] ENTONCES
                distancia[v] = nueva_distancia
                predecesor[v] = u
            FIN_SI
        FIN_PARA
    FIN_MIENTRAS
FIN

Aplicación real: sistema GPS de vehículos comerciales que calcula rutas óptimas considerando restricciones de peso, altura y materiales peligrosos.

Ejemplo numérico: una empresa de mensajería tiene 6 oficinas conectadas por carreteras con diferentes tiempos de tránsito. Dijkstra determina la ruta más rápida desde la oficina central a cualquier sucursal.

Problemas de flujos

Flujo total máximo

El problema de flujo máximo determina la cantidad máxima de material que puede transportarse desde un origen hasta un destino a través de una red con capacidades limitadas.

Aplicación logística: determinar el throughput máximo de un puerto o aeropuerto considerando capacidades de muelles, almacenes y vías de acceso.

Algoritmo de Ford-Fulkerson

El algoritmo de Ford-Fulkerson encuentra el flujo máximo mediante búsqueda de caminos aumentantes en la red residual.

Pseudocódigo:

ALGORITMO Ford-Fulkerson
ENTRADA: red G, nodo_origen s, nodo_destino t
SALIDA: flujo_maximo
INICIO
    flujo_actual = 0
    MIENTRAS existe camino aumentante de s a t HACER
        capacidad_residual = capacidad_minima_en_camino
        PARA cada arista e EN camino HACER
            aumentar flujo(e) EN capacidad_residual
        FIN_PARA
        flujo_actual = flujo_actual + capacidad_residual
    FIN_MIENTRAS
    DEVOLVER flujo_actual
FIN

Caso práctico: una empresa gestiona una red de oleoductos. Ford-Fulkerson calcula el volumen máximo de combustible transportable desde refinerías hasta estaciones de servicio, considerando capacidades de tuberías y estaciones de bombeo.

Casos prácticos

  • Gestión portuaria: optimizar flujo de contenedores desde barcos hasta camiones, considerando capacidades de grúas, zonas de almacenamiento y accesos terrestres.
  • Redes de distribución: maximizar throughput en centros de distribución con múltiples muelles de carga y descarga.
  • Transporte multimodal: calcular capacidad máxima de redes que combinan transporte por carretera, ferrocarril y marítimo.

Programación lineal

Introducción a la programación lineal

La programación lineal optimiza funciones lineales sujetas a restricciones lineales. Esta técnica matemática resulta especialmente útil en logística para asignar recursos limitados de manera óptima.

¿Qué es la programación lineal?

La programación lineal resuelve problemas de optimización donde tanto la función objetivo como las restricciones son lineales. Permite encontrar la mejor solución posible dentro de un conjunto de alternativas factibles.

Componentes principales:

  • Variables de decisión: representan decisiones a tomar
  • Función objetivo: expresión matemática a optimizar
  • Restricciones: limitaciones del problema

El primer modelo matemático

Ejemplo básico de transporte:

Una empresa debe enviar productos desde 2 almacenes a 3 tiendas:

Variables de decisión:

  • x₁₁ = unidades enviadas del almacén 1 a la tienda 1
  • x₁₂ = unidades enviadas del almacén 1 a la tienda 2
  • x₁₃ = unidades enviadas del almacén 1 a la tienda 3
  • x₂₁ = unidades enviadas del almacén 2 a la tienda 1
  • x₂₂ = unidades enviadas del almacén 2 a la tienda 2
  • x₂₃ = unidades enviadas del almacén 2 a la tienda 3

Función objetivo (minimizar costes de transporte): Min Z = 3x₁₁ + 4x₁₂ + 6x₁₃ + 2x₂₁ + 5x₂₂ + 4x₂₃

Restricciones de capacidad de almacenes: x₁₁ + x₁₂ + x₁₃ ≤ 100 x₂₁ + x₂₂ + x₂₃ ≤ 80

Restricciones de demanda de tiendas: x₁₁ + x₂₁ = 60 x₁₂ + x₂₂ = 70 x₁₃ + x₂₃ = 40

Restricciones de no negatividad: xᵢⱼ ≥ 0 para todo i, j

Transformaciones de variables

  • Variables acotadas: cuando una variable tiene límites superior e inferior x ∈ [a, b] se transforma en x = a + x’ donde x’ ≥ 0 y x’ ≤ b – a
  • Variables sin restricción de signo: se descompone en diferencia de dos variables no negativas x = x⁺ – x⁻ donde x⁺ ≥ 0 y x⁻ ≥ 0

Transformaciones de la función objetivo

  • Maximización a minimización: Max f(x) = -Min(-f(x))
  • Múltiples objetivos: se utiliza ponderación o programación por metas

Transformaciones de restricciones

  • Restricciones de igualdad: se mantienen como están
  • Restricciones de desigualdad ≤: se añade variable de holgura aᵢx ≤ bᵢ → aᵢx + sᵢ = bᵢ donde sᵢ ≥ 0
  • Restricciones de desigualdad ≥: se añade variable de exceso aᵢx ≥ bᵢ → aᵢx – eᵢ = bᵢ donde eᵢ ≥ 0

Resolución gráfica

La resolución gráfica se aplica a problemas con dos variables de decisión. Permite visualizar el espacio de soluciones y identificar gráficamente la solución óptima.

Área de soluciones factibles

El área factible es la región que satisface simultáneamente todas las restricciones. Se determina:

  1. Graficando cada restricción como una línea
  2. Identificando el lado correcto de cada línea según la desigualdad
  3. Encontrando la intersección de todas las regiones válidas

Ejemplo gráfico: problema de transporte con dos rutas

Variables:

  • x₁ = número de camiones por ruta 1
  • x₂ = número de camiones por ruta 2

Función objetivo: Min Z = 50x₁ + 60x₂

Restricciones:

  • x₁ + x₂ ≥ 10 (demanda mínima)
  • 2x₁ + x₂ ≤ 20 (limitación de conductores)
  • x₁ ≤ 8 (capacidad ruta 1)
  • x₁, x₂ ≥ 0

Variables básicas y no básicas

En cada vértice del área factible:

  • Variables básicas: toman valores positivos
  • Variables no básicas: toman valor cero

El número de variables básicas iguala el número de restricciones de igualdad.

Solución óptima

La solución óptima se encuentra en un vértice del área factible. Se evalúa la función objetivo en cada vértice para determinar el óptimo.

Método gráfico:

  1. Dibujar líneas de nivel de la función objetivo
  2. Mover paralelas hasta el último punto de contacto con el área factible
  3. Ese punto es la solución óptima

Tipos de soluciones

  • Solución única: un solo vértice óptimo
  • Soluciones múltiples: la función objetivo es paralela a una arista del área factible
  • Solución no acotada: la función objetivo puede mejorar indefinidamente
  • Problema infactible: no existe área de soluciones factibles

Modelo dual y análisis de sensibilidad

Reglas de transformación primal-dual

Para cada problema primal existe un problema dual asociado:

  • Problema primal: Min cx sujeto a: Ax ≥ b, x ≥ 0
  • Problema dual: Max yb sujeto a: yA ≤ c, y ≥ 0

Significado de las variables duales

Las variables duales representan el valor marginal de los recursos. Indican cuánto mejoraría la función objetivo al aumentar una unidad cada recurso.

Interpretación económica: precio sombra o coste de oportunidad de los recursos escasos.

Análisis de sensibilidad de los coeficientes de coste

Determina el rango de variación de los coeficientes de la función objetivo que mantienen la misma solución óptima.

Aplicación práctica: evaluar impacto de cambios en costes de transporte sobre la estrategia óptima de distribución.

Análisis de sensibilidad de los términos independientes

Analiza cómo afectan cambios en la disponibilidad de recursos (lado derecho de restricciones) a la solución óptima.

Utilidad: determinar valor de recursos adicionales antes de adquirirlos.

Utilidad del precio dual

El precio dual indica:

  • Valor económico de recursos escasos
  • Prioridad en la adquisición de recursos adicionales
  • Impacto de cambios en disponibilidad de recursos

Ejemplo: si el precio dual de la capacidad de almacén es €15/m³, aumentar la capacidad en 1 m³ reduciría los costes totales en €15.

Programación lineal entera y mixta

Variables reales, enteras y binarias

  • Variables reales: pueden tomar cualquier valor real no negativo
  • Variables enteras: restringidas a valores enteros (0, 1, 2, 3, …)
  • Variables binarias: solo pueden tomar valores 0 ó 1

Utilidad de las variables binarias

Las variables binarias modelan decisiones de tipo sí/no:

  • Abrir o no un almacén
  • Utilizar o no una ruta
  • Asignar o no un vehículo a una zona

Ejemplo de modelado: yᵢ = 1 si se abre el almacén i, 0 en caso contrario

Coste fijo de apertura: Σ fᵢyᵢ Restricción lógica: si xᵢⱼ > 0 entonces yᵢ = 1 Se modela como: xᵢⱼ ≤ Myᵢ donde M es un número muy grande

Casos prácticos: aplicación a la logística

Problema de localización de almacenes

Descripción: decidir ubicación y capacidad de centros de distribución para minimizar costes totales.

Modelado: Variables binarias: yᵢ = 1 si se abre almacén en ubicación i Variables enteras: xᵢⱼ = unidades enviadas desde almacén i a cliente j

Función objetivo: Min Σ fᵢyᵢ + Σ Σ cᵢⱼxᵢⱼ

Problema de ruteo de vehículos simplificado

Descripción: asignar clientes a vehículos minimizando distancia total.

Variables: xᵢⱼₖ = 1 si vehículo k va directamente del cliente i al cliente j

Problema de planificación de turnos

Descripción: asignar conductores a turnos cumpliendo regulaciones laborales.

Variables binarias: yᵢⱼ = 1 si conductor i trabaja turno j

Utilización de la herramienta “Solver” de Excel

Excel Solver permite resolver problemas de programación lineal de tamaño moderado.

Pasos para usar Solver:

  1. Preparar datos: organizar variables, función objetivo y restricciones en celdas
  2. Definir celdas variables: seleccionar celdas que contienen variables de decisión
  3. Establecer función objetivo: indicar celda a optimizar y tipo (minimizar/maximizar)
  4. Añadir restricciones: especificar limitaciones del problema
  5. Configurar opciones: seleccionar método Simplex LP para problemas lineales
  6. Resolver: ejecutar Solver y analizar resultados

Ejemplo práctico en Excel:

Problema de transporte entre 2 almacenes y 3 clientes:

    A    B    C    D    E    F    G
1        Cliente1 Cliente2 Cliente3 Capacidad
2  Alm1    3      4       6       100
3  Alm2    2      5       4        80
4  Demanda 60     70      40
5
6        Cliente1 Cliente2 Cliente3 Enviado
7  Alm1   =B7    =C7     =D7      =SUMA(B7:D7)
8  Alm2   =B8    =C8     =D8      =SUMA(B8:D8)
9  Recibido =SUMA(B7:B8) =SUMA(C7:C8) =SUMA(D7:D8)
10
11 Coste Total: =B2*B7+C2*C7+D2*D7+B3*B8+C3*C8+D3*D8

Configuración de Solver:

  • Celda objetivo: G11 (minimizar)
  • Variables: rango B7:D8
  • Restricciones:
    • E7 ≤ E2 (capacidad almacén 1)
    • E8 ≤ E3 (capacidad almacén 2)
    • B9 = B4 (demanda cliente 1)
    • C9 = C4 (demanda cliente 2)
    • D9 = D4 (demanda cliente 3)
    • B7:D8 ≥ 0 (no negatividad)

Algoritmos heurísticos aplicados a la resolución de problemas logísticos

Los algoritmos heurísticos proporcionan soluciones buenas en tiempo razonable para problemas complejos donde métodos exactos son impracticables. En logística, estos algoritmos abordan problemas de gran escala con múltiples variables y restricciones.

Problema del viajante de comercio (Travelling Salesman Problem, TSP)

Descripción del problema

Un viajante debe visitar n ciudades exactamente una vez y regresar al punto de partida, minimizando la distancia total recorrida.

Aplicación logística: ruta óptima para vehículo de reparto que debe visitar múltiples clientes.

Formulación matemática

Variables binarias: xᵢⱼ = 1 si se viaja directamente de ciudad i a ciudad j

Función objetivo: Min Σ Σ dᵢⱼxᵢⱼ

Restricciones:

  • Cada ciudad se visita exactamente una vez: Σ xᵢⱼ = 1 ∀j
  • Se sale de cada ciudad exactamente una vez: Σ xᵢⱼ = 1 ∀i
  • Eliminación de subciclos

Algoritmos heurísticos para TSP

Algoritmo del vecino más cercano:

ALGORITMO vecino_mas_cercano
ENTRADA: matriz_distancias, ciudad_inicial
SALIDA: ruta_completa, distancia_total
INICIO
    ciudad_actual = ciudad_inicial
    ciudades_no_visitadas = todas_las_ciudades - {ciudad_inicial}
    ruta = [ciudad_inicial]
    distancia_total = 0
    
    MIENTRAS ciudades_no_visitadas ≠ vacío HACER
        ciudad_mas_cercana = encontrar_minima_distancia(ciudad_actual, ciudades_no_visitadas)
        AÑADIR ciudad_mas_cercana A ruta
        distancia_total += distancia(ciudad_actual, ciudad_mas_cercana)
        ciudad_actual = ciudad_mas_cercana
        REMOVER ciudad_mas_cercana DE ciudades_no_visitadas
    FIN_MIENTRAS
    
    distancia_total += distancia(ciudad_actual, ciudad_inicial)
    AÑADIR ciudad_inicial A ruta
    DEVOLVER ruta, distancia_total
FIN

Algoritmo 2-opt: Mejora una solución inicial intercambiando aristas:

ALGORITMO 2_opt
ENTRADA: ruta_inicial
SALIDA: ruta_mejorada
INICIO
    mejor_distancia = calcular_distancia(ruta_inicial)
    mejorado = VERDADERO
    
    MIENTRAS mejorado HACER
        mejorado = FALSO
        PARA i = 0 HASTA n-2 HACER
            PARA j = i+2 HASTA n HACER
                nueva_ruta = intercambiar_aristas(ruta, i, j)
                nueva_distancia = calcular_distancia(nueva_ruta)
                SI nueva_distancia < mejor_distancia ENTONCES
                    ruta = nueva_ruta
                    mejor_distancia = nueva_distancia
                    mejorado = VERDADERO
                FIN_SI
            FIN_PARA
        FIN_PARA
    FIN_MIENTRAS
    DEVOLVER ruta
FIN

Caso práctico: empresa de reparto de medicamentos con 15 farmacias. El TSP determina la ruta diaria óptima, reduciendo tiempo de entrega y costes de combustible.

Problema de rutas de vehículos (Vehicle Routing Problem, VRP)

Descripción del problema

Extensión del TSP donde múltiples vehículos con capacidad limitada atienden clientes desde un depósito central.

Variantes principales:

  • CVRP (Capacitated VRP): restricciones de capacidad
  • VRPTW (VRP with Time Windows): ventanas temporales de servicio
  • VRPD (VRP with Deliveries): entregas y recogidas

Algoritmo de Clarke-Wright

Construye rutas combinando clientes mediante ahorros de distancia:

ALGORITMO Clarke_Wright
ENTRADA: clientes, deposito, capacidades_vehiculos
SALIDA: rutas_optimizadas
INICIO
    // Calcular ahorros para todos los pares de clientes
    PARA cada cliente i HACER
        PARA cada cliente j > i HACER
            ahorro[i,j] = distancia(deposito,i) + distancia(deposito,j) - distancia(i,j)
        FIN_PARA
    FIN_PARA
    
    // Ordenar ahorros de mayor a menor
    ORDENAR lista_ahorros POR valor DESCENDENTE
    
    // Inicializar rutas individuales para cada cliente
    rutas = crear_rutas_individuales(clientes)
    
    // Combinar rutas basándose en ahorros
    PARA cada ahorro EN lista_ahorros HACER
        cliente_i = ahorro.cliente1
        cliente_j = ahorro.cliente2
        ruta_i = encontrar_ruta(cliente_i)
        ruta_j = encontrar_ruta(cliente_j)
        
        SI ruta_i ≠ ruta_j Y se_pueden_combinar(ruta_i, ruta_j) ENTONCES
            nueva_ruta = combinar_rutas(ruta_i, ruta_j, cliente_i, cliente_j)
            SI capacidad(nueva_ruta) ≤ capacidad_vehiculo ENTONCES
                reemplazar_rutas(ruta_i, ruta_j, nueva_ruta)
            FIN_SI
        FIN_SI
    FIN_PARA
    
    DEVOLVER rutas
FIN

Ejemplo aplicado: empresa de bebidas con 50 clientes y 8 camiones de diferente capacidad. Clarke-Wright optimiza rutas diarias considerando volumen de pedidos y restricciones de carga.

Mejoras heurísticas para VRP

Intercambio intra-ruta: mejora rutas individuales usando técnicas TSP (2-opt, 3-opt)

Intercambio inter-ruta: transfiere clientes entre rutas diferentes

  • 1-1 intercambio: intercambiar un cliente entre dos rutas
  • 2-1 intercambio: mover dos clientes consecutivos a otra ruta

Ejemplo de 1-1 intercambio:

Ruta A: Depósito → Cliente1 → Cliente2 → Cliente3 → Depósito
Ruta B: Depósito → Cliente4 → Cliente5 → Depósito

Después del intercambio Cliente2 ↔ Cliente4:
Ruta A: Depósito → Cliente1 → Cliente4 → Cliente3 → Depósito
Ruta B: Depósito → Cliente2 → Cliente5 → Depósito

Problema de la mochila (Knapsack Problem, KP)

Descripción del problema

Seleccionar objetos con peso y valor específicos para maximizar valor total sin exceder capacidad de la mochila.

Aplicación logística: optimizar carga de vehículos con productos de diferente valor y peso.

Variantes del problema

Mochila 0-1: cada objeto se puede tomar una sola vez Mochila ilimitada: número ilimitado de cada objeto Mochila múltiple: múltiples mochilas con diferentes capacidades

Algoritmo heurístico greedy

ALGORITMO mochila_greedy
ENTRADA: objetos[], capacidad_maxima
SALIDA: seleccion_optima, valor_total
INICIO
    // Calcular ratio valor/peso para cada objeto
    PARA cada objeto EN objetos HACER
        objeto.ratio = objeto.valor / objeto.peso
    FIN_PARA
    
    // Ordenar por ratio decreciente
    ORDENAR objetos POR ratio DESCENDENTE
    
    capacidad_restante = capacidad_maxima
    valor_total = 0
    seleccion = []
    
    PARA cada objeto EN objetos HACER
        SI objeto.peso ≤ capacidad_restante ENTONCES
            AÑADIR objeto A seleccion
            valor_total += objeto.valor
            capacidad_restante -= objeto.peso
        FIN_SI
    FIN_PARA
    
    DEVOLVER seleccion, valor_total
FIN

Caso práctico: camión de 15 toneladas debe cargar productos electrónicos. Cada producto tiene peso, volumen y margen de beneficio diferente. El algoritmo selecciona combinación que maximiza beneficios respetando restricciones.

Programación dinámica para mochila 0-1

Para problemas de tamaño moderado, la programación dinámica garantiza solución óptima:

ALGORITMO mochila_dinamica
ENTRADA: objetos[], capacidad W
SALIDA: valor_maximo
INICIO
    n = numero_objetos
    tabla[0...n][0...W] = matriz inicializada en 0
    
    PARA i = 1 HASTA n HACER
        PARA w = 1 HASTA W HACER
            SI objetos[i-1].peso ≤ w ENTONCES
                tabla[i][w] = MAX(
                    tabla[i-1][w],
                    tabla[i-1][w-objetos[i-1].peso] + objetos[i-1].valor
                )
            SINO
                tabla[i][w] = tabla[i-1][w]
            FIN_SI
        FIN_PARA
    FIN_PARA
    
    DEVOLVER tabla[n][W]
FIN

Problema de empaquetado en contenedores (Bin Packing Problem, BPP)

Descripción del problema

Asignar objetos de diferentes tamaños al mínimo número de contenedores de capacidad fija.

Aplicación logística: minimizar número de camiones necesarios para transportar conjunto de pedidos.

Algoritmos heurísticos para BPP

First Fit (FF):

ALGORITMO first_fit
ENTRADA: objetos[], capacidad_contenedor
SALIDA: asignacion_contenedores
INICIO
    contenedores = []
    
    PARA cada objeto EN objetos HACER
        colocado = FALSO
        PARA cada contenedor EN contenedores HACER
            SI contenedor.espacio_libre ≥ objeto.tamaño ENTONCES
                AÑADIR objeto A contenedor
                contenedor.espacio_libre -= objeto.tamaño
                colocado = VERDADERO
                SALIR_BUCLE
            FIN_SI
        FIN_PARA
        
        SI NO colocado ENTONCES
            nuevo_contenedor = crear_contenedor()
            AÑADIR objeto A nuevo_contenedor
            AÑADIR nuevo_contenedor A contenedores
        FIN_SI
    FIN_PARA
    
    DEVOLVER contenedores
FIN

Best Fit (BF): coloca cada objeto en el contenedor con menor espacio libre suficiente

First Fit Decreasing (FFD): ordena objetos por tamaño decreciente antes de aplicar First Fit

ALGORITMO first_fit_decreasing
ENTRADA: objetos[], capacidad_contenedor
SALIDA: asignacion_optimizada
INICIO
    ORDENAR objetos POR tamaño DESCENDENTE
    DEVOLVER first_fit(objetos, capacidad_contenedor)
FIN

Comparación de rendimiento:

  • FF: rápido pero puede desperdiciar espacio
  • BF: mejor utilización pero más lento
  • FFD: excelente compromiso entre calidad y velocidad

Aplicación práctica avanzada

Empresa de mudanzas: optimizar carga de camiones considerando peso, volumen y fragilidad de objetos.

Variables adicionales:

  • Restricciones de peso por eje
  • Compatibilidad entre objetos (frágiles vs pesados)
  • Orden de carga/descarga

Algoritmo modificado:

ALGORITMO bin_packing_mudanzas
ENTRADA: objetos[], camiones[], restricciones[]
SALIDA: plan_carga_optimizado
INICIO
    // Clasificar objetos por tipo
    fragiles = filtrar_objetos(objetos, "frágil")
    pesados = filtrar_objetos(objetos, "pesado")
    normales = filtrar_objetos(objetos, "normal")
    
    // Secuencia de carga: pesados al fondo, frágiles arriba
    PARA cada camion EN camiones HACER
        cargar_objetos(camion, pesados, "fondo")
        cargar_objetos(camion, normales, "medio")
        cargar_objetos(camion, fragiles, "arriba")
        
        verificar_restricciones(camion, restricciones)
    FIN_PARA
    
    DEVOLVER plan_carga
FIN

Libros sobre métodos cuantitativos aplicados a la logística