Modelos matemáticos y análisis de la complejidad para un problema de ruteo con satisfacción de demanda.

MELCHIORI, LUCIANA; NASINI, GRACIAELA; MONTAGNA, JORGE M.; CORSANO, GABRIELA

Simposio; Simposio Nacional de Ingeniería Industrial e Investigación Operativa, JAIIO 2020; 2020

UBA

En la industria forestal, el transporte de troncos para su distribución desde lospuntos de suministro a las diferentes industrias que los requieren, representa unode los factores de mayor impacto en los costos generales. Por tanto, hacer máseficientes las operaciones de transporte mediante una planificación adecuada,constituye un ahorro significativo 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 lacomplejidad computacional asociada a este tipo de problemas de ruteo. Audy ycol. [1] presentan una revisión sobre distintas características y metodologías deresolución propuestas para este problema. En Bordón y col. [2] se propone unmodelo de Programación Lineal Entera (PLE) que resuelve en forma eficiente elproblema de ruteo de troncos en instancias de tamaño moderado (1000 cargasde 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 costomínimo, mientras se garantiza el suministro de las demandas y el tiempo máximopermitido en una jornada laboral de los conductores.Se presenta una reducción del PRSD a un problema de cubrimiento de unsubconjunto de vértices de un digrafo con circuitos, con ciertas restriccionesadicionales. Dicho digrafo se caracteriza por ser tripartito, la partición de susvértices se asocia a los camiones disponibles, los frentes de cosecha que ofertanmateria prima y las plantas que la demandan. El subconjunto de vértices acubrir se corresponde con aquellos asociados a las plantas y sus demandas. Lascondiciones adicionales de los circuitos indican que los mismos deben contenerexactamente un vértice asociado a los camiones y una duración no mayor a lapermitida. Esta reducción permitió probar que el PRSD es NP-difícil y proponermodelos de PLE alternativos a los de la literatura. Se trabaja en la evaluación de la performance de los mismos en diferentesinstancias y su adaptación al problema que incorpora restricciones de scheduling.