Browsing by Subject "Metaheurística"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Diseño de metaheurística y modelo matemático para asignación de horarios en el programa de ingeniería industrial en la PUJ Cali
    (Pontificia Universidad Javeriana Cali, 2024) Hernández Rendón, Felipe; Vidal Duque, Nicolás; Morillo Torres, Daniel
    La asignación de horarios (Timetabling) es un problema combinatorio, desafiante, laborioso y repetitivo en distintos sectores; este trata de ordenar una cantidad finita de personal, espacios o recursos a bloques horarios. En el University Course Timetabling (UCT) los cursos deben tomar lugar y distribuir las sesiones académicas evitando cruces lógicos como: un profesor no puede dictar dos materias a la misma hora, un estudiante no puede asistir a dos clases simultáneamente, entre otros. Las universidades e instituciones educativas de nivel superior en Colombia optan por resolver estos problemas de manera manual mediante la prueba y error. Debido a la volátil calidad de las soluciones y complejidad de tipo NP-Hard, la metodología actual en las instituciones usualmente resulta en soluciones lejanas al óptimo. Para abordar este problema en del Programa de Ingeniería industrial en la PUJ como caso aplicado, se diseñó un algoritmo de dos etapas: una metaheurística de tipo búsqueda local iterativa y un método de inicialización a partir de un modelo de programación lineal entera-mixta. Mediante un diseño de experimentos Taguchi se establecieron los parámetros para optimizar el desempeño del algoritmo. Como objetivo se maximizaron las preferencias cumplidas por profesor y la reducción de cruces entre materias que se pueden adelantar o atrasar, a su vez que se eliminaron conflictos entre asignaturas que comparten semestre, profesor y salón. Como consecuencia de la implementación, se redujo en un 99,37% el tiempo asociado al proceso de asignación de horarios semestral, como también un aumento del 14,8% respecto a las preferencias de los profesores. De esta forma la institución obtiene una mayor eficiencia implementando herramientas de automatización y optimización al mismo tiempo que se consideran factores sociales como las preferencias.
  • Thumbnail Image
    Item
    Diseño de un modelo ecológico de optimización aplicado al ruteo de vehículos con ventanas de tiempo
    (Pontificia Universidad Javeriana Cali, 2020) González García, Valentina; Gutiérrez Padilla, María Victoria; Mendoza Torres, Jhoan Manuel; Morillo Torres, Daniel
    El problema de enrutamiento de vehículos es conocido en la literatura académica como Vehicle Routing Problem (VRP), y es uno de los problemas de optimización combinatoria más importantes. El objetivo es determinar el conjunto óptimo de rutas que debe realizar una flota de vehículos para atender a un conjunto determinado de clientes, de forma que se minimicen los costos de transporte. Una de las variantes del VRP con mayor relevancia en la actualidad es el Pollution Routing Problem (PRP) que considera la minimización de los costos de transporte y la reducción de emisiones contaminantes. El presente proyecto propone el diseño de un modelo de programación lineal entera-mixta y una metaheurística de Búsqueda Tabú para la solución del Pollution Routing Problem with Time Windows and Speed Decisions. Para la validación de los diseños propuestos se adaptaron las instancias de Kramer, et all. y se compararon los resultados obtenidos con el algoritmo del vecino más cercano planteado como solución actual. Mediante la implementación se obtuvieron soluciones óptimas para instancias pequeñas (de 10 y 15 clientes) por medio del del modelo matemático, mejorando en promedio, un 62,08% los costos totales y un 81,23% las emisiones de CO2. Mientras que la Búsqueda Tabú demostró eficiencia en relación con los resultados obtenidos y el tiempo de cómputo para las instancias de todos los tamaños, obteniendo un porcentaje de mejora promedio para los costos totales de 66,04% y de 90,97% para las emisiones de CO2.
  • Thumbnail Image
    Item
    Diseño de una metaheurística basada en el algoritmo genético para la solución del problema de intercambio de riñones en Estados Unidos
    (Pontificia Universidad Javeriana Cali, 2021) Ortega Bedoya, Juan Felipe; Otero Villamarín, Juan Felipe; Patiño Espinosa, Alejandro; Solano Ossa, José David; Morillo Torres, Daniel
    En los Estados Unidos, las complicaciones renales ocupan la octava posición como causa de muerte más frecuente, generando listas de espera que se acercan a las 100,000 personas, con solo alrededor de 25,000 accediendo a trasplantes renales. Ante la dificultad de suplir la demanda total de riñones necesarios, han surgido programas de intercambio renal que involucran donantes, receptores y altruistas, buscando establecer intercambios con cadenas o ciclos de longitud reducida por consideraciones logísticas. Frente al aumento de estos intercambios y programas tanto en Estados Unidos como en Europa, se ha desarrollado una metaheurística basada en el algoritmo genético. Esta estrategia ha sido concebida para abordar casos de prueba de mayor envergadura, superando las limitaciones de los modelos matemáticos convencionales. La aplicación de esta metaheurística proporciona una solución eficaz y escalable, mejorando la asignación de riñones en un contexto de alta demanda y limitaciones logísticas, ofreciendo respuestas a desafíos previamente considerados inabordables.