Modelos matemáticos y análisis de la complejidad para un Problema de Ruteo con Satisfacción de Demanda

LUCIANA MELCHIORI; GRACIELA NASINI; JORGE M. MONTAGNA; GABRIELA CORSANO

Simposio; Simposio Argentino de Informática Industrial e Investigación Operativa de las 49ºJornadas Argentinas de Informática; 2020

Sociedad Argentina de Informática (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 eficientes las operaciones de transporte mediante una planificación adecuada, constituye un ahorro significativo para las empresas del sector, representando una 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 eficiente el problema de ruteo de troncos en instancias de tamaño 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.[1] Audy, J. F., D´Amours, S., Ronnqvist, M. : Planning methods and decision support systems in vehicle routing problems for timber transportation: a review. CIRRELT research paper, 38. Montreal, Canada. (2012)[2] Bordón, M, Montagna, J.M., Corsano, G. : An exact mathematical formulation for the optimal log transportation. Forest Policy and Economics 95, 115-122 (2018)