Resumen en español

El proyecto se basa en una de las variantes del problema de ruteo de vehículos el cual consiste en diseñar un conjunto óptimo de rutas para una flota de vehículos con el fin de servir un grupo dado de clientes satisfaciendo su demanda. Esa variante es la del VRP con conflictos (VRPC), donde se tiene en cuenta las propiedades físico-químicas de los artículos transportados, pues son materiales cuya naturaleza genera graves consecuencias sobre las condiciones del transporte. El objetivo del presente trabajo es optimizar el recorrido realizado por una flota de vehículos que debe entregar productos químicos en la región del Valle del Cauca y los cuales presentan incompatibilidades entre sí, mediante un modelo de programación lineal entera mixta y la aplicación del algoritmo de los ahorros buscando resolver el problema para instancias de mayor tamaño y minimizar la distancia total recorrida en la entrega de los productos químicos, comparando los resultados obtenidos en cada uno de los algoritmos en términos de la calidad de la solución. El proyecto tiene tres etapas: En la primera se realizó la caracterización del proceso de distribución de productos químicos con restricciones de compatibilidad evidenciando que la empresa caso de estudio transporta en un mismo vehículo productos químicos que presentan incompatibilidades entre sí. A partir de esta información, en la segunda etapa se formuló el modelo matemático el cual se ejecutó en el servidor NEOS obteniendo las rutas a recorrer por la flota de vehículos de acuerdo a la demanda de los clientes, sus coordenadas geográficas y la capacidad de los vehículos. Luego se desarrolla la heurística basada en el algoritmo de los ahorros, en donde la solución de las rutas al resolver el TSP cumple con las restricciones dadas en la formulación matemática. Finalmente, para validar el desempeño del modelo en la tercera etapa se consideraron diferentes escenarios variando por un lado los grupos de productos químicos y por el otro las ubicaciones geográficas, en estos se analizaron dos indicadores como lo son el tiempo de ejecución en el modelo matemático y la calidad de la solución de la heurística con respecto al algoritmo exacto, concluyendo que la heurística basada en el algoritmo de Clarke and Wright presenta resultados de muy buena calidad.