Un modelo de programación lineal entera para un problema de transporte de troncos y estudio de su performance computacional

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

Virtual

Congreso; VirtUMA - Reunión Anual Unión Matemática Argentina; 2020

UMA

En el presente trabajo se propone un modelo de Programación Lineal Entera para la resoluciónpor optimalidad del problema de ruteo diario de camiones en la industria forestal. El objetivoes generar las rutas de los camiones involucrados a un costo mínimo, mientras se garantiza elsuministro de materia prima a las plantas implicadas. El problema considerado se correspondecon una variación del Problema de Recogida y Entrega (PRE) que denominamos Problemade Recogida y Entrega en transporte de troncos (PRETT). Ver [1, 2] para la denición endetalle del PRE, y [3] para el PRETT.Se demuestra que PRETT integra la clase de los problemas NP-difíciles. La prueba se basaen una reducción polinomial del problema del viajante (TSP) en grafos bipartitos completosal PRETT.Los modelos que se encuentran habitualmente en la literatura para este problema asumenque los viajes que se deben realizar se conocen de antemano o se generan en una etapa previaa la asignación de las rutas a los vehículos o la asignación de qué materias primas deben sertransportadas en cada uno de esos viajes. A diferencia de esos enfoques, en este trabajo sepropone un modelo que determina la conguración de cada viaje junto con las decisiones deasignación de materia prima.Dada la complejidad combinatoria de las soluciones de este modelo, se proponen restriccionesadicionales que consisten en reducir el número de soluciones alternativas y establecer relacionesválidas para disminuir el tiempo de cómputo. Se evalúa la performance computacional delas formulaciones propuestas por medio de varios escenarios, demostrando en todos ellos queel enfoque propuesto resuelve ecientemente el problema abordado y mejora la performancerespecto a los modelos ya existentes en la literatura.