Modelos matematicos y analisis de la complejidad para un Problema de Ruteo con Satisfaccion de Demanda

NASINI, GRACIELA; MONTAGNA, JORGE MARCELO; MELCHIORI, LUCIANA; CORSANO, GABRIELA

Virtual

Simposio; 49 JAIIO - Simposio Argentino de Informatica Industrial e Investigacion Operativa; 2020

SADIO

En la industria forestal, el transporte de troncos para su distribución desde los puntos de suministro a las diferentes industrias que los requieren, representa uno de los factores de mayor impacto en los costos generales. Por tanto, hacer más ecientes las operaciones de transporte mediante una planicación adecuada, constituye un ahorro signicativo para las empresas del sector, representandouna tarea de gran interés.El problema del transporte de troncos ha sido abordado por diferentes autores en la literatura, mediante diversos enfoques de optimización debido a la complejidad computacional asociada a este tipo de problemas de ruteo. Audy y col. [1] presentan una revisión sobre distintas características y metodologías de resolución propuestas para este problema. En Bordón y col. [2] se propone un modelo de Programación Lineal Entera (PLE) que resuelve en forma eciente elproblema de ruteo de troncos en instancias de tama~no moderado (1000 cargas de demanda y 500 camiones disponibles).En este trabajo se aborda el Problema de Ruteo con Satisfacción de Demanda (PRSD) que consiste en generar las rutas de los camiones involucrados a un costo mínimo, mientras se garantiza el suministro de las demandas y el tiempo máximo permitido en una jornada laboral de los conductores.Se presenta una reducción del PRSD a un problema de cubrimiento de un subconjunto de vértices de un digrafo con circuitos, con ciertas restricciones adicionales. Dicho digrafo se caracteriza por ser tripartito, la partición de sus vértices se asocia a los camiones disponibles, los frentes de cosecha que ofertan materia prima y las plantas que la demandan. El subconjunto de vértices acubrir se corresponde con aquellos asociados a las plantas y sus demandas. Las condiciones adicionales de los circuitos indican que los mismos deben contener exactamente un vértice asociado a los camiones y una duración no mayor a la permitida. Esta reducción permitió probar que el PRSD es NP-difícil y proponer modelos de PLE alternativos a los de la literatura.Se trabaja en la evaluación de la performance de los mismos en diferentes instancias y su adaptación al problema que incorpora restricciones de scheduling.