Resolución del problema integrado de enrutamiento y gestión de inventarios con múltiples vehículos mediante programación lineal entera mixta

Introducción

El vendor-managed inventory (VMI) es una iniciativa en la gestión de la cadena de suministros que se popularizó en 1980 gracias a Walmart y Procter & Gamble. Esta iniciativa considera un problema de distribución en el que un producto debe ser enviado desde un proveedor (fabricante o distribuidor) a varios minoristas en un horizonte de tiempo determinado ¹. Cada minorista define un nivel máximo de inventario, que el proveedor debe gestionar a fin de que no haya desabastecimiento, por lo que debe programar sus visitas utilizando vehículos de capacidad limitada y considerando el manejo de inventarios bajo una de dos políticas: maximum level (ML), donde se repone el inventario de acuerdo con la demanda del minorista en cada periodo de tiempo; y order up to level (OU), que busca que las cantidades entregadas alcancen el nivel máximo de inventario. El manejo de la información de inventarios de todos los minoristas es el factor determinante para gestionar la satisfacción de la demanda, minimizando los costos de inventarios. Además, si dentro de los objetivos también está la planificación de las rutas, se configura el inventory routing problem (IRP).

Actualmente, las compañías están experimentando costos elevados de transporte, un incremento en la inversión de inventarios y tiempos de ciclos más largos e impredecibles ². Al mismo tiempo, los clientes son más demandantes, exigiendo precios más bajos, alta calidad, cumplimiento de los tiempos prometidos de entrega y mayor capacidad de respuesta por parte del proveedor, por lo que la integración de sistemas logísticos en las empresas ha ido en aumento, evidenciando los beneficios obtenidos al incorporarlos, tanto para la compañía como para los clientes ³. Los avances tecnológicos y los sistemas de información han impactado significativamente el aumento de la competitividad empresarial a nivel global, donde la logística desarrolla un papel fundamental. Esta cubre desde la planificación, el control y el almacenamiento de los productos hasta la verificación de entregas en los puntos de consumo, con el fin de satisfacer los requerimientos del cliente ⁴.

La correcta gestión de la cadena de suministro ha tomado mayor relevancia, a consecuencia de impactos cada vez más importantes como la necesidad de sostenibilidad ambiental, la congestión urbana, la búsqueda de eficiencia logística y los costos asociados tanto al transporte como al inventario de mercancía ³. Explorar soluciones con el fin de reducir los costos logísticos es un área de interés tanto para la comunidad académica como para la empresarial, en particular el comercio electrónico, pues este ha revolucionado el comportamiento y las necesidades de los clientes y, en consecuencia, la forma en que las empresas hacen negocios. Esto, debido en gran medida al aumento de compras por canales digitales, lo cual ha significado incrementos históricos en ventas y compras por internet, como es el caso del mercado colombiano, con crecimientos hasta del 300 % en el año 2020 ⁵. De igual manera, el comercio electrónico prevé un promedio de crecimiento del 116 % en Latinoamérica entre 2019 y 2024, destacando países como Argentina con 153 % de aumento en estos últimos 5 años, Perú con 121 % y Colombia con 92 % ⁶. Por ello, es indispensable que las empresas se adapten y mejoren sus procesos y operaciones logísticas, en aras ofrecer un mejor servicio, no solo en América Latina, sino a nivel mundial ⁷.

El control de inventarios y su distribución son procesos claves en la pérdida tanto de eficiencia como de eficacia en el campo de la logística. Además, de acuerdo con el Departamento Nacional de Planeación de Colombia, el componente de transporte representa el 30,7 % del costo logístico, seguido de inventarios con el 29,3 % y almacenamiento con el 13,9 %. Según datos de la Encuesta Nacional de Logística 2020, el transporte, almacenamiento e inventarios representan el 73,9 % del costo logístico total ⁸. En consecuencia, para las compañías hay una creciente dificultad para encarar los desafíos logísticos. Esto, en el marco de la búsqueda de alternativas para que sus procesos sean más rápidos, más flexibles y menos costosos ³.

La correcta implementación logística en las organizaciones implica enfocar las acciones en minimizar los costos más representativos, como lo son el transporte, el almacenaje y el manejo de inventarios ⁹. La implementación de un sistema de enrutamiento es un ejemplo de esto, ya que propende por el ahorro de costos logísticos, el ahorro en tiempo de trabajo y una mejor utilización de vehículos, entre otros ¹⁰. De igual manera, la gestión de inventarios permite tener control sobre la compra, reparto y almacenamiento del stock de la empresa, transmitiendo valor agregado al cliente, lo cual se ve reflejado en la puntualidad, la consistencia de entrega y la disponibilidad del producto ¹¹.

En ¹² y ¹³ se presenta la solución exacta de varias clases de problemas de enrutamiento e inventario mediante un algoritmo branch-and-cut. El trabajo desarrollado en ¹⁴ identifica y describe diferentes enfoques en cuanto a estructuras, modelos y métodos de solución para el IRP enfocado al manejo de productos perecederos. De manera similar, en ¹⁵ se presenta un modelo matemático multiobjetivo de ruteo e inventarios para la cadena de suministro de perecederos, donde se establece una propuesta de ruteo, distribución y gestión de inventarios de frutas. Tratar este problema con un enfoque de solución exacta es interesante, ya que estos métodos se utilizan menos que los aproximados, y la mayoría de los investigadores utilizan la capacidad predeterminada del software existente para resolver problemas pequeños o medianos, en lugar de codificar nuevos algoritmos exactos ¹⁶

El estudio propuesto por ¹⁷ evidencia la alta adaptabilidad del problema según los criterios establecidos por el proveedor lo y minoristas. Se consideran diferentes políticas de abastecimiento. Además, un aspecto importante de este estudio es que considera variantes mejoradas de estos modelos para tratar de encontrar un método de resolución exacto mucho más eficiente.

En ¹⁸ se estudia el problema de enrutamiento de inventario de múltiples vehículos y múltiples compartimentos con demandas estocásticas (MCIRPSD) en el contexto de la entrega de combustible, y se desarrollan enfoques heurísticos de dos fases basados en el algoritmo de descomposición de corte único y su versión de corte múltiple para tratar el MCIRPSD en las instancias de mediana y gran escala, donde se demuestra su eficacia.

La variante del IRP clásica ha atraído una atención significativa. Sin embargo, debido a la complejidad del problema, la gran mayoría de artículos introducen métodos de solución heurísticos y metaheurísticos, como la heurística de generación de columnas ¹⁹, la metaheurística adaptativa de búsqueda por vecindad (ALNS) ²⁰ y una heurística de dos fases basada en un modelo de programación lineal ¹⁸.

La literatura sobre algoritmos exactos para variantes del IRP es relativamente escasa. El primer método exacto para el caso de un vehículo que consideró las políticas de inventario ML y OU fue propuesto por ¹². Esta metodología se ha ampliado para manejar múltiples productos y entornos de problemas más complejos, como el transbordo ²² y otras aplicaciones específicas.

La finalidad de este artículo es aplicar modelos de optimización matemática al problema de inventario y enrutamiento de vehículos (multiple vehicle inventory routing problem, o multi-vehicle IRP) que permitan el manejo óptimo de las redes de valor. Se consideran dos enfoques: la distribución óptima de las rutas y el manejo óptimo de los inventarios. Con la adopción de estos modelos, el proveedor determina un plan de distribución que responde interrogantes como ¿qué cantidad de producto se debe enviar a los clientes?, ¿cuándo se debe visitar a los clientes?, ¿cómo deben ser definidas las secuencias de las rutas de distribución? y ¿cuál vehículo debe ser asignado para las rutas de entrega? Se pretende encontrar beneficios para el proveedor, reflejados en la reducción de costos en producción, transporte y optimización de los tiempos de entrega, entre otros; así como para los clientes, minimizando los costos de almacenamiento y reposición de inventarios. Esta propuesta se enfoca en el desarrollo de herramientas para la toma de decisiones que permitan gestionar de forma eficiente la cadena de suministro de empresas de cualquier tamaño.

El propósito del trabajo es adaptar el modelo matemático IRP clásico a su variante con múltiples vehículos (multi-vehicle IRP) para resolverlo mediante modelos de programación lineal entera mixta, planteando dos maneras de gestionar el inventario: maximum level (ML) y order up to level (OU). Así mismo se formulan tres formas de eliminar la creación de sub-tours: una general, una de flujos adaptada de ²³ y ¹⁷ respectivamente y la Miller-Tucker-Zemlin (MTZ) propuesta por ²⁴. En este artículo se desarrolla un modelo matemático exacto flexible, pues se identificó que este problema ha sido resuelto principalmente mediante técnicas aproximadas como heurísticas y metaheurísticas. Además, se describen y comparan los modelos matemáticos por medio de la solución de instancias de baja y media complejidad matemática, presentando la cantidad de variables y restricciones, así como la función objetivo, el tiempo de ejecución y la brecha inexplorada entre el límite superior e inferior del algoritmo Branch & Bound del CPLEX (i.e., GAP). Esto, con el fin de identificar el modelo matemático más competitivo.

Formulación matemática

La definición del multi-vehicle IRP puede representarse mediante un conjunto de clientes indexados en V1 : {1 . . . n}, donde n es el número total de clientes y O : {0} representa al nodo del proveedor. El problema se define sobre un horizonte de planificación de longitud p, en el cual cada periodo de tiempo es representado por el conjunto t : {1 . . . p}. La cantidad de producto disponible para el proveedor en cada periodo de tiempo se expresa con rt, y el cliente es i. El proveedor incurre en un costo unitario de almacenamiento de inventario Hi en cada periodo y tiene una máxima capacidad de almacenamiento de inventario Ci . Además, al inicio del horizonte de planificación, se conocen los datos de los inventarios iniciales tanto del proveedor como de los clientes i, lo cual se denota como It−1 cuando t = 1. El proveedor tiene conocimiento de dit, la demanda de cada cliente i para cada periodo de tiempo t. También se tiene un conjunto de vehículos K : {1 . . . k}, donde k es el número total de vehículos disponibles para trabajar. La capacidad de cada vehículo se denota como Q. Cada vehículo puede realizar una ruta por período de tiempo desde el proveedor hasta un subconjunto de clientes. El costo de enrutamiento Costoij se expresa como la distancia euclidiana entre cada par de nodos

El objetivo del multi-vehicle IRP es minimizar el costo total de enrutamiento y mantenimiento de inventario mientras se satisface la demanda de los clientes, contando con múltiples vehículos para realizar la distribución de productos en un determinado horizonte de tiempo. El plan de reposición está sujeto a las siguientes condiciones: (i) el proveedor debe tener suficiente inventario para satisfacer toda la demanda durante el horizonte de planificación; (ii) al final del período t, el inventario en la ubicación de un cliente no debe exceder su capacidad máxima, (iii) no se permite que los inventarios sean negativos, (iv) cada uno de los vehículos del proveedor puede realizar como máximo una ruta por período de tiempo, (v) cada ruta comienza y termina en el depósito y (vi) las capacidades del vehículo no se pueden exceder.

El multi-vehicle IRP, en contraste con su problema base, considera la inclusión de varios vehículos en la asignación de rutas de distribución. En la Fig. 1 se presenta un escenario de distribución, contando con dos periodos de tiempo, 16 clientes y 3 vehículos que deben regresar al depósito al finalizar el recorrido de las rutas. Además, la secuencia de distribución depende de cada periodo, de acuerdo con la demanda y posición geográfica de los clientes. En el primer periodo, se visita a todos los clientes por medio de los 3 vehículos con el fin de satisfacer la demanda. Sin embargo, en el segundo periodo se utilizan 3 vehículos, pero solo se visita a 13 clientes, debido que los clientes 3, 6 y 11 tienen inventario adecuado para su operación.

Figura 1: Ejemplo gestión de inventarios y enrutamiento de clientes usando múltiples vehículos en un horizonte de tiempo determinado. (a) Periodo de tiempo i, (b) periodo i + 1

El modelo matemático es descrito por las Ecs. ¹ y ¹⁴, y la Tabla I expone los conjuntos, los parámetros y las variables de decisión del modelo matemático.

Sujeto a,

Tabla I: Conjuntos, parámetros y variables de decisión del modelo matemático

La Ec. (1) busca minimizar el costo logístico asociado al almacenamiento de inventario tanto del proveedor como de los clientes, expresado en la primera expresión de suma doble. En la segunda parte de la función objetivo se busca minimizar el costo asociado a las rutas asignadas a cada vehículo en un determinado horizonte de planeación. La Ec. (2) calcula el nivel de inventario del proveedor en cada periodo de tiempo t. La Ec. (3) permite calcular el inventario inicial de cada cliente en cada periodo del horizonte de planeación. La Ec. (4) asegura que el inventario en cada periodo de tiempo sea menor o igual que la máxima capacidad de almacenamiento de cada cliente. La Ec. (5) asegura que la cantidad a enviar por el centro de distribución sea menor o igual a la disponibilidad del almacén del cliente, de acuerdo con su capacidad y su nivel de inventario en el periodo anterior. La Ec. (6) garantiza que la cantidad de productos que se envíe no supere la capacidad de almacén de los clientes introducidos en la ruta de distribución de cada vehículo k.

A su vez, las Ecs. (5) y (6) identifican la política de manejo de inventarios ML, donde se optimiza la cantidad de producto entregado en cada visita a los clientes, asegurando que se respete la capacidad de cada almacén. La Ec. (7) establece que la cantidad de producto a enviar a los clientes introducidos en la ruta debe ser menor o igual que la máxima capacidad de los vehículos. La Ec. (8) establece que, si al cliente i se le envía producto a través del vehículo k en el periodo t, entonces solo se puede activar uno de todos los posibles arcos de entrada. La Ec. (9) establece que, si al cliente j se le envía producto a través del vehículo k en el periodo t, solo se puede activar uno de todos los posibles arcos de salida. La Ec. (10) indica que, si se ingresa al nodo j por medio de un arco, también se debe de salir del nodo j por un arco. Las Ecs. (8), (9), (10) aseguran la conservación del flujo de las rutas, con una única entrada y salida de los nodos para el vehículo k en el periodo t. La Ec. (11) establece que se debe iniciar siempre desde el nodo del centro de distribución. Las Ecs. (12) y (13) garantizan la conexión de los circuitos sin la creación de sub-tours en la formulación general por el método MTZ, la cual fue propuesta por ²³ y adaptada al modelo. Finalmente, las Ecs. (14) y (15) presentan la naturaleza de las variables.

Resultados computacionales

La implementación del algoritmo se llevó a cabo en un computador con procesador Intel Core i5-5200U CPU @ 2.2 GHz con 4 GB de RAM y un tiempo de ejecución máximo de una hora.

Para replicar los modelos multi-vehicle IRP y sus distintas maneras de abordarlo, se utilizó el software de programación algebraica A Mathematical Programming Language (AMPL), con el fin de validar su funcionamiento con las instancias presentadas en la literatura ²⁵

Para probar los modelos propuestos, se utilizaron las instancias propuestas por ²⁶, las cuales fueron generadas para el problema de gestión integrada de rutas e inventario para un producto. Como base, se consideraron los siguientes datos: horizonte temporal H = 6; número de clientes o minoristas de n = 5, 10, 15, 20, 25, 30, 35, 40, 45 y 50; una cantidad de inventario rst utilizado por el cliente s en el periodo t, generada aleatoriamente como un numero entero en un intervalo (10, 100); el costo de almacenamiento Hi , generado aleatoriamente en un intervalo (0,01, 0,05); el costo de transporte Costoij , calculado mediante la distancia euclidiana, donde (Xi , Xj ) y (yi , yj ) corresponden a las coordenadas del centro de distribución y los clientes, las cuales fueron generadas aleatoriamente en un intervalo de valores (0, 500), obteniendo una matriz de costos simétrica, i.e., Costoij = Costoji.

Se compararon los modelos multi-vehicle IRP con el fin de identificar la modelación que requiere el menor tiempo y ofrece una respuesta de buena calidad.

Cantidad de variables y restricciones

La Tabla II presenta la cantidad de variables y restricciones para los tres modelos (general, MTZ y flujos) para n = 5, 10, 15, 20, 25, 30, 35, 40, 45 y 50 clientes con la política de abastecimiento ML, y para n = 5, 10, 15 y 20 con la política OU, considerando un horizonte de tiempo H = 3 y dos vehículos K = 2.

Tabla II: Conteo de variables y restricciones, multi-vehicle IRP (H = 3,K = 2)

Se observa que el multi-vehicle IRP es un problema NP-hard, debido a su crecimiento exponencial tanto en el número de variables como en el número de restricciones a medida que aumenta el número de clientes. Además, en el multi-vehicle IRP (ML) (H = 3, K = 2), el modelo por flujos presenta mayor cantidad de variables que los modelos general y MTZ, los cuales tienen cantidades de variables muy similares. Los tres modelos presentan cantidades similares de restricciones.

De manera similar para el multi-vehicle IRP (OU) (H = 3, K = 2), el modelo de flujos es el que más número de variables y restricciones presenta en comparación con los modelos MTZ y general. Tanto el número de variables como el de restricciones mantienen una tendencia creciente a medida que el número de clientes aumenta. El modelo multi-vehicle IRP bajo la política OU presenta mayor número de restricciones en todos sus modelos (MTZ, general y flujos) en comparación con el modelo multi-vehicle IRP bajo la política ML. El número de variables tiende a ser igual en ambas políticas de gestión de inventarios.

En la Tabla III se presentan los resultados para el modelo multi-vehicle IRP con horizonte temporal H = 3, pero ya no solo con 2 vehículos sino con tres vehículos para n = 5, 10, 15, 20, 25, 30, 35, 40, 45 y 50 con la política ML, y con n = 5, 10, 15 y 20 para la política OU. Esto, para los tres modelos (general, MTZ y flujos).

Tabla III: Conteo de variables y restricciones, multi-vehicle IRP (H = 3,K = 3)

Se evidencia que, en el modelo multi-vehicle IRP (H = 3, K = 3), las variantes general y MTZ comparten la misma cantidad de variables. Sin embargo, en la variante de flujos se observa una mayor cantidad de variables, la cual se hace evidente a medida que la cantidad de clientes aumenta. En cuanto a la cantidad de restricciones, se observa que los tres modelos presentan un comportamiento similar. Sin embargo, el modelo de flujos presenta una cantidad de restricciones levemente mayor.

El modelo multi-vehicle IRP (OU) (H = 3, K = 3), comparado con su contraparte ML (H = 3, K = 3), presenta igual número de variables en los modelos MTZ y general, pero su variante de flujos muestra leves diferencias en el número de variables. A su vez, la cantidad de restricciones es mayor en OU que en ML.

Tiempos de ejecución y GAP

Multi-vehicle IRP (ML) H=3, K=2

A continuación, se presentan los resultados de la función objetivo ($), tiempos (s) y GAP ( %) obtenidos para el modelo multiple-vehicle IRP bajo las políticas de inventario ML y OU, con un horizonte de planeación de tres periodos (H = 3) y considerando 2 vehículos (K = 2) bajo distintos modelos de eliminación de sub-tours (general, MTZ y flujos). Se presentan las mejores soluciones (best known solutions, BKS) reportadas por ²⁷ para la política ML, con el fin de comparar la función objetivo de las instancias implementadas.

En la Tabla IV se puede evidenciar que la tendencia creciente de los tiempos computacionales se mantiene a medida que el número de clientes aumenta, dado que esto implica dar respuesta a un mayor número de variables y restricciones. Por ejemplo, para el modelo de flujos, mientras que, para una instancia de 5 clientes, la respuesta óptima (GAP = 0 %) se logra en 2 segundos, para 50 clientes, una respuesta muy cercana al óptimo (GAP = 3,88 %) se logra en 1.476 segundos. Para este modelo, debido a su alta complejidad computacional, se obtuvieron GAP entre el 0 y el 15 % para el modelo general, entre el 0 y el 10 % para el modelo MTZ y entre el 0 y el 7,5 % para el modelo de flujos.

Tabla IV: Resultados del multi-vehicle IRP (ML) (H = 3, K = 2)

Multi-vehicle IRP (ML) H=3, K=3

En la Tabla V se presentan los resultados para tres periodos de tiempo (H = 3) y tres vehículos (K = 3). Aquí se observa cómo el problema aumenta su complejidad al comparar los tiempos de ejecución con respecto al modelo con K = 2. Por ejemplo, mientras que, para resolver una instancia de 20 clientes con K = 2, el modelo de flujos se demoraba 674 segundos y se obtenía un GAP del 0,26 %, ahora, con K = 3, para resolver la misma instancia de 20 clientes con el modelo de flujos, se obtiene un GAP del 3,08 % en 3.600 segundos.

Tabla V: Resultados del multi-vehicle IRP (ML) (H = 3, K = 3)

Multi-vehicle IRP (OU) H=3, K=2

En la Tabla VI se muestra cómo, para las políticas OU y ML, la tendencia creciente de los tiempos computacionales se mantiene a medida que el número de clientes aumenta.

Tabla VI: Resultados del multi-vehicle IRP (OU) (H = 3, K = 2

Multi-vehicle IRP (OU) H=3, K=3

En la Tabla VII se presentan los resultados del modelo multi-vehicle IRP (H = 3, K = 3) bajo la política de gestión de inventarios OU.

Tabla VII: Resultados del multi-vehicle IRP (OU) (H = 3, K = 3)

Interpretación de resultados

Para la interpretación de resultados, se propone la siguiente instancia, donde se tienen tanto la latitud como la longitud del proveedor y los clientes, inventarios iniciales, costos unitarios de almacenamiento, demanda de los clientes y máximas capacidades de almacenamiento. Además, n representa el número de clientes (5 para este caso), p es el horizonte de planificación (3 meses), k es el número de vehículos disponibles (3 en este caso), r es la cantidad de producto disponible en el proveedor en cada instante de tiempo del horizonte de planificación (193) y Q es la capacidad de transporte constante de cada vehículo, que corresponde a 96.

En la Fig. 2 se presentan los resultados obtenidos mediante el programa Power BI, con la visualización de las rutas generadas a partir de los 3 vehículos en el plan de distribución para el mes 1. Además, se presentan las cantidades a entregar y el inventario al final del mes de cada uno de los clientes. En este caso, se muestra que el cliente 5 es visitado con el vehículo 3, se le entregan 11 unidades de producto, y su inventario al final del mes será de 11 unidades.

Figura 2: Plan de distribución. (a) Periodo 1, (b) periodo 2, (c) periodo 3

Tabla VIII: Parámetros de la instancia propuesta

Conclusiones

En esta investigación se presenta una metodología general de solución mediante programación exacta que puede ser adaptada para diferentes campos de aplicación del problema integrado de inventarios y enrutamiento con múltiples vehículos. Esto, con el fin de identificar el más eficiente.

Los modelos matemáticos implementados en AMPL son capaces de resolver el IRP con múltiples vehículos bajo diferentes políticas de inventario, permitiendo obtener los planes de distribución y gestión de inventarios. El modelo más eficiente para eliminación de sub-tours es el de flujos para las dos políticas de abastecimiento estudiadas (ML como OU). Esto se hace evidente a medida que el número clientes o el número de periodos evaluados aumenta. Cabe añadir que la política ML muestra mejores valores de GAP en comparación con la política OU

Debido a la alta complejidad computacional del problema, los trabajos futuros deben encaminarse en busca de nuevas alternativas diferentes a la optimización exacta, tales como heurísticas o metaheurísticas, que permitan estar lo más cerca posible del óptimo en tiempos de computación menores, validando la implementación por medio de instancias pequeñas y comparando estas técnicas aproximadas con las exactas. De igual manera, se recomienda el desarrollo de un modelo dinámico que pueda incluir variables estocásticas y análisis probabilístico. Esto permitiría una representación más completa del sistema, así como la consideración de demandas estocásticas. De igual manera, podrían incluirse funciones multiobjetivo en distintos frentes además de la reducción de costos, como las emisiones contaminantes, restricciones en los de horarios de los vehículos, entre otros. También podría incursionarse en el problema con flotas propias y subcontratadas, así como con transbordo.