Un modelo de Programación Lineal Entera para un Problema de Transporte de Troncos y estudio de su performance computacional

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

Congreso; LXIX Reunión de Comunicaciones Científicas de la Reunión Anual Virtual de la Unión Matemática Argentina.; 2020

Unión Matemática Argentina

En el presente trabajo se propone un modelo de Programación Lineal Entera para la resolución por optimalidad del problema de ruteo diario de camiones en la industria forestal. El objetivo es generar las rutas de los camiones involucrados a un costo mínimo, mientras se garantiza el suministro de materia prima a las plantas implicadas. El problema considerado se corresponde con una variación del Problema de Recogida y Entrega (PRE) que denominamos Problema de Recogida y Entrega en transporte de troncos (PRETT). Ver [1,2] para la definición en detalle del PRE, y [3] para el PRETT.Se demuestra que PRETT integra la clase de los problemas NP-difíciles. La prueba se basa en una reducción polinomial del problema del viajante (TSP) en grafos bipartitos completos al PRETT.Los modelos que se encuentran habitualmente en la literatura para este problema asumen que los viajes que se deben realizar se conocen de antemano o se generan en una etapa previa a la asignación de las rutas a los vehículos o la asignación de qué materias primas deben ser transportada en cada uno de esos viajes. A diferencia de esos enfoques, en este trabajo se se propone un modelo que determina la configuración de cada viaje junto con las decisiones de asignación de materia prima.Dada la complejidad combinatoria de las soluciones de este modelo, se proponen restricciones adicionales que consisten en reducir el número de soluciones alternativas y establecer relaciones válidas para disminuir el tiempo de cómputo. Se evalúa la performance computacional de las formulaciones propuestas por medio de varios escenarios, demostrando en todos ellos que el enfoque propuesto resuelve eficientemente el problema abordado y mejora la performance respecto a los modelos ya existentes en la literatura.[1] Parragh, S.N., Doerner, K.F., Hartl, R.F. A survey on pickup and delivery problems. J. f ̈ur Betriebswirtschaft 58, 21?51. (2008) https://doi.org/10.1007/s11301-008-0033-7.[2] Parragh, S.N., Doerner, K.F., Hartl, R.F. A survey on pickup and delivery problems. J. f ̈ur Betriebswirtschaft 58, 81?117. (2008) https://doi.org/10.1007/s11301-008-0036-4.[3] Borges, J.G., Diaz-Balteiro, L., McDill, M.E., Rodriguez, L.C.E.: The Management of Industrial Forest Plantations, Managing Forest Ecosystems. Springer, Dordrecht. (2014) https://doi.org/10.1007/978-94-017-8899-1.