Desarrollo de una alternativa metaheurística de dos fases para el problema de ruteo de vehículos, con restricciones de capacidad y flota homogénea

Durante los últimos años se han desarrollado nuevas oportunidades de penetración en otros mercados, aumentando así la necesidad de ser cada día más competitivos y prepararnos para participar eficientemente en esta era de la globalización. Gracias a ello, nuevos conocimientos y técnicas se han desarr...

Full description

Autores:: Daza Escorcia, Julio Mario

Tipo de recurso:: Trabajo de grado de pregrado

Fecha de publicación:: 2007

Institución:: Corporación Universidad de la Costa

Repositorio:: REDICUC - Repositorio CUC

Idioma:: spa

Description
Summary:	Durante los últimos años se han desarrollado nuevas oportunidades de penetración en otros mercados, aumentando así la necesidad de ser cada día más competitivos y prepararnos para participar eficientemente en esta era de la globalización. Gracias a ello, nuevos conocimientos y técnicas se han desarrollado para poder mejorar y gestionar los sistemas organizativos desde una perspectiva diferente a la tradicional. La actividades logística abordan el estudio de cuatro flujos: el físico de carga, el físico de la documentación, el efectivo y la información, desde el proveedor hasta el consumidor final, con el objetivo de poder garantizar que los productos lleguen al consumidor final en el momento y lugar adecuado, con la cantidad requerida, la mejor calidad y al menor costo posible. Este enfoque incluye entonces el estudio integrado de funciones básicas de la organización, tales como la gestión del aprovisionamiento, la gestión de la distribución física de entrada y de salida, y la gestión de la producción, todo lo anterior con el apoyo relevante de la gestión del transporte. Por ello, se hace necesario el estudio de las particularidades relativas a la logística de transporte y los procesos generados a partir de éstos, como factores determinantes de la competitividad. Esta investigación apunta hacia un objetivo específico en la logística: la gestión del transporte. Al respecto, existen muchos ahorros potenciales para explotar, por ejemplo, la utilización de la capacidad instalada, y la reducción del costo de transporte propiamente dicho por una mejor planificación de rutas, entre otras. La gestión del transporte tiene también oportunidades de innovación tecnológica que proporcionan ventajas competitivas, sobre todo en lo concerniente a sistemas de información dirigidos a contribuir en la reducción de estos costos. En el mismo orden de ideas, la optimización de rutas de transporte, en un sistema logístico real posee infinidad de restricciones que dan como resultado el surgimiento de uno de los problemas más estudiados en el ámbito científico de la optimización combinatoria, denominado problema de ruteo de vehículo PRV, este ocupa gran parte de las investigaciones actuales en diversos lugares del planeta. El problema en su versión más simple, totalmente descifrado hoy, se muestra trivial ante la complejidad de los problemas reales, es entonces como comienzan a estudiarse sus variantes, alcanzando notables cercanías a lo usual en el día a día. El problema que justifica este proyecto es uno de esos acercamientos, y corresponde a situaciones reales de algunas organizaciones de nuestro entorno. El problema escogido es una generalización del problema de ruteo de vehiculo PRV con restricciones de capacidad vehicular (PRVRC), un escenario estático y determinístico ampliamente estudiado en la literatura científica de la optimización combinatoria, el cual consiste en rutear una flota vehicular teniendo en cuenta que esta posee una capacidad determinada. Con respecto a las técnicas para enfrentar el problema, una gran variedad de estas han sido propuestas desde la primera aparición de los PRV's, estos métodos de resolución pueden agruparse en tres grandes grupos, algoritmos exactos, heurísticos y meta heurísticos, los cuales poseen tanto deficiencias como virtudes. La optimización matemática exacta sigue siendo la única forma de obtener un resultado exacto, pero es una alternativa poco práctica, en tiempo y costo, dada la complejidad de los problemas solo las instancias con pocos clientes pueden ser resueltas consistentemente con estos métodos. Los procedimientos heurísticos son ampliamente utilizados en el tratamiento del problema, no obstante la aplicación de estos, no suele garantizar un comportamiento homogéneo en cuanto a la calidad de las soluciones generadas. Un procedimiento heurístico es capaz de proporcionar una solución en muy poco tiempo, pero la calidad de sus soluciones es reducida y no se disponen de métodos para evaluar un posible espacio de soluciones, lo cual no garantiza que el procedimiento se comporte adecuadamente en todas las ocasiones. Los procedimientos meta heurísticos, ejecutan búsquedas por el espacio de soluciones factible, la aplicación de estos procedimientos, garantizan en mayor medida la calidad de la solución, así como la confiabilidad y homogeneidad del comportamiento entre un conjunto de posibles situaciones o estado de las variables y factores del sistema. No obstante el tratamiento práctico de la planificación de clientes, bajo la metodología de algoritmos meta heurísticos, implica una considerable inversión en tiempo de computo debido a la compleja topología de la región de soluciones factibles. Lo anterior puede llegar a ser una restricción importante, especialmente en ambientes logísticos en los que se requieran respuestas inmediatas, tales como los sistemas On-Line El modelo a presentar en esta investigación es una alternativa diseñada e implementada para resolver el PRVRC-FH con una aproximación metaheurística que consta de la combinación de dos fases que son el rutco y la planificación; la primera fase, esta compuesta de procedimientos heuristicos y puede subdividirse en dos partes; la primera, denominada construcción, donde se utilizan algunos métodos de optimización local convencional como el barrido o sweeping en conjunto a la rotación cartesiana para minimizar el tamaño de la flotn y algunas características de la heurística de inserción, acompañada del algoritmo de intercambio Or-Opt, con el objetivo de acercar el proceso hasta una muy buena solución inicial; la segunda parte llamada mejoramiento, emplea un método de búsqueda local inteligente con características de memoria denominado Búsqueda Tabú como una estrategia para mejorar visiblemente los resultados logrados en la primera fase y obtener soluciones no dominadas, esto con un tiempo polinomialmente razonable. Posteriormente se realiza la segunda fase que se denomina planificación, aquí se propone un procedimiento que tiene como función primordial minimizar el costo fijo causado por la utilización de la capacidad instalada. Este modelo se aplicó sobre una instancia no conocida y una instancia real arrojando resultados inimaginables al posicionarse en el primer lugar de las heurísticas evaluadas para resolver este problema en función de los costos de la capacidad instalada.

Desarrollo de una alternativa metaheurística de dos fases para el problema de ruteo de vehículos, con restricciones de capacidad y flota homogénea

Publicaciones similares