Examinando por Tema "Optimización combinatoria"
  • Documento
    Algoritmo búsqueda tabú aplicado al problema de la planeación de sistemas de distribución considerando ubicación y dimensionamiento de condensadores y reguladores de tensión
    (Pereira : Universidad Tecnológica de Pereira, 2014) Grajales Otalvaro, Alejandro
    El problema del planeamiento de sistemas primarios de distribución es de gran complejidad y puede ser resuelto empleando metodologías estáticas o dinámicas. Su modelamiento puede considerar redes radiales y enmalladas, reconductorización de líneas existentes, aumento de la capacidad de subestaciones existentes y determinación de la capacidad y localización de nuevas líneas y subestaciones. Muchos estudios de planeamiento de sistemas de distribución involucran equipos para control de perfiles de tensión y disminución de pérdidas de energía. Dichos equipos son utilizados tradicionalmente al final de la etapa de planeamiento y se emplean para corregir variables operativas del sistema y enmarcarlo dentro de las restricciones técnicas requeridas. El problema de ubicación y dimensionamiento de dichos equipos es complejo y actualmente, junto con el problema de planeamiento de sistemas de distribución, son temáticas de estudio a nivel mundial, donde cada día, diversos autores proponen nuevos modelos matemáticos y métodos de solución, buscando encontrar mejores respuestas técnicas y económicas. En este trabajo se presenta una metodología para resolver el problema de planeamiento de sistemas primarios de distribución integrado con el problema de ubicación y dimensionamiento de bancos de condensadores y reguladores de tensión. Para solucionar este problema se formula un modelo de tipo no lineal entero mixto, el cual tiene como objetivo la minimización de los costos de inversión más los costos de operación, sujeto a un conjunto de restricciones técnicas y operativas; para solucionarlo se emplea la técnica metaheurística Búsqueda Tabú. Esta técnica de optimización está integrada con un Algoritmo Genético de Chu-Beasley, el cual es utilizado sólo para ubicar y dimensionar los bancos de condensadores y reguladores de tensión en la configuración inicial. Para la evolución de la búsqueda del Algoritmo Búsqueda Tabú se han generado estructuras de vecindad basadas en algoritmos heurísticos donde se contemplan vecinos por cambio de calibre de los tramos de red, reconfiguración topológica y cambio en los valores de los bancos de condensadores y los reguladores de tensión.
  • Documento
    Application of Ant Colony Optimization to course timetabling problem
    (Pereira : Universidad Tecnológica de Pereira, 2008) Peñuela Meneses, César Augusto ; Franco Baquero, John Fredy ; Toro Ocampo, Eliana Mirledy
    Se presenta el problema de la programación óptima de horarios de clase, así como el modelo matemático que lo representa y la codificación empleada. Se muestra la aplicación de la técnica de optimización combinatorial Colonia de Hormigas en la solución del problema y se usa la metodología desarrollada en casos de prueba de la literatura especializada.
  • Documento
    Combinatorial optimization techniques applied to Sudoku¿s solution
    (Pereira : Universidad Tecnológica de Pereira, 2007) Franco Baquero, John Fredy ; Gómez Carmona, Oscar ; Gallego Rendón, Ramón Alfonso
    Se presenta el Sudoku como un problema de optimización combinatorial de única solución y se propone un modelo matemático que lo representa. Se aplican las técnicas de optimización combinatorial Búsqueda Tabú y Algoritmos Genéticos en varios casos de prueba.
  • Documento
    Diseño e implementación de un algoritmo para dar solución al problema de asignación de salones (Timetabling) usando el método de colonia de hormigas
    (Pereira : Universidad Tecnológica de Pereira, 2009) Gómez Toro, Jennifer Andrea ; Vanegas Castellanos, Juan David ; Zuluaga Gómez, Natalia
    En muy corto tiempo el software es posiblemente uno de los productos de la Ingeniería que más se ha transformado, evolucionando desde el software empírico, hasta llegar al desarrollo de aplicaciones bajo los principios y herramientas de la Ingeniería del software, aun así, cuando se ha tratado de mantener en regla dichos principios, aquellos encargados de su elaboración se han visto obligados a enfrentar una serie de problemas muy comunes gracias a la gran exigencia en la capacidad de resultados de los programas y a diferentes requerimientos que con el pasar del tiempo se vuelven aun más grandes debido al cambio de las condiciones de uso, instalación, plataformas, tiempos, hardware, etc. lo que aumenta su complejidad y con el transcurso de los días su obsolescencia. Gracias al rápido avance tecnológico de la información, la cantidad y la complejidad del software se ha acrecentado de una forma considerable, así como también han aumentado los requerimientos en su funcionalidad, confiabilidad y por lo tanto su seguridad, intentando con esto reconocer requisitos incompletos, ambiguos o contradictorios; de esta manera la calidad y la productividad se están transformando en las mayores preocupaciones para los desarrolladores del software. Uno de los problemas en los que la computación de alto desempeño puede mejorar los tiempos de ejecución así como también la forma de implementar un algoritmo determinado es la programación de clases con aulas y horarios adecuados a las necesidades de una institución educativa; problema al que se llamara de ahora en adelante Asignación de Aulas y Horarios, el cual se intentará resolver usando Colonia de Hormigas como metodología heurística para la búsqueda de soluciones. La Asignación de Aulas y Horarios consiste en relacionar un grupo de profesores a un grupo de materias dentro de un período de tiempo fijo, generalmente una semana, satisfaciendo un grupo de restricciones de diferente tipo; encontrar una solución de forma.
  • Documento
    Identificación de errores grandes en la estimación de estado usando búsqueda tabú
    (Pereira : Universidad Tecnológica de Pereira, 2007) Toro Ocampo, Eliana Mirledy ; Granada Echeverri, Mauricio ; Ruíz Florez, Hugo Andrés
    La estimación de estado es comúnmente desarrollada usando la técnica de los mínimos cuadrados ponderados WLS (por acrónimo en inglés). Sin embargo, se presentan dificultades en la identificación de mediciones erróneas, dado que no existe un proceso de verificación que permita tener certeza sobre la calidad de dichas mediciones. Por lo tanto, en este artículo se presenta una metodología que combina la técnica clásica con un método de optimización combinatorial para garantizar una mayor eficiencia en la detección de mediciones erróneas. Además se utiliza como criterio de observabilidad la teoría de puntos de apalancamiento.
  • Documento
    Identificación en Línea de Sistemas utilizando Algoritmos Genéticos
    (Pereira : Universidad Tecnológica de Pereira, 2015) Amariles Aroca, Jhon Alexander
    Los algoritmos genéticos son de las denominadas técnicas metaheurísticas de optimización, las cuales son útiles cuando el problema a resolver no es fácilmente desarrollable mediante técnicas de optimización exactas. Las técnicas metaheurísticas poseen mecanismos para escapar de soluciones óptimas locales, ayudando a encontrar de mejor forma un óptimo global, teniendo en cuenta que estas técnicas no lo garantizan. Los métodos tradicionales de búsqueda utilizan características del problema para determinar el siguiente punto, diferente de los métodos de búsqueda estocásticos, en los cuales el siguiente punto se determina a partir de reglas de muestreo y decisión estocástica. Los algoritmos genéticos manipulan una población de soluciones e implementan una “supervivencia del más adaptado” como estrategia de mejores soluciones. Esto provee un paralelismo implícito y explicito que permite la explotación de varias regiones prometedoras al mismo tiempo.
  • Documento
    Introducción al problema de enrutamiento de vehículos en la logística de distribución
    (Universidad Tecnológica de Pereira, 2020) Toro Ocampo, Eliana Mirledy ; Castañeda Londoño, John Fredy ; Gallego Rendón, Ramón Alfonso
    Este libro presenta un modelo matemático flexible y una metodología metaheurística que puede ser adaptada a diferentes variantes del problema de enrutamiento. Este se basa en el problema clásico del agente viajero, travel salesman problem (TSP), donde se necesita definir una ruta que visite todos los nodos una única vez. En algunas aplicaciones no se permite que la longitud de ruta exceda un límite de tiempo o de distancia, lo que hace necesaria la confección de varias trayectorias o ciclos para visitar todo el conjunto de clientes, esto configura el problema de múltiples agentes viajeros, multitravel salesman problem (M-TSP). En ambos problemas, el objetivo es visitar todos los clientes, minimizando la sumatoria de los arcos activos.
  • Documento
    Localización y ruteo de vehículos capacitado multi-objetivo con consideraciones de sostenibilidad
    (Pereira: Universidad Tecnológica de Pereira, 2020) Galindres Guancha, Luis Fernando ; Gallego Rendón, Ramón Alfonso
    En la actualidad las empresas, entidades gubernamentales, la comunidad academica y cientifi ca, enfocan su atención en el desarrollo sostenible. Uno de los sectores de mayor interés en este enfoque es la logística, especificamente el area de transporte. La inclusión de consideraciones de desarrollo sostenible implica cambiar la planeación, diseño y operación de sus procesos lo que impacta directamente en la e ficiencia y competitividad...
  • Documento
    Optimal two-dimensional packing with rotatable items using a hybrid algorithm of variable neighborhood search and simulated annealing
    (Pereira : Universidad Tecnológica de Pereira, 2009) Alvarez Martínez, David ; Toro Ocampo, Eliana Mirledy ; Gallego Rendón, Ramón Alfonso
    Los problemas de empaquetamiento tienen un amplio espectro de aplicación en ingeniería de producción, ya que muchos problemas requieren la ubicación de rectángulos en una hoja de material rectangular de mayor tamaño. Se presenta un modelo matemático del problema de empaquetamiento bidimensional permitiendo rotación de las piezas, donde el objetivo es minimizar el área desperdiciada, se utiliza una metaheurística híbrida, búsqueda en vecindario variable y recocido simulado. La eficiencia de la metodología propuesta es evaluada usando 50 casos de estudio, comparándose con dos técnicas presentadas en la literatura especializada que no consideran rotación de piezas, obteniendo resultados de excelente calidad.
  • Documento
    Optimización multiobjetivo para resolver el problema de ruteo sin retorno al depósito de inicio (OVRP)
    (Pereira : Universidad Tecnológica de Pereira, 2019) Pava García, Lisbeth Carolina ; Toro Ocampo, Eliana Mirledy
    La Planificación de ruta es una de las decisiones operacionales de las empresas de logística, transporte y distribución que tienen un alto impacto en la eficiencia y la calidad de los servicios. Hoy en día estos problemas tienen mayor importancia, y no sólo por razones económicas. La posibilidad de obtener soluciones de alta calidad tan pronto como sea posible con independencia de los operadores humanos no puede ser ignorada. La interacción humana puede fallar, retrasar respuestas o provocar errores irrecuperables. Por lo tanto, la disponibilidad de sistemas inteligentes que implementan efectivamente modelos operativos y soluciones adecuadas es una prioridad. Sin embargo, en profundidad se requiere el conocimiento de los modelos en los que han de basarse para tales sistemas. En el problema de ruteo de vehículos abiertos, Open Vehicle Routing Problem (OVRP), un vehículo no vuelve al depósito después de dar servicio el último cliente en una ruta. La descripción de esta variante del problema de rutas para vehículos estándar aparecido en la literatura de hace más de 20 años, pero solo recientemente atrajo la atención de los profesionales e investigadores.
  • Documento
    Ordenamiento óptimo usando el algoritmo recocido simulado y almacenamiento compacto aplicados a la solución de sistemas de ecuaciones lineales
    (Pereira : Universidad Tecnológica de Pereira, 2008) Arias Palacio, Jorge Mario ; González Hoyos, Julián David
    Gran número de fenómenos y procesos reales que se analizan en ingeniería son modelados a través de sistemas de ecuaciones lineales de gran tamaño, en cuyos casos, requieren de la intervención de un gran número de diferentes variables que, a su vez, se relacionan entre sí. En el caso específico del modelamiento de sistemas de potencia a gran escala, donde se analizan redes del orden de las centenas y hasta miles de barras, las matrices encargadas de almacenar los coeficientes que acompañan las variables del sistema, presentan en general, un gran número de elementos nulos. Esta característica es llamada dispersidad, la cual permite realizar cierto tipo de manipulaciones en cuanto al orden en que las variables serán procesadas y al almacenamiento computacional de la información. Debido a la característica dispersa de las matrices que intervienen en procesos eléctricos, es de vital importancia aprovechar de manera adecuada las ventajas que trae el hecho de tener que trabajar con pocos elementos no nulos. Como es sabido, no es eficiente almacenar elementos con valor igual a cero, ya que requiere de un gran espacio en memoria y de un exigente esfuerzo computacional innecesario. Por ejemplo, considere que un sistema eléctrico de 1000 barras tiene una matriz de admitancia nodal con el 85% de sus elementos iguales a cero, el cual es un valor normal de dispersidad. Si se deseara almacenar la totalidad de los elementos de la matriz, sería necesario guardar 1 millón de posiciones, lo cual contrasta con la aplicación de un esquema de almacenamiento, en donde sólo sería necesario almacenar 150 mil elementos más una información adicional que proporcione la ubicación de los mismos. Este tipo de manipulación ayuda no sólo a disminuir el espacio requerido en memoria, sino también a reducir el número de operaciones que deben ser realizadas, pues como se sabe, cualquier número multiplicado por cero es igual cero.
  • Documento
    Planeamiento de sistemas de distribución de energía eléctrica con generación distribuida utilizando búsqueda Tabú
    (Pereira : Universidad Tecnológica de Pereira, 2014) Santacruz Cabrera, Andrés Camilo ; Cañaveral Osorio, Christian
    El planeamiento de la expansión de los sistemas de distribución es de vital importancia para el análisis de sistemas eléctricos, pues permite encontrar la topología más adecuada y económica que se adapte a criterios técnicos y operativos, a través de la utilización de diversos modelos y técnicas matemáticas exactas y no exactas. Cada vez el análisis de dichos sistemas se vuelve más complejo, pues se deben incorporar una mayor cantidad de variables con el fin de acercarse más a lo que sucede en los sistemas reales: aspectos como la coordinación de protecciones, la necesidad de utilización de energías limpias para la generación de energía, los impactos en los niveles de confiabilidad y regulación de tensión en la red, la contribución en los niveles de pérdidas de potencia, entre otras situaciones pueden ser consideradas en el análisis, según sea la finalidad del modelo de planeamiento.
  • Documento
    Planeamiento de sistemas de distribución usando búsqueda Tabú
    (Pereira : Universidad Tecnológica de Pereira, 2007) Franco Baquero, John Fredy ; Gallego Rendón, Ramón Alfonso ; Pérez Hernández, Lucas Paúl
    El problema del planeamiento de sistemas de distribución de energía eléctrica trata la adecuada expansión del sistema, para satisfacer la demanda de los usuarios, cumpliendo con los límites técnicos y operativos, a un mínimo costo. En este artículo se presenta un modelo no lineal resuelto usando la metodología de búsqueda tabú. La metodología propuesta fue verificada con un sistema de prueba de 50 nodos tomado de literatura especializada, el cual presentó excelentes resultados.
  • Documento
    Planeamiento de subestaciones y alimentadores en sistemas de distribución usando programación entera
    (Pereira : Universidad Tecnológica de Pereira, 2005) Hincapié Isaza, Ricardo Alberto ; Granada Echeverri, Mauricio ; Gallego Rendón, Ramón Alfonso
    Se presenta una metodología matemática para resolver el problema del planeamiento de redes de distribución que incluye la localización y dimensionamiento de nuevas subestaciones y redimensionamiento de las existentes, reconductorización, de alimentadores existentes y enrutamiento y selección de conductor de los alimentadores nuevos. Para la solución del modelo matemático se emplea un algoritmo de Branch and Bound. Este modelo es del tipo Lineal Entero Mixto (PLEM), y es de difícil solución por su carácter combinatorial, debido a su gran complejidad computacional. Para su comprobación se emplea un sistema de la literatura especializada, obteniéndose resultados de alta calidad.
  • Documento
    Planteamiento multiobjetivo para resolver el problema de ruteo de vehículos con restricciones de capacidad
    (Pereira : Universidad Tecnológica de Pereira, 2017) Quiñones Saavedra, Lilibeth ; Toro Ocampo, Eliana Mirledy
    Desde los inicios de la conformación de países y ciudades, el mundo exige de diferentes rutas para la movilización de las personas, ya que esto hace parte de la vida cotidiana. Pero, a medida en que evoluciona la sociedad, la forma de movilización es cada vez más difícil, especialmente cuando se trata de llegar a un lugar en el menor tiempo posible o a un menor costo. Sin embargo, las personas en la mayoría de los casos construyen rutas para desplazarse de manera intuitiva. A pesar de esto, se siguen presentando inconvenientes, ya que de esta manera no se logran resultados efectivos. Ahora bien, las diferentes empresas reflejan una necesidad de conocer la manera de resolver problemas relacionados con el trasporte, es por ello que el presente proyecto radica en la documentación de planteamientos multiobjetivos para solución del problema de ruteo de vehículos con restricción de capacidad.
  • Documento
    Programación de turnos para los tecnólogos en radiología e imágenes diagnósticas en las sedes de Cartago de la empresa Radiólogos Asociados S.A.S usando algoritmos de inteligencia artificial
    (Pereira : Universidad Tecnológica de Pereira, 2013) Mazuera Echeverri, Cristina ; Henao Bedoya, Yenifer
    La distribución, asignación u organización de recursos sean estos tangibles o intangibles, en cualquier institución, es indispensable para un adecuado funcionamiento. Esto muchas veces se convierte en un inconveniente por la demanda de tiempo y procesamiento que requiere establecer dicha distribución, de forma óptima que satisfaga las necesidades de la institución sin implicar nuevos costos en dinero, tiempo, recursos humanos o materiales de cualquier otra índole. Este es el caso de la empresa de Radiólogos Asociados SAS, donde el proceso de asignación de horarios y recursos como salas, para los tecnólogos se hace de forma manual, es decir no existe un sistema o aplicativo que permita generar dicha asignación. Es entonces este el objetivo del actual proyecto de grado, implementar una solución automatizada para la asignación de horarios, utilizando para ello métodos de inteligencia artificial. para hallar una solución a este problema se implementó un hibrido entre el algoritmo genético y enfriamiento simulado, decisión basada en resultados de investigaciones previas similares a este tipo de problemas, estudios que arrojaron buenos resultados y soluciones óptimas sin indicar que fueran las mejores, aun así se debe tener en cuenta que cada institución tiene necesidades y requerimientos propios que son independientes y diferentes a las de otras instituciones, razón por la cual una buena solución depende de los requisitos que se deban satisfacer de la institución en particular.
  • 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
    Solución al problema de asignación de conductores y vehículos en sistemas de transporte público masivo de pasajeros mediante la implementación de una técnica metaheurística de optimización
    (Pereira: Universidad Tecnológica de Pereira, 2021) Bolaños, Rubén Iván ; Granada Echeverri, Mauricio
    La presente investigación está enfocada en la sofisticación de la planeación de los sistemas ´ de transporte público de pasajeros operado con buses de transito ligero, denominados BRT, ´ específicamente se analizan y se resuelven dos problemas propios de la planeación operativa, los cuales se conocen como Programación de Vehículos (Vehicle Scheduling Problem) y Programación de Conductores (Crew Scheduling Problem), ambos problemas son catalogados ´ como problemas de difícil solución y se clasifican en la literatura especializada como problemas ´ de Tipo NP- Hard...
  • 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.
  • Documento
    Solución al problema de ruteo de vehículos con restricciones de capacidad considerando demanda estocástica - CVRPSD
    (Pereira : Universidad Tecnológica de Pereira, 2020) Mena Ríos, Andrés Mauricio ; Toro Ocampo, Eliana Mirledy
    Partiendo por la comprensión de diferentes modelos del problema de ruteo vehículos, entre los cuales destaca el problema del agente viajero (TSP) y el problema de ruteo de vehículos con restricciones de capacidad (CVRP), el presente proyecto busca crear múltiples instancias del CVRP a partir de casos de prueba propuestos por diferentes autores, eligiendo de forma aleatoria un cliente para cada escenario, y variando su demanda siguiendo una distribución de probabilidad Poisson, para que este dato ingrese como variable de entrada ya conocida a un modelo matemático de solución flexible y exacto, con el fin de dar solución al problema de ruteo de vehículos con restricciones de capacidad considerando demanda estocástica (CVRPSD), con el propósito de que pueda ser replicado en el futuro en ambientes organizacionales para el mejoramiento de procesos logísticos reales...