Examinando por Tema "Métodos heurísticos"
  • Documento
    Un algoritmo metaheurístico para la solución del problema de ruteo de vehículos con múltiples depósitos y flota heterogénea
    (Pereira : Universidad Tecnológica de Pereira, 2014) Bolaños, Rubén Iván
    En este trabajo se presenta un algoritmo metaheurístico para resolver el problema de ruteo de vehículos con múltiples depósitos y flota heterogénea (MDHFVRP), la formulación matemática del problema se basa en un modelo de programación lineal entera mixta de cuatro índices propuesto en la literatura especializada. Para solucionar el problema MDHFVRP se utiliza una técnica de solución basada en un algoritmo genético de Chu-Beasley modificado. La metodología presenta un enfoque híbrido que permite generar una población inicial de buena calidad, para ello se utiliza como punto de inicio el procedimiento heurístico de \Lin-Kernighan-Helsgaun" (LKH), apoyado con la solución del modelo de programación lineal para el problema de la ruta m as corta. Dos métodos de recombinación que permiten obtener descendientes diversos son implementados y utilizados de forma conjunta. Adicionalmente, se presenta una etapa de mejoramiento utilizada como operador de mutación, donde seis estrategias de búsqueda local inter-rutas y dos estrategias de búsqueda local intra-rutas son utilizadas, de tal manera que cada descendiente sea mejorado en cada ciclo generacional tal que sea posible entrar a formar parte de la población. Para validar la metodología propuesta, se emplean instancias de prueba cuyo n umero de clientes varia entre 50 y 360. Las instancias han sido adaptadas y utilizadas en la literatura especializada como prueba de las metodologías existentes para el MDHFVRP.
  • Documento
    Análisis y prototipado de un algoritmo genético modificado para solucionar el problema de ruteo de vehículos con ventanas de tiempo (VPTWR), prioridad de metas económicas y componente medio ambiental
    (Pereira : Universidad Tecnológica de Pereira, 2018) Segura Londoño, Catalina ; Arias Hernández, Claudia Patricia ; Ríos Patiño, Jorge Iván
    El origen de los problemas de ruteo se da en el siglo XVIII cuando habitantes de Königsberg, un pueblo de Rusia, debate sobre cuál es la ruta que pasa una sola vez por los siete puentes que atravesaban el río Pregel regresando al punto de origen; este problema lo propuso el matemático suizo Leonhard Euler, quien en el año 1736 demostró que no existía ninguna, además de hacer solo referencia a la existencia de un camino y no a la búsqueda del óptimo, lo que conduce al mismo planteamiento de los problemas de rutas; uno de los más conocidos a lo largo de la historia es el problema de rutas de vehículo (VRP) que ha sido de gran importancia e influencia en investigaciones y estudios enfocados en implementar algoritmos que permitan encontrar una solución óptima. Este tipo de problemas son considerados difíciles de resolver y dentro de la optimización combinatoria son conocidos como problemas NP-Hard, dado que no se obtiene una solución de manera eficiente; así mismo dentro de la teoría de la complejidad computacional pertenecen a la clase NP-Completos, al no poderse garantizar hallar la mejor solución en un tiempo de cómputo razonable, ya que este aumenta de manera exponencial, generando así una búsqueda de soluciones aproximadas, siendo conveniente emplear métodos heurísticos y metaheurísticos que aplican el conocimiento del problema para acercarse a la solución en un tiempo de computo razonable...
  • Documento
    Método heurístico para construir la población inicial del problema de planeamiento integrado de sistemas de distribución de electricidad y gas natural
    (Pereira : Universidad Tecnológica de Pereira, 2013) Alvarez Echavarria, Andrés Felipe
    En la siguiente etapa se comentan los modelos matemáticos que fueron usados para representar el problema de planeamiento de los sistemas de distribución tanto de electricidad como de gas, además, se presenta un modelo integrado que permite realizar el planeamiento óptimo de ambas redes de manera conjunta. Se continúa con una presentación de los diferentes índices de sensibilidad utilizados para desarrollar los algoritmos heurísticos que permitieron encontrar soluciones de buena calidad. Este conjunto de soluciones se construye con el objetivo de formar una población inicial con respuestas de buena calidad para técnicas de solución más robustos. Una vez presentados los índices de sensibilidad, se proponen diversos algoritmos heurísticos que dan solución al planeamiento de redes de distribución de energía eléctrica y gas. Se presentan tanto alternativas de algoritmos heurísticos para ambos sistemas desintegrados como para el sistema integrado de electricidad y gas. Los resultados obtenidos presentan en primera instancia la solución del modelo matemático planteado para representar el problema de planeamiento de redes de distribución de electricidad y gas. Luego, se muestra el conjunto de soluciones obtenidas a partir de los algoritmos heurísticos propuestos.
  • Documento
    Métodología híbrida para resolver el problema de ruteo de vehículos con depósitos múltiples considerando el consumo de combustible
    (Pereira : Universidad Tecnológica de Pereira, 2016) Bravo Montenegro, María Janeth ; Toro Ocampo, Eliana Mirledy
    El presente proyecto aborda la solución del Multi Depot Vehicle Routing Problem (MDVRP) involucrando el consumo de combustible, este problema es considerado NP-HARD, por lo cual se resuelve mediante un algoritmo híbrido que permite minimizar los costos de distancia y consumo de combustible, en un tiempo computacional razonable. La agrupación de clientes y asignación a los depósitos se realiza aplicando dos procedimientos con el fin de conformar la población inicial, el primer procedimiento es asignar primero y rutear después utilizando elipses, el segundo es rutear primero y asignar después solucionando el Traveling Salesman Problem (TSP) para los clientes. Las rutas se programan y optimizan utilizando algoritmos genéticos. El rendimiento del algoritmo se evalúa realizando diferentes corridas y comparando los resultados obtenidos con las instancias diseñadas por Cordeau encontradas en Networking and Emerging Optimization (NEO), con el fin de aplicar la metodología de solución al caso de prueba de distribución de productos lácteos de una empresa de San Juan de Pasto, donde se considera además de la distancia el costo de combustible. Con la presente investigación se espera contribuir a la optimización de distribución de productos cuando se dispone de múltiples depósitos y adoptar mecanismos que permitan reducir el consumo de combustible con el fin de lograr mejorar las soluciones de forma integral.
  • Documento
    Revisión del estado del arte del problema de enrutamiento de vehículos con restricción de capacidad, CVRP, involucrado en la administración de la cadena de suministro
    (Pereira : Universidad Tecnológica de Pereira, 2014) Castro Basto, Sandra Milena
    En este capítulo trataremos de dar respuesta a por qué el transporte se convierte en un punto clave para el correcto funcionamiento de la cadena de suministro, ya que está presente y sirve para conectar procesos tanto internos como externos de la administración de la cadena de suministro.
  • Documento
    Revisión del estado del arte del problema de ruteo abierto (OVRP)
    (Pereira : Universidad Tecnológica de Pereira, 2017) Tangarife Álvarez, Anderson Felipe ; Toro Ocampo, Eliana Mirledy
    En este documento se lleva a cabo una revisión bibliográfica del estado del arte del problema de ruteo abierto (OVRP; Open Vehicle Routing Problem). Se realiza la definición del problema, una clasificación de sus variantes y de los artículos e investigaciones publicadas en las bibliotecas virtuales: Scopus, Science Direct y Google Scholar acerca del tema. Además, se plantean los modelos de solución utilizados por los autores, las aplicaciones del estudio y las tendencias o futuras líneas de investigación. El OVRP es un problema de planificación de rutas de transporte, generalización del Problema del Agente Viajero muy conocido y ampliamente estudiado, tiene como característica diferenciadora que los vehículos una vez finalizadas las entregas correspondientes no están obligados a regresar al punto de partida o depósito. La revisión observa lo publicado hasta mayo del año 2017.
  • Documento
    Solución al problema de ruteo de vehículos con capacidad limitada "CVRP" a través de la heurística de barrido y la implementación del algoritmo genético de Chu-beasley
    (Pereira : Universidad Tecnológica de Pereira, 2013) Orrego Cardozo, Juan Pablo
    Los problemas de ruteo de vehículos han sido objeto de investigación intensiva por más de 50 años, debido al gran interés científico que éstos tienen por ser considerados NP-completos y donde algunas instancias Euclidianas con 75 nodos aún no han sido resueltas hasta su óptimo (Prins, Christian (2004)). Por otra parte, se debe a su importancia cómo modelo de optimización, en cantidades de campos de aplicación, como son, transporte, logística, comunicaciones, manufactura, militar, entre otros. El problema “tradicional” CVRP (por sus siglas en inglés Capacitated Vehicle Routing Problem) puede ser descrito en su forma más sencilla como una flota de vehículos con capacidades uniformes que tiene que satisfacer la demanda de un grupo de clientes a través de un conjunto de rutas que empiezan y terminan en un almacén común y que representan el menor costo posible, así como la identificación del orden de visita a los mismos (Gendreau et al. (2012)). Como consecuencia de los altos niveles actuales de congestión vehicular, de los fuertes consumos de energía de los vehículos de carga, así como del impacto negativo que estos últimos tienen en el medio ambiente como emisiones, accidentes, ruido y vibraciones; en los últimos años uno de los problemas que más ha interesado a la logística urbana “City Logistics” ha sido el de optimizar globalmente los sistemas de transporte, considerando los costos y beneficios de esquemas tanto públicos como privados. Estos conceptos de City Logistics, han sido implementados y son objeto de interés presentes en muchos modelos desarrollados recientemente para predecir y establecer sistemas inteligentes de transporte (Taniguchi y Thompson (2002)). Cómo caso particular se relacionan posteriormente todos los modelos generales y explícitos del VRP y sus variantes.