A column generation-based algorithm for solving combined inventory and routing problems

Algoritmo basado en generación de columnas para resolver problemas combinados de ruteo e inventarios

Este trabajo presenta un algoritmo basado en generación de columnas para la solución de problemas combinados de ruteo e inventarios. Este problema trata de coordinar los niveles de inventario del cliente mediante envíos a costo mínimo. Siendo este un problema de decisión combinatorio, ya que combina problemas de ruteo de vehículos (VRP) y problemas de inventario.

Utilizando el método de generación de columnas se pueden generar iterativamente rutas interesantes al sistema basadas en los costos duales, esto es rutas que mejoren la calidad de la función objetivo al presentar costos reducidos negativos. Para esto el problema entero mixto original se relaja para obtener los costos reducidos y se establece un subproblema encargado de generar las rutas. El subproblema se modela como un problema de ruta más corta. Finalmente cuando se tiene un conjunto de rutas atractivas para el modelo, el problema entero mixto es el encargado de seleccionar aquellas rutas que minimicen costos y satisfagan las restricciones establecidas.

INTRODUCCIÓN Y MOTIVACIÓN

Hoy en día muchas empresas tienen que enfrentarse al problema de coordinar las políticas de inventario y la gestión del transporte. Debido a este problema se utilizan diversas estrategias para minimizar los costes logísticos. Una de estas estrategias es el Sistema de Inventario Gestionado por el Proveedor (VMI) donde los proveedores deciden la cantidad que se enviará a los clientes, el periodo de tiempo que se hará la entrega y cómo se distribuirá el producto. Cuando estas decisiones son tomadas por los minoristas se reducen los costes logísticos y el cliente puede reducir el coste de los pedidos.

El VMI puede ser modelado como un Problema de Rutas de Inventario (IRP), que es un problema atractivo por su complejidad y por la aplicabilidad que tiene. De hecho, este problema es NP-Hard porque es una extensión del problema de enrutamiento de vehículos (VRP) e implica decisiones de inventario.

El Problema de Rutas de Inventario (IRP) fue introducido por Federguen y Zipkin [1]. Este problema puede verse como una extensión del clásico problema de rutas de vehículos (VRP). El problema consiste en diseñar un conjunto de rutas de vehículos de coste mínimo, con salida y regreso al depósito, satisfaciendo al mismo tiempo las restricciones de capacidad y los requisitos de los clientes. Los dos tipos de decisiones relativas al inventario y a las rutas se toman simultáneamente.

El problema traslada las responsabilidades de los clientes y los proveedores (Savelsbergh & Song [2]). Los clientes transfieren el control del inventario al proveedor. Los proveedores controlan el nivel de inventario y deciden cuándo entregar, cuánto entregar y cómo entregar. Este cambio tiene ventajas como la reducción de los recursos necesarios para la gestión del inventario para los clientes, y la libertad del proveedor para decidir las rutas, cuándo, cómo y cuánto entregar. Es habitual utilizar la llamada política de pedido hasta el nivel o la política de nivel máximo en el problema de enrutamiento del inventario.