Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas

Equation Chapter 1 Section 1 Trabajo Fin de Grado Ingeniería de Organización Industrial Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Autor: Luis Alcayde Natera Tutor: Jose Manuel Molina Pariente Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 iii Trabajo Fin de Grado Ingeniería de Organización Industrial Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Autor: Luis Alcayde Natera Tutor: Jose Manuel Molina Pariente Profesor Permanente Laboral Dpto. Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2024 v Proyecto Fin de Carrera: Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Autor: Luis Alcayde Natera Tutor: Jose Manuel Molina Pariente El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2024 El Secretario del Tribunal vii Resumen El proyecto "Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas" se centra en abordar uno de los desafíos cruciales en el ámbito hospitalario: la asignación eficiente de pacientes a quirófanos y días. Para abordar este problema, el proyecto propone el uso de algoritmos de colonia de hormigas, una técnica de optimización inspirada en el comportamiento de las hormigas reales en la búsqueda de comida. Estos algoritmos son capaces de encontrar mejores soluciones explorando múltiples posibilidades y adaptándose dinámicamente a cambios en el entorno. El proyecto se desarrolla en Python, aprovechando las capacidades de este lenguaje de programación para implementar y comparar diferentes variantes de algoritmos de colonia de hormigas. Se considera como métrica de rendimiento la equidad en la distribución de la carga de trabajo entre los cirujanos. Además, se llevan a cabo experimentos computacionales basados en configuraciones de recursos quirúrgicos y niveles de saturación del sistema, con el objetivo de evaluar el rendimiento de los algoritmos propuestos en una variedad de escenarios reales. Se generan instancias para representar diferentes situaciones operativas y se analizan los resultados obtenidos para determinar el rendimiento de cada algoritmo en la optimización quirúrgica. Al final del proyecto, se realiza una comparación exhaustiva de las variantes de algoritmos propuestos, evaluando su capacidad para equilibrar la carga de trabajo de los cirujanos y mejorar la eficiencia operativa del sistema quirúrgico. Los hallazgos y conclusiones de este estudio proporcionarán información valiosa para la toma de decisiones en la asignación de los quirófanos, contribuyendo así a una atención médica más eficaz y equilibrada en términos de carga de trabajo. ix Índice Resumen vii Índice ix Índice de Tablas xi Índice de Figuras xii 1 Introducción 1 Objetivos 3 Sumario 4 2 Descripción del problema 5 Optimización de la asignación y secuenciación de cirugías a quirófanos y días y recursos quirúrgicos para equilibrar la carga de trabajo de los cirujanos en Hospitales 5 Definición del problema 5 3 Metodología de resolución 7 Decoding 7 3.1.1 Best Fit 8 3.1.2 Next Fit 9 3.1.3 First Fit 10 Secuencia de pacientes asignados 11 Algoritmos de optimización 13 3.3.1 Ant Colony Optimization 13 3.3.2 Búsqueda Local 16 4 Análisis computacional 15 Herramienta utilizada 15 4.1.1 Librerías 15 4.1.2 Jerarquía del Código 16 Datos de entrada a la optimización 16 4.2.1 Generación de pacientes 17 4.2.2 Generación de tiempo estimado de cirugía 17 4.2.3 Elegibilidad de las cirugías 18 4.2.4 Generación de datos de los cirujanos 18 Calibración de los parámetros de los algoritmos 19 4.3.1 Tiempo de computación 19 4.3.2 Tamaño de la vecindad en la búsqueda local 20 4.3.3 Resultados de la calibración 20 5 Resultados 22 Escenario 1: 3 quirófanos 22 Escenario 2: 9 quirófanos 26 Escenario 3: Ampliación del tiempo de computación 31 Conclusiones 36 Referencias 39 Anexos 41 1 1 INTRODUCCIÓN l ámbito de la planificación y programación de cirugías en un sistema hospitalario enfrenta desafíos y problemas de gran complejidad, como la disponibilidad limitada de recursos (quirófanos, cirujanos…), la gestión de la demanda, ya que no todos los cirujanos pueden operar a todos los pacientes, y la administración del tiempo, ya que es difícil predecir la duración exacta de cada cirugía. En la actualidad, muchos investigadores enfocan su trabajo en el desarrollo de herramientas y sistemas que apoyen y faciliten la atención quirúrgica, con el objetivo de optimizar la distribución de trabajo entre los cirujanos y mejorar la eficiencia operativa de los hospitales [1]. El marco teórico de este trabajo se estructura en torno a dos niveles de decisión fundamentales [2]: el nivel táctico y el nivel operativo. En el nivel táctico, se enfoca en la distribución de horas de trabajo entre los cirujanos, asegurando que cada uno tenga una carga de trabajo equilibrada y que se respeten todas las regulaciones laborales, evitando casos de sobreexplotación y garantizando el cumplimiento de los horarios establecidos. Este nivel táctico es crucial para planificar de manera anticipada y establecer un marco de trabajo que asegure la disponibilidad y eficiencia de los recursos humanos en el entorno hospitalario. Por otro lado, el nivel operativo se encarga de la programación quirúrgica detallada y específica. En este nivel, se determina el quirófano y el día en que se realizará cada cirugía, y se define la secuencia de cirugías para cada quirófano dentro de cada día del horizonte de planificación, asegurando una asignación adecuada de recursos y tiempos para minimizar el desequilibrio entre cargas de trabajo de los cirujanos En conjunto, estos niveles de decisión forman un marco integral que busca equilibrar la carga de trabajo de los cirujanos, mejorar la gestión de los recursos y elevar la calidad del servicio hospitalario, abordando tanto la planificación estratégica como la operativa de manera coherente y eficiente. El principal problema en los entornos quirúrgicos radica en la distribución desigual de la carga de trabajo entre los cirujanos, lo que puede llevar a una gestión ineficiente de los recursos y afectar a la calidad del servicio prestado a los pacientes [3]. Por ello, es crucial desarrollar métodos que permitan una distribución equitativa del trabajo quirúrgico, garantizando al mismo tiempo la máxima eficiencia y la calidad del servicio y contribuyendo a un ambiente de trabajo más sostenible y a la satisfacción del personal médico. El presente proyecto se centra en la optimización de la carga de trabajo de los cirujanos mediante el uso de algoritmos de colonia de hormigas. Los algoritmos de colonia de hormigas son heurísticas eficaces para explorar soluciones en espacios de búsqueda complejos y adaptarse a cambios en condiciones y restricciones del problema, sin necesidad de una formulación matemática precisa. Además, ofrecen robustez ante problemas no lineales o no convexos, explorando soluciones prometedoras que pueden ser subóptimas según criterios estrictos pero satisfactorias en la práctica. Estos algoritmos, inspirados en el comportamiento de las hormigas en la naturaleza, aprovechan la capacidad de E Introducción 2 2 estos insectos para encontrar las rutas más eficientes a través de la cooperación y la comunicación indirecta mediante feromonas. Este enfoque ha demostrado ser altamente eficaz en la resolución de problemas complejos de distribución y secuenciación en diversos campos, y su aplicación en el ámbito quirúrgico presenta un gran potencial para mejorar la eficiencia operativa. La utilización de algoritmos de colonia de hormigas permitirá diseñar un sistema de asignación que distribuya las cirugías de manera equitativa y eficiente, teniendo en cuenta factores como la disponibilidad de los cirujanos y quirófanos, la elegibilidad de los pacientes y duración de las intervenciones, y otros recursos hospitalarios necesarios. La investigación se estructura en varias fases. En primer lugar, se diseñarán y adaptarán algoritmos de colonia de hormigas específicos para el problema de la optimización de la carga de trabajo en entornos quirúrgicos, con el objetivo de encontrar soluciones óptimas para la distribución de las tareas quirúrgicas. Posteriormente, se validarán estos algoritmos utilizando datos que representen escenarios reales en un entorno hospitalario. Estos datos incluirán información sobre la disponibilidad de los cirujanos, la duración y la urgencia de las cirugías, y otros factores relevantes que puedan afectar a la distribución de la carga de trabajo. Finalmente, se evaluarán las soluciones obtenidas mediante un análisis computacional detallado, considerando diferentes escenarios y condiciones operativas. Este análisis permitirá determinar el rendimiento de los algoritmos propuestos en la optimización de la carga de trabajo de los cirujanos, contribuyendo así a mejorar la gestión de las cirugías en hospitales. Una distribución eficiente de las tareas quirúrgicas asegura que los cirujanos estén asignados adecuadamente según su disponibilidad y los pacientes que tenga asignados. La planificación de cirugías en un entorno hospitalario presenta varios desafíos específicos que deben ser abordados para garantizar una operación eficiente y de alta calidad. En primer lugar, la diversidad y complejidad de las cirugías representan un gran reto. Las cirugías varían ampliamente en términos de duración, complejidad y requisitos específicos. Algunas cirugías pueden requerir equipos especializados o configuraciones particulares del quirófano, lo que añade una capa adicional de complejidad a la planificación. Otro desafío crítico es la disponibilidad y capacidades del personal médico. La asignación debe considerar la disponibilidad de cirujanos y los pacientes que tiene cada uno asignado para intervenir. Cada cirujano tiene un límite en la cantidad de horas que puede trabajar, y es crucial respetar estas restricciones para conseguir una asignación y secuenciación de cirugías a quirófanos y días adecuada. Además, los cirujanos poseen diferentes niveles de experiencia y competencias en ciertos tipos de procedimientos, lo que debe ser tomado en cuenta al asignar las cirugías, lo cual no aplica a este proyecto, ya que, como se ha explicado anteriormente en este apartado, los cirujanos ya tienen asignados los pacientes e intervenciones a realizar. Cabe destacar que, en la mayoría de los casos, la asignación de los pacientes a los cirujanos suele realizarse en función del nivel de experiencia y competencias específicas de cada cirujano. La combinación de estos desafíos requiere un enfoque meticuloso y bien estructurado para la asignación y secuenciación de cirugías a quirófanos y días. La implementación de técnicas avanzadas de optimización y 3 3 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas algoritmos metaheurísticos, como los Algoritmos de Colonia de Hormigas (ACO) y la Búsqueda Local Iterada (ILS), puede ofrecer soluciones robustas y eficientes para gestionar estos desafíos. Estas técnicas permiten manejar la complejidad y variabilidad del entorno hospitalario, asegurando que las cirugías se asignen de manera óptima, los recursos se utilicen eficientemente y los cirujanos no se sobrecarguen de trabajo. En resumen, el objetivo de este proyecto es desarrollar y aplicar nuevas estrategias de optimización basadas en algoritmos de colonia de hormigas para equilibrar la carga de trabajo de los cirujanos en entornos hospitalarios. Se busca contribuir al avance del conocimiento en este campo y proporcionar herramientas efectivas para la toma de decisiones en la planificación de cirugías. Objetivos El principal objetivo del presente proyecto es la optimización de la carga de trabajo de los cirujanos mediante el uso de algoritmos de colonia de hormigas. Esta optimización se llevará a cabo poniendo el foco en la distribución y secuenciación de las intervenciones quirúrgicas, asegurando una asignación eficiente y equilibrada de las intervenciones de cada cirujano disponible. Para ello, se seguirán los siguientes pasos: - Diseño y adaptación de algoritmos de colonia de hormigas: Se desarrollarán algoritmos específicos basados en la técnica de colonia de hormigas, así como metaheurísticas a partir de otras ya existentes como la Búsqueda Local Iterada, combinándolas y adaptándolas a las particularidades del entorno quirúrgico para lograr el mejor resultado en la resolución del problema y una distribución óptima de las tareas. - Implementación y resolución: Se implementarán los algoritmos diseñados utilizando un lenguaje de programación adecuado, como Python, y se resolverán una batería de problemas de gestión de listas de esperas quirúrgicas para evaluar su desempeño en condiciones cercanas a la realidad hospitalaria. - Validación con datos reales: Los algoritmos serán validados utilizando datos generados de pacientes y recursos usando como referencia el artículo [4], con el objetivo de asegurar que las soluciones propuestas sean aplicables y efectivas en un entorno práctico. - Evaluación de resultados: Se analizarán los resultados obtenidos mediante un análisis computacional, y posteriormente evaluando los resultados obtenidos de cada variante del algoritmo, comparándolos entre ellos, de forma que busquemos cuál de ellas funciona mejor y ha conseguido los mejores resultados. Principalmente, los valores a comparar son el valor de la función objetivo, que se comparará mediante la técnica ARPD (referencia), el número de iteraciones realizadas por cada algoritmo dentro del tiempo de ejecución, y el número de veces que es capaz cada algoritmo de mejorar la solución global. Estos pasos permitirán desarrollar una herramienta robusta y eficaz para la distribución equilibrada de las cirugías, equilibrando la carga de trabajo de los cirujanos. Introducción 4 4 Sumario La memoria se compone de un total de 5 capítulos y 9 anexos. A continuación, se realiza un resumen de sobre qué trata cada capítulo: 1. Introducción: Se introduce el proyecto, se expone el problema a resolver junto con los objetivos planteados, y se detallan los pasos seguidos para alcanzar estos objetivos. 2. Descripción del problema: Se proporciona una descripción detallada del problema, incluyendo las restricciones que lo delimitan, las variables involucradas y la función objetivo que se busca minimizar. Además, se presenta el entorno específico sobre el cual se basa el problema. 3. Metodología de resolución: Se explica el método utilizado para construir la solución, detallando su estructura y presentando las posibilidades consideradas para la optimización del problema. Se definen los algoritmos y metaheurísticas empleadas en este proceso. 4. Desarrollo de algoritmos aproximados para la resolución del problema: Se enfoca en el desarrollo específico de los algoritmos diseñados para abordar el problema de gestión de equilibrado de la carga de trabajo de los cirujanos en un sistema hospitalario. 5. Análisis computacional: Se describen los escenarios generados para el análisis. Se detalla la generación de datos de entrada y la calibración de parámetros necesaria para asegurar el correcto funcionamiento de los algoritmos implementados. 6. Resultados: Se presentan los resultados obtenidos del análisis computacional realizado y se realiza un análisis detallado para determinar si se logró resolver satisfactoriamente el problema planteado. 7. Conclusiones: Se resumen las conclusiones derivadas del análisis realizado en el capítulo anterior y se proponen posibles áreas de mejora para investigaciones futuras. 8. Anexos: Incluye los códigos desarrollados en lenguaje Python, abarcando tanto la implementación de los algoritmos como el decoding necesario para optimizar la asignación de pacientes. 5 2 DESCRIPCIÓN DEL PROBLEMA n el ámbito hospitalario, la gestión eficiente de los recursos quirúrgicos es un desafío de gran importancia. La adecuada asignación de los pacientes a los quirófanos y días no solo afecta la eficiencia operativa de un hospital, sino que también tiene un impacto directo en la sostenibilidad de un ambiente de trabajo y a la satisfacción del personal médico. Los hospitales se enfrentan a la necesidad de equilibrar la carga de trabajo de los cirujanos y optimizar el uso de los quirófanos y otros recursos médicos disponibles. Optimización de la asignación y secuenciación de cirugías a quirófanos y días y recursos quirúrgicos para equilibrar la carga de trabajo de los cirujanos en Hospitales Una asignación inadecuada de cirugías puede llevar a una serie de problemas significativos, como el desequilibrio en la carga de trabajo de los cirujanos y el uso ineficiente de quirófanos. Esto no solo afecta la calidad del servicio ofrecido, sino que también puede incrementar los costes operativos y reducir la eficiencia general del hospital. Definición del problema El objetivo principal es desarrollar un sistema de asignación y secuenciación de cirugías a quirófanos y días que equilibre la carga de trabajo de los cirujanos. Esto incluye minimizar el tiempo en el que los quirófanos están inactivos y evitar el desequilibrio de la carga de trabajo de los cirujanos en la realización de intervenciones, asegurando al mismo tiempo que se cumplan todas las restricciones establecidas para el problema. Un equilibrio adecuado también contribuye a un ambiente de trabajo más sostenible y a la satisfacción del personal médico[5]. El problema se enfoca en la asignación y programación de las cirugías de los pacientes a quirófanos y días, respetando las restricciones y prioridades establecidas. Los pacientes deben ser asignados a un quirófano y un día determinado, manteniendo un equilibrio en la carga de trabajo de los cirujanos, definido como la cantidad de pacientes operados por cada cirujano en el horizonte temporal del problema. Las actividades que componen el proceso quirúrgico se centran, principalmente, en la intervención. Esta actividad requiere diferentes tipos de recursos, tales como cirujanos y quirófanos. La correcta asignación de los pacientes a estos recursos es crucial para asegurar que el proceso quirúrgico se realice de manera eficiente. Para garantizar un equilibrio en la carga de trabajo de los cirujanos, es fundamental distribuir las intervenciones de manera equitativa entre los cirujanos. Esto implica que ningún cirujano debe ser asignado a más procedimientos de los que puede gestionar de manera eficiente, y se debe considerar la disponibilidad de cada E Descripción del problema 6 6 profesional. El problema de optimización de la carga de trabajo de los cirujanos considera varios conjuntos e índices clave. El conjunto H representa los periodos de tiempo dentro del horizonte de planificación para los recursos perioperatorios. El conjunto I incluye a los pacientes (o cirugías) en la lista de espera, indicando que hay una lista de espera de I intervenciones. El conjunto J se refiere a las salas de operaciones, también conocidas como quirófanos, las cuales son las mismas mencionadas anteriormente. El conjunto S agrupa a los cirujanos disponibles. Los parámetros del problema incluyen la capacidad regular de una sala de operaciones 𝒓𝒋𝒉 y de los cirujanos 𝒂𝒔𝒉 en el día h (en minutos), el número de salas de operaciones en las que un cirujano puede operar 𝒖𝒔, el cirujano asignado a cada paciente 𝜸𝒊, las fechas a partir de las cuales y hasta las cuales se puede realizar la cirugía 𝒓𝒅𝒊 y 𝒅𝒊 respectivamente, el parámetro binario 𝜹𝒊𝒋𝒉 , que representa la elegibilidad de las cirugías, que indica si una cirugía puede realizarse en una sala en un día específico, y el tiempo esperado de cada cirugía 𝒕𝒊. Aunque estos parámetros no se utilizan directamente en el modelo final, proporcionan una base teórica para la descripción y comprensión del problema. Existen varias restricciones que deben ser respetadas, tales como la disponibilidad de cirujanos, no pudiendo operar un cirujano más tiempo del establecido; la capacidad de los quirófanos, no pudiéndose realizar un número de intervenciones que sobrepase el tiempo disponible cada día por quirófano y la elegibilidad de los pacientes para ser asignados a los quirófanos y días. Además, cada intervención debe ser realizada después de la 𝒓𝒅𝒊 y antes de la 𝒅𝒊. Es importante también asegurarse de que ningún cirujano tenga asignada más de una intervención simultáneamente, es decir, cada cirujano solo podrá operar a un paciente en un quirófano al mismo tiempo. Este enfoque no solo mejora los resultados clínicos, sino que también contribuye a una mejor gestión de los recursos hospitalarios. 7 7 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas 3 METODOLOGÍA DE RESOLUCIÓN l capítulo 3 contiene la definición de los algoritmos que se aplican en el proyecto realizado para la optimización quirúrgica de forma que se equilibre la carga de trabajo de los cirujanos, explicando la forma en la que se han aplicado al problema en el que se centra el proyecto. También se explica el código creado en el decoding, el cual lleva a cabo la correcta asignación de los pacientes en la lista de espera a los días, quirófanos y cirujanos correspondientes evitando incompatibilidades. En cuanto al algoritmo de optimización, este trabajo se centra en el ACO, una metaheurística introducida por primera vez en 1992 por Marco Dorigo [6]. Este tipo de algoritmos se inspiran en el comportamiento de las colonias de hormigas, como sugiere su nombre, y forman parte del ámbito de los algoritmos basados en el comportamiento de enjambres ("swarm intelligence"). Además, en algunos casos, se ha implementado una Búsqueda Local Iterada (Iterated Local Search) como método para escapar de los óptimos locales. En cuanto al decoding, se aplican varias estrategias, Best Fit, Next Fit y First Fit, siendo éstas unas de las estrategias más comunes para problemas de asignación [7]. El objetivo es comparar cada algoritmo desarrollado en este trabajo y ver cuál de ellos ofrece mejores resultados en función de un número de iteraciones establecido para realizar el análisis computacional. La implementación considera la disponibilidad de cirujanos y quirófanos, además de la elegibilidad de estos últimos para albergar diferentes tipos de operaciones, optimizando la programación de las cirugías para equilibrar la carga de trabajo de los cirujanos. Decoding En el presente proyecto, además de realizar la programación de los algoritmos utilizados y de la creación de los datos de entrada, se ha desarrollado el código que lleva a cabo la asignación de los pacientes que contiene la lista de espera a los quirófanos y días, para concluir con el cálculo de la función objetivo. El decoding es parte del algoritmo, además parte fundamental, ya que es el proceso mediante el cual se interpreta la solución generada por el algoritmo y se transforma en una secuencia de asignación específica que resulta en el un valor de la función objetivo específico. Sin un decoding efectivo, no se podría garantizar que las soluciones propuestas sean viables y cumplan con las restricciones y objetivos del problema, lo que subraya su importancia en la correcta implementación y éxito del algoritmo. Los datos de entrada que requiere el decoding son el conjunto de quirófanos y días disponibles (J y H), el conjunto de cirujanos y la disponibilidad y capacidad de estos (S, 𝒂𝒔𝒉, 𝒖𝒔), la matriz de elegibilidad de cirugías (𝜹𝒊𝒋𝒉), y el tiempo requerido para cada cirugía (𝒕𝒊). La función recorre uno por uno los pacientes, del primero al último en la lista de espera. Se inicializan varias estructuras de datos para la asignación, como la lista de pacientes asignados, el conteo de operaciones por E Metodología de resolución 8 8 cirujano, matrices de tiempo de cirugía y tiempo acumulado en quirófanos, y un conjunto de pacientes ya asignados. Para cada paciente en la lista de espera, se extraen los detalles necesarios, concretamente el cirujano responsable, el tiempo esperado de la cirugía, y el día mínimo y máximo en el que se pueden intervenir. Luego, se evalúan los quirófanos y días disponibles siguiendo una estrategia de asignación (ver detalle en 3.1.1, 3.1.2 y 3.1.3), verificando la disponibilidad, calculando los tiempos de inicio y finalización, y comprobando la elegibilidad. Si se encuentra un quirófano y día adecuados, se realiza la asignación y se actualizan las estructuras de datos correspondientes. Por último, se calcula el valor de la función objetivo, que, en este caso, al buscar un equilibrio en la carga de trabajo de los cirujanos, se ha definido como diferencia entre el número de operaciones asignadas a cada cirujano y la media de operaciones asignadas, buscando una distribución equitativa de las operaciones. Este proceso asegura la eficiencia en la asignación, optimizando el uso de quirófanos y cirujanos, y respetando todas las restricciones y capacidades definidas. Al finalizar, se ordena la lista de pacientes asignados y se retornan los resultados que incluyen la lista de asignaciones, el conteo de operaciones por cirujano, las asignaciones de cirujanos a quirófanos y días, y el total de pacientes programados para cirugía. Como se ha indicado anteriormente, en este trabajo se han estudiado tres estrategias para el decoding, se detallarán a continuación. 3.1.1 Best Fit En el contexto de la asignación de pacientes a quirófanos, la estrategia Best Fit busca minimizar el desperdicio de tiempo disponible en los quirófanos. Al implementar esta estrategia, para un paciente determinado, se calcula el tiempo disponible en cada quirófano y día, considerando las restricciones de disponibilidad del cirujano y las restricciones del quirófano. Se selecciona aquel quirófano con el menor tiempo disponible después de asignar la cirugía, asegurando así que el quirófano se utilice de la manera más eficiente posible. Esta estrategia se enfoca en reducir los huecos de tiempo en la programación, maximizando la utilización del tiempo disponible en los quirófanos y distribuyendo de manera óptima las cirugías a lo largo del día. Una vez identificado el quirófano y día, se verifica que la cirugía no cause conflictos con otras cirugías ya programadas y se asigna la cirugía al quirófano seleccionado, actualizando las estructuras de datos correspondientes para reflejar esta nueva asignación. A continuación, en la Figura 1 se presenta el pseudocódigo de esta estrategia de decoding. 9 9 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Figura 1. Pseudocódigo de la estrategia Best Fit 3.1.2 Next Fit La estrategia Next Fit es más sencilla y rápida en comparación con Best Fit. Aquí, la asignación se realiza de manera secuencial, buscando el primer quirófano y día disponibles que cumplan con las restricciones de tiempo y capacidad. Al procesar la lista de espera de pacientes, se asigna cada paciente al siguiente quirófano disponible en la secuencia, sin retroceder para buscar mejores opciones. Esta estrategia es eficiente en términos de tiempo de cómputo, ya que no requiere comparar todos los posibles quirófanos y días para encontrar el mejor ajuste. Sin embargo, puede no ser tan eficiente en términos de utilización de recursos, ya que no minimiza los huecos de tiempo de la misma manera que lo hace Best Fit. Después de encontrar un quirófano y día adecuados, se asigna la cirugía si se cumplen todas las restricciones y se actualizan las estructuras de datos para reflejar la nueva programación. Al igual que en la anterior estrategia, se presenta el pseudocódigo para mayor comprensión de la estrategia en la Figura 2. BestFit Inicializar parámetros Para cada paciente en lista de espera: Inicializar diccionario de tiempo disponible en quirófanos Para cada día en el rango permitido: Para cada quirófano: Verificar disponibilidad del quirófano y cirujano Calcular tiempo disponible en quirófano y actualizar diccionario Si hay quirófanos disponibles: Seleccionar quirófano con menor tiempo disponible Si el cirujano asignado a la cirugía está disponible: Asignar cirugía al quirófano seleccionado Actualizar parámetros Ordenar pacientes asignados por día, quirófano y tiempo de inicio Devolver resultados Metodología de resolución 16 16 Figura 8. Pseudocódigo del ACO principal del proyecto (Elaboración propia) En cuanto a la actualización de feromonas, se han incluido tres variantes [9] en el código: - Actualizar feromonas una única vez por cada iteración: en este caso, para cada iteración del algoritmo, es decir, para cada vez que el conjunto de hormigas finaliza su paso, solo se actualizará la matriz de feromonas con la solución construida por la mejor hormiga de dicha iteración, esto es, la que mejor valor de la función objetivo obtiene de todas las hormigas de la iteración. - Actualizar feromonas tras el paso de todas las hormigas: es la variante principal, en la que, tras el paso de cada hormiga, con los resultados obtenidos, sean los mejores o no, se actualiza la matriz de feromonas. - Actualizar feromonas siempre con la mejor solución global: al igual que en el caso principal explicado anteriormente, la matriz de feromonas se actualiza tras el paso de cada hormiga. La diferencia es que, en lugar de utilizar la solución que ha construido cada hormiga, siempre se utiliza la mejor solución global, independientemente de que pertenezca o no a esa iteración. 3.3.2 Búsqueda Local Al finalizar la etapa de construcción a través de las hormigas, se puede incorporar un procedimiento de búsqueda local con el objetivo de mejorar las soluciones obtenidas durante dicha etapa a través de la implementación de una variante incluyendo un procedimiento de búsqueda local (proceso de intensificación). Existen diversas alternativas búsqueda local que realizan este tipo de intensificación, y en el presente proyecto se ha utilizado la siguiente: • Búsqueda Local Iterada (ILS): La idea central del ILS es enfocar la búsqueda en un pequeño Algoritmo Colonia Hormigas Inicializar mejor_solucion, mejor_fo, mejor_𝜋 Inicializar matriz feromonas y matriz probabilidades Mientras que no se alcance el tiempo máximo de ejecución: Iterando sobre el número de hormigas Actualizar matriz de probabilidades y 𝜋 usando las feromonas Se introduce 𝜋 en el decoding y se construye la lista de pacientes asignados (solución) Se calcula el valor de la FO con los datos obtenidos del decoding Si se cumple criterio de aceptación: Actualizar mejor_solucion, mejor_fo, mejor_𝜋 Actualizar matriz feromonas Devolver mejor_solucion, mejor_fo, mejor_𝜋 17 17 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas subconjunto de soluciones, definido por aquellas que son óptimos locales. En este problema, a partir de una solución inicial, que será la mejor solución obtenida de la aplicación del ACO, se elige un paciente aleatorio y se busca en las n posiciones vecinas. La secuencia con la mejor solución se almacena y se reemplaza por la inicial si ofrece un mejor resultado. Hay tres formas de realizar la búsqueda, según el tipo de vecindad definida: intercambio adyacente, intercambio e inserción. La técnica intercambio es la utilizada en el presente proyecto. - Intercambio: Consiste en seleccionar un paciente de la secuencia actual y permutarlo, es decir, intercambiar sus posiciones, con los n pacientes vecinos [8]. Luego, se evalúa la calidad de la nueva asignación, calculando la función objetivo para determinar si la nueva solución mejora la anterior en términos de equilibrio de la carga de trabajo de los cirujanos. Si la nueva asignación es mejor, se reemplaza la inicial; de lo contrario, se mantiene la solución original. Este proceso de selección, intercambio, evaluación y actualización se repite hasta que se cumpla un criterio de parada, en este caso el tamaño de la vecindad. Esta estrategia permite explorar el espacio de soluciones de manera más exhaustiva, conduciendo a una asignación de pacientes más eficiente y óptima. Figura 9. Pasos fundamentales de la heurística ILS En el siguiente ejemplo, antes del intercambio, el paciente en la posición j se intercambia con el paciente en la posición k. Después del intercambio, la nueva secuencia refleja este cambio. Metodología de resolución 18 18 Figura 10. Intercambio. [8] Este tipo de gráfico es útil para visualizar claramente cómo la técnica de Intercambio modifica las posiciones de los elementos, permitiendo una mejor comprensión de las operaciones realizadas durante la búsqueda local iterada. Siguiendo el mismo esquema que en el anterior punto, el pseudocódigo una vez añadido al ACO con ILS, quedaría de la siguiente manera: Figura 11. Pseudocódigo del ACO con ILS (Elaboración propia) A continuación, se explica en modo de resumen cada variante del algoritmo que posteriormente será analizada: • ACO Todas: Esta variante actualiza las feromonas después del paso de cada hormiga. En general, esta estrategia permite una rápida convergencia hacia mejores soluciones. Algoritmo Colonia Hormigas con ILS Inicializar mejor_solucion, mejor_fo, mejor_𝜋 Inicializar matriz feromonas y matriz probabilidades Mientras que no se alcance el tiempo máximo de ejecución: Iterando sobre el número de hormigas Actualizar matriz de probabilidades y 𝜋 usando las feromonas Se introduce 𝜋 en el decoding y se construye la lista de pacientes asignados (solución) Se calcula el valor de la FO con los datos obtenidos del decoding Si se cumple criterio de aceptación Actualizar mejor_solucion, mejor_fo, mejor_𝜋 Actualizar matriz feromonas ILS (Intercambio) Perturbar mejor 𝜋 Se introduce 𝜋 perturbada en el decoding y se construye la lista de pacientes asignados (solución) Se calcula el valor de la FO con los datos obtenidos del decoding Si se cumple el criterio de aceptación Actualizar mejor_solucion, mejor_fo, mejor_𝜋 Devolver mejor_solucion, mejor_fo, mejor_𝜋 19 19 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas • ACO Iter: Actualiza las feromonas después del paso de todas las hormigas utilizando los resultados de la mejor hormiga. Esta estrategia balancea la exploración y explotación, permitiendo una mejor diversificación en las soluciones. • ACO Global: Usa siempre los datos de la mejor hormiga independientemente de la hormiga que haya pasado. Esta variante mostró ser la más efectiva en términos de encontrar la mejor solución global, ya que concentra la búsqueda en las áreas más prometedoras del espacio de soluciones. • ACO ILS Todas: Combina la actualización de feromonas después del paso de cada hormiga con una búsqueda local iterada. Esta variante mejora significativamente las soluciones debido a la intensificación de la búsqueda local. • ACO ILS Iter: Similar al ACO Iter, pero incorpora búsqueda local iterada. Esta variante también mostró buenos resultados, mejorando las soluciones de manera más consistente. • ACO ILS Global: Utiliza la estrategia de actualización global combinada con búsqueda local iterada. Esta variante resultó ser la más robusta, encontrando consistentemente las mejores soluciones en la mayoría de las instancias. 15 4 ANÁLISIS COMPUTACIONAL continuación, se presentan brevemente las herramientas empleadas para realizar el análisis de diferentes escenarios de gestión. El entorno de programación es Spyder, un entorno de desarrollo interactivo para el lenguaje Python. Se hace uso de las librerías que ofrece Python, las cuales amplían significativamente su funcionalidad. Además, se explican los parámetros que definen los algoritmos utilizados, así como los valores empleados para realizar el análisis y los datos de entrada necesarios para la optimización, junto con los procedimientos utilizados para su cálculo. Herramienta utilizada El desarrollo de todo el código relacionado con la optimización se llevó a cabo en el entorno de programación Spyder, utilizando el lenguaje Python. Una de las principales ventajas de este lenguaje radica en su amplia gama de bibliotecas que pueden ser importadas al programa, todas ellas implementadas de manera eficiente para su uso simultáneo. Aunque en los anexos se proporciona el código creado para abordar el problema de optimización planteado junto con una explicación detallada del mismo, se ofrece también una breve descripción de la estructura que siguen los diferentes códigos y de las funciones que cada uno realiza. 4.1.1 Librerías En primer lugar, se recogen las librerías que se han utilizado en la optimización y se explican brevemente: • Numpy: Es una biblioteca especializada en el cálculo numérico y el análisis de datos, especialmente útil cuando se trabaja con grandes conjuntos de datos. Proporciona una mayor eficiencia en el manejo de vectores y matrices, e incluye numerosas funciones matemáticas para operar con estos tipos de datos [10]. • Pandas: Otra biblioteca destinada al almacenamiento, manipulación y análisis de datos en Python. Su característica principal es la introducción de dos estructuras de datos, las Series y los DataFrames. Este último es particularmente útil en tareas de optimización, ya que se puede concebir como un conjunto de series del mismo tamaño, con índices compartidos y la capacidad de ser almacenados juntos en una estructura tabular. En este proyecto, los resultados de las diferentes instancias generadas son exportados a Excel para su almacenamiento mediante este objeto [11]. • JSON: Esta biblioteca se utiliza para el manejo de datos en formato JSON (JavaScript Object Notation). Permite la serialización y deserialización de objetos Python a y desde JSON, lo que facilita el intercambio de datos entre diferentes sistemas y plataformas. En el presente proyecto, se emplea específicamente para A Análisis computacional 16 16 cargar los datos del problema desde un archivo en formato JSON, tomando el valor asignado a cada variable en el archivo y convirtiéndolo de una cadena JSON a una estructura de datos Python [12]. 4.1.2 Jerarquía del Código En la realización del código existen varios archivos .py, los cuales corresponden a las diversas variantes del algoritmo, que incluyen las distintas funciones requeridas para la creación de los datos del problema, la extracción de los resultados a un archivo Excel y la asignación de los pacientes a lo largo del horizonte temporal mediante las diferentes estrategias anteriormente explicadas, además de contener el código de los distintos algoritmos para la optimización en la secuenciación. A continuación, se mencionan los archivos creados, los cuales, a su vez, tienen tres variantes, una por cada método de actualización de feromonas explicado anteriormente: - ACO.py - ACO_ILS.py - Decoding.py - Gen_datos.py - ARPD.py Cada archivo, además, registra los resultados del algoritmo correspondiente, importándolos al final de la ejecución a un archivo Excel, que posteriormente, mediante el archivo ‘ARPD.py’, será analizado usando el método que se explicará más adelante. Datos de entrada a la optimización Para llevar a cabo la recreación de la jornada en el contexto de la planificación de recursos quirúrgicos para su posterior optimización, es necesario hacer una serie de suposiciones que faciliten la creación de los pacientes en lista de espera junto con el tiempo esperado de sus cirugías, la capacidad regular de las salas de operaciones y los cirujanos disponibles. Para ello, se ha tomado como referencia el artículo “New heuristics for planning operating rooms” [4]. Para realizar la calibración, se generan 10 instancias para cada combinación de los siguientes factores, esto es, un total de 160 problemas a resolver (ver Tabla 2): ▪ Número de quirófanos: 3 y 9. ▪ Valores de β, capacidad máxima de los quirófanos: 1 y 1.25. ▪ Valores de 𝛼, un factor de control usado para el cálculo del número de cirujanos: 1.5 y 2. ▪ Máximo número de días que un cirujano está disponible para llevar a cabo cirugías: 3 y 4. 17 17 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Tabla 2. Valores de entrada al algoritmo 4.2.1 Generación de pacientes Algunos estudios proponen generar cirugías de una en una hasta que la suma de las duraciones esperadas de las cirugías generadas supere un porcentaje β% del tiempo total disponible en los quirófanos a lo largo de todo el horizonte de planificación [13] [14]. En este trabajo, se consideran los niveles del 100% y 125% para el factor β. Este último valor se incluye para simular escenarios donde el tiempo total de cirugía en la lista de espera supera la capacidad total de los quirófanos. Actualmente, estos escenarios son comunes debido a presupuestos restrictivos. De esta manera, para generar la lista de espera, se calcula la capacidad total disponible aumentada en β %, y se agregan cirugías hasta alcanzar este límite. Se asigna a cada cirugía un cirujano de manera equilibrada, y se determinan las fechas mínimas y máximas en las que se puede realizar cada cirugía. También se define la elegibilidad de los quirófanos, considerando si las cirugías requieren quirófanos especializados o multifuncionales, lo que permite un análisis integral y representativo de diferentes configuraciones hospitalarias. De esta manera, el problema se estructura para evaluar diversos escenarios hospitalarios, considerando factores clave como el número de días en el horizonte de planificación, la cantidad de quirófanos disponibles y el número de cirugías en la lista de espera. Por último, consideramos un conjunto I de pacientes, cada uno con características específicas como el tipo de cirugía requerida, el tiempo estimado del procedimiento (𝑡𝑖), y las fechas de liberación (queda establecido que un 95% de los pacientes pueden ser operados desde el primer día) y límite para realizar la cirugía (𝑟𝑑𝑖 y 𝑑𝑖, respectivamente). La asignación de estos pacientes debe considerar también la disponibilidad (𝑢𝑠) y especialización de los cirujanos (𝛾𝑖) y la capacidad de las salas de operaciones (𝑟 𝑗ℎ). 4.2.2 Generación de tiempo estimado de cirugía En este estudio, se analiza la duración de las cirugías, representada por 𝑡𝑖 en minutos, siguiendo una distribución log-normal de 2 parámetros. La duración esperada µ se genera aleatoriamente dentro de un intervalo específico, mientras que la desviación estándar σ se determina a través de un coeficiente de variación que varía dentro de un rango predefinido [0.1µ ... 0.5µ] La fecha límite para realizar una cirugía, representada por 𝑑𝑖 en días, se calcula utilizando una expresión que involucra el tiempo máximo antes del tratamiento (MTBT) y el número de días en la lista de espera (dwl). MTBT varía según el grupo de urgencia del paciente y dwl se selecciona de manera aleatoria dentro de ciertos límites para evitar fechas negativas. Por último, se asigna un cirujano a cada cirugía de la lista de espera. Los cirujanos se ordenan aleatoriamente en cada iteración y se asigna una cirugía a cada uno hasta que todas las cirugías hayan sido asignadas. Análisis computacional 18 18 4.2.3 Elegibilidad de las cirugías La elegibilidad en este contexto se refiere a si una cirugía puede ser realizada en un quirófano especializado o si puede llevarse a cabo en cualquier quirófano, ya sea multifuncional o especializado. En este estudio, la elegibilidad (representada por δ) se genera siguiendo un procedimiento utilizado por una especialidad quirúrgica en un hospital español. El 90% de las cirugías en la lista de espera pueden ser planificadas en cualquier tipo de quirófano, ya sea multifuncional o especializado. Sin embargo, el 10% restante de las cirugías deben realizarse en un quirófano especializado. En esa unidad, el 30% de los quirófanos son especializados. Esto significa que la mayoría de las cirugías pueden realizarse en cualquier quirófano disponible, mientras que un pequeño porcentaje de cirugías requieren un quirófano especializado, y estos quirófanos especializados constituyen una fracción específica de todos los quirófanos disponibles. 4.2.4 Generación de datos de los cirujanos En primer lugar, el número de cirujanos se genera mediante la siguiente expresión [4]: 𝑆 = 𝛼 ∙ ∑ ∑ 𝑟 𝑗ℎℎ∈𝐻𝑗∈𝐽 𝑙 ∙ 𝑎 ∙ 𝑚𝑑𝑠 donde l es el número de semanas laborales en el horizonte de planificación, 𝑟 𝑗ℎ es la capacidad regular del quirófano j en el día h, y 𝛼 es un factor de control. En relación con los datos de los cirujanos, en este proyecto se crea un horario semanal que especifica qué cirujanos están disponibles en cada día. Para evitar que un quirófano disponible esté inactivo en un día, se utiliza un procedimiento de dos pasos para generar el horario semanal. En el primer paso, para cada día, se asigna aleatoriamente un número de cirujanos igual al número de quirófanos disponibles. En el segundo paso, la diferencia entre el máximo número de días por semana trabajada que un cirujano está disponible para llevar a cabo cirugías (mds) y el número de días obtenidos en el primer paso se asigna a cada cirujano. Esto garantiza que se asignen cirujanos adicionales en caso de que no haya suficientes para cubrir todos los días. El tiempo máximo que un cirujano está disponible en un día para realizar cirugías se fija dependiendo de la disponibilidad de cada cirujano, lo cual se especifica según la capacidad regular de un quirófano. En este caso, se considera que este tiempo es igual a la capacidad regular de un quirófano, que se establece normalmente en 8 horas para todos los quirófanos en todos los días. No se considera la capacidad de horas extras en este estudio. A continuación, a modo de resumen, se incluye una tabla en la que se puede observar el tamaño promedio de los problemas que se resuelven en este proyecto. 19 19 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Tabla 3. Tamaño promedio de los problemas resueltos Calibración de los parámetros de los algoritmos La comparación de resultados se realiza mediante un RPD (Relative Percentage Deviation) [2]: 𝑅𝑃𝐷 = 𝑆𝑜𝑚𝑒𝑠𝑜𝑙 − 𝐵𝑒𝑠𝑡𝑠𝑜𝑙 𝑊𝑜𝑟𝑠𝑡𝑠𝑜𝑙 − 𝐵𝑒𝑠𝑡𝑠𝑜𝑙 ∙100 Donde 𝑆𝑜𝑚𝑒𝑠𝑜𝑙 representa la solución obtenida por el algoritmo específico para una instancia particular, 𝑊𝑜𝑟𝑠𝑡𝑠𝑜𝑙 es la peor solución obtenida para esa instancia y 𝐵𝑒𝑠𝑡𝑠𝑜𝑙 es la mejor solución obtenida para esa instancia, ambos valores independientemente del algoritmo utilizado. Luego, se calcula el promedio del RPD (Relative Percentage Deviation) para cada algoritmo (ARPD) y se compara con los otros algoritmos. El ARPD indica, en términos porcentuales, la desviación del resultado obtenido por un algoritmo dado con respecto a la mejor solución encontrada. Por lo tanto, el algoritmo que presente un menor valor de ARPD es el que ofrece mejores resultados para el problema en cuestión. 4.3.1 Tiempo de computación El algoritmo, como se ha explicado anteriormente, se detiene al cumplirse una condición de finalización especificada, el tiempo de computación. Este parámetro define cuánto tiempo se lleva el algoritmo realizando las distintas iteraciones de hormigas y de búsqueda local, cuando proceda, arrastrando sucesivamente la secuencia que aportó una mejor solución en la iteración anterior en este caso. El valor del parámetro se establece siguiendo la regla propuesta por [4], que propone la siguiente fórmula para su cálculo: 𝑇𝑖𝑒𝑚𝑝𝑜 𝑚á𝑥𝑖𝑚𝑜 = |𝐻|∙|𝐽|∙|𝐼|∙ 𝜂 JV Beta Alfa MDS Promedio pacientes en lista de espera Promedio de cirujanos Promedio tiempo ejecucion 3 1 1,5 3 46,10 8,00 8,64 3 1 1,5 4 47,30 6,00 8,87 3 1 2 3 48,00 10,00 9,00 3 1 2 4 48,90 8,00 9,17 3 1,25 1,5 3 61,40 8,00 11,51 3 1,25 1,5 4 59,70 6,00 11,19 3 1,25 2 3 59,20 10,00 11,10 3 1,25 2 4 58,40 8,00 10,95 9 1 1,5 3 146,80 22,00 82,58 9 1 1,5 4 146,40 17,00 82,35 9 1 2 3 146,00 30,00 82,13 9 1 2 4 146,20 22,00 82,24 9 1,25 1,5 3 185,00 22,00 104,06 9 1,25 1,5 4 177,70 17,00 99,96 9 1,25 2 3 183,70 30,00 103,33 9 1,25 2 4 180,90 22,00 101,76 Resultados 26 26 respectivamente para la configuración de beta de 1, y 1,5 y 1,85 para la configuración de beta de 1,25, mostrando un incremento significativo en el número de iteraciones necesarias bajo la configuración más exigente. Esto se correlaciona con ARPD que, aunque bajos, indican un esfuerzo computacional mayor para mantener la precisión requerida. ACO ILS ITER, con promedios de iteraciones de 1,45 y 1,85 para las configuraciones respectivas, destaca por tener el mejor ARPD de 12,06%, pero a costa de un mayor número de iteraciones, lo cual sugiere un compromiso entre precisión y eficiencia computacional. En resumen, los resultados muestran que mientras ACO GLOBAL y ACO TODAS son eficientes en términos de convergencia con un coste computacional relativamente bajo, ACO ILS ITER alcanza una precisión superior, pero requiere más recursos computacionales significativos. En conclusión, en el escenario de 3 quirófanos, las variantes del ACO con Búsqueda Local Iterada (ILS) mostraron un desempeño superior en términos de ARPD y el número promedio de iteraciones, ya que han demostrado obtener resultados mejores a costa de un número de iteraciones no muy superior, incluso parecido en algunos casos, a las realizadas por las variantes que solo realizan el ACO. La variante ACO ILS ITER, en particular, se destacó al obtener las mejores soluciones de manera más consistente y eficiente. Esto sugiere que esta estrategia de actualización de feromonas combinada con búsqueda local iterada es altamente efectiva para problemas de asignación de pacientes en quirófanos con una cantidad moderada de recursos. La mejora en el ARPD y la reducción en el número de iteraciones necesarias para converger a una solución óptima destacan la capacidad de esta estrategia para equilibrar exploración y explotación en el espacio de soluciones. Escenario 2: 9 quirófanos En este escenario, la cantidad promedio de pacientes asignados es de 145 pacientes para un nivel de capacidad de quirófano o beta del 100%, y de 169 pacientes para una capacidad del 125%. Igualmente, la primera comparación de los distintos algoritmos se realiza en función del número de mejores soluciones encontradas en cada instancia por cada algoritmo, es decir, cuántas veces es capaz cada algoritmo de mejorar la solución hasta encontrar la mejor. En la Figura 15 se observa que, para el tiempo de computación considerado, la estrategia de actualizar las feromonas tras el paso de cada hormiga es la que más veces ha conseguido mejorar la solución. Tanto los algoritmos que utilizan esta estrategia, como en el resto de los algoritmos, el ACO con ILS ha obtenido los mejores resultados, es decir, ha sido el más eficaz. 27 27 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Figura 15. Promedio de actualizaciones de la mejor solución encontrada por algoritmo. 9 quirófanos. Para seguir con el análisis se procede ahora a calcular el ARPD de cada algoritmo. En el cálculo de la desviación promedio de la mejor solución encontrada por cada algoritmo respecto a la mejor solución global, no se sigue la tendencia anterior. Los resultados para el escenario con 9 quirófanos, basados en el ARPD, muestran diferencias claras en el desempeño de los diferentes algoritmos (Figura 16): ➢ ACO TODAS: 38,18% ➢ ACO ITER: 40,04% ➢ ACO GLOBAL: 39,65% ➢ ACO ILS TODAS: 20,12% ➢ ACO ILS ITER: 20,74% ➢ ACO ILS GLOBAL: 28,09% Los datos revelan que la combinación de ACO con ILS, tanto en ACO ILS TODAS como en ACO ILS ITER, muestra una mejora significativa en la precisión de las soluciones obtenidas con respecto a las variantes sin ILS, con ARPD del 20,12% y 20,74% respectivamente. Estos valores son considerablemente menores que los obtenidos por las variantes sin ILS (ACO TODAS, ACO ITER y ACO GLOBAL), indicando una mejor capacidad para optimizar la asignación de quirófanos. La variante ACO ILS GLOBAL muestra un ARPD de Resultados 28 28 28,09%, que es superior pero aún mejor que las variantes sin ILS. Como se puede observar en la Figura 16, la introducción de más quirófanos aumenta los ARPD en las variantes sin ILS, destacando la necesidad de técnicas avanzadas como ILS para mantener la precisión. Figura 16. ARPD para 80 instancias. 9 quirófanos. A continuación, siguiendo el mismo esquema que en el anterior caso, se analiza el número de iteraciones promedio para evaluar el rendimiento de los algoritmos, podemos observarlo en la Figura 17: 29 29 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Figura 17. Promedio de iteraciones por algoritmo para cada nivel de capacidad de los quirófanos. 3 quirófanos. En base a los resultados proporcionados y considerando los valores de beta (1 y 1,25) como diferentes configuraciones de prueba para 9 quirófanos, se puede realizar un análisis detallado de los algoritmos ACO en términos de eficiencia computacional y convergencia. ACO TODAS muestra promedios de iteraciones de 1,1078 y 0,9032 para las configuraciones de beta respectivas, indicando una variabilidad en la eficiencia del algoritmo dependiendo de la capacidad de los quirófanos. ACO ITER exhibe promedios de 1,12 y 0,90, destacando una mayor sensibilidad a las condiciones de prueba y la necesidad de ajustes precisos para optimizar su desempeño. En cuanto al ARPD, ACO TODAS y ACO ITER muestran variaciones significativas que reflejan diferencias relativas en la precisión de los resultados bajo diferentes configuraciones de beta. ACO GLOBAL, con promedios de iteraciones de 1,1058 y 0,9044, mantiene una estabilidad relativa en eficiencia, respaldada por ARPD similares, lo que sugiere una capacidad consistente para obtener resultados precisos con un coste computacional controlado. Por otro lado, ACO ILS ITER y ACO ILS GLOBAL presentan promedios de iteraciones de 1,05 y 1,53 respectivamente para la configuración de capacidad del 100%, y 1,40 y 1,30 para la capacidad de 125%. Estos valores indican un incremento significativo en el número de iteraciones necesarias bajo la configuración más exigente, lo cual se correlaciona con ARPD que, aunque bajos, revelan un esfuerzo computacional mayor para Resultados 30 30 mantener la precisión requerida en la asignación de quirófanos. ACO ILS ITER, con promedios de iteraciones de 1,1058 y 0,9044 para las configuraciones respectivas, destaca por alcanzar el mejor ARPD de 20,12%. La comparación de iteraciones entre los algoritmos ACO para asignación de quirófanos revela diferencias significativas basadas en el número de quirófanos y niveles de capacidad. Para el caso de 3 quirófanos, los promedios de iteraciones varían desde 1,05 hasta 1,65, siendo ACO ILS ITER el más alto debido a su enfoque más exhaustivo con un ARPD del 12,06%. En contraste, para 9 quirófanos, los promedios de iteraciones fluctúan entre 0,90 y 1,53, reflejando ajustes en la estrategia de búsqueda según la capacidad, con ACO ILS TODAS y ACO ILS ITER mostrando un desempeño destacado con ARPD de 20,12% y 20,74% respectivamente. Estos resultados destacan la eficacia de la búsqueda local iterada en mejorar la precisión de la asignación de recursos en configuraciones más complejas de quirófanos. Además, como se puede observar en la Figura 18, el promedio de pacientes operados en cada una de las variantes es similar, lo cual demuestra aún más la eficacia del método y la superioridad de las variantes mencionadas, ya que han conseguido realizar un número similar de intervenciones, pero a su vez han logrado equilibrar la carga de trabajo de los cirujanos, disminuyendo así el valor de la función objetivo, lo cuál era la meta principal de este problema. Figura 18. Promedio de pacientes intervenidos por variante 31 31 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Escenario 3: Ampliación del tiempo de computación Para profundizar en el análisis, se introduce un nuevo escenario en el cual se amplía el tiempo de ejecución a 15 minutos para los mejores algoritmos identificados en los análisis previos. Esto se debe a la posibilidad de que un tiempo de computación bajo y pocas iteraciones no sean suficientes para encontrar las mejores soluciones posibles. La ampliación del tiempo de ejecución permitirá evaluar si un mayor tiempo de computación conduce a una mejora significativa en la calidad de las soluciones obtenidas. Dado que evaluar todos los algoritmos con esta ampliación implicaría un tiempo computacional excesivo (aproximadamente 40 horas por cada algoritmo), nos centraremos en los algoritmos más prometedores: ACO ILS TODAS y ACO ILS ITER. El objetivo es determinar si la ampliación del tiempo de ejecución a 15 minutos mejora la calidad de las soluciones encontradas por los algoritmos ACO ILS TODAS y ACO ILS ITER, que previamente demostraron ser los más efectivos. Este análisis permitirá obtener una visión más completa del rendimiento de estos algoritmos bajo condiciones de ejecución extendidas y evaluar el impacto del tiempo adicional en la optimización de la asignación de pacientes en quirófanos. La Figura 19 muestra los promedios de actualización de la mejor solución obtenidos por los algoritmos ACO ILS TODAS y ACO ILS ITER al extender el tiempo de computación a 15 minutos tanto para los escenarios de 3 y 9 quirófanos, como para sus respectivos valores de beta, 1 y 1.25. ACO ILS TODAS muestra un promedio constante de actualizaciones, lo que indica que sigue encontrando mejoras en las soluciones a lo largo del tiempo de computación extendido. Esto sugiere que un mayor tiempo de computación permite al algoritmo explorar más exhaustivamente el espacio de soluciones, encontrando mejores configuraciones de asignación de quirófanos. Similar a ACO ILS TODAS, ACO ILS ITER también presenta un número significativo de actualizaciones de la mejor solución, destacando su capacidad para mejorar continuamente las soluciones a lo largo del tiempo. La frecuencia de las actualizaciones puede ser un indicador de la efectividad del enfoque iterativo del algoritmo. Resultados 32 32 Figura 19. Promedios de actualización de la mejor solución La Figura 20 ilustra los promedios de iteraciones realizadas por los algoritmos ACO ILS TODAS y ACO ILS ITER durante el tiempo de ejecución extendido. ACO ILS TODAS muestra un número considerable de iteraciones, reflejando su enfoque en explorar una amplia variedad de soluciones posibles. El alto número de iteraciones sugiere que el algoritmo se beneficia del tiempo extendido, permitiendo una mayor cobertura del espacio de soluciones. Aunque el número de iteraciones es menor en comparación con ACO ILS TODAS, ACO ILS ITER todavía realiza un número significativo de iteraciones. Esto indica que, aunque su enfoque iterativo puede ser más intensivo en tiempo por iteración, sigue aprovechando el tiempo extendido para explorar y mejorar las soluciones. 33 33 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Figura 20. Promedios de iteraciones realizadas La Figura 21 presenta los valores de ARPD para los algoritmos ACO ILS TODAS y ACO ILS ITER con el tiempo de ejecución extendido. El ARPD, como se ha explicado anteriormente, es una medida de la calidad de las soluciones en comparación con una solución óptima conocida o una referencia. Los valores de ARPD para ACO ILS ITER son notablemente bajos, indicando que las soluciones obtenidas están muy cerca de la mejor. La reducción del ARPD en comparación con tiempos de computación más cortos sugiere que el algoritmo se beneficia significativamente del tiempo adicional, permitiendo una mayor refinación de las soluciones. ACO ILS TODAS también muestra valores bajos de ARPD, aunque ligeramente superiores a los de ACO ILS ITER. Esto indica que, aunque ACO ILS TODAS mejora con el tiempo extendido, puede no alcanzar el mismo nivel de refinamiento que ACO ILS ITER en algunos casos. Resultados 34 34 Figura 21. ARPD La Figura 22 muestra el promedio de pacientes intervenidos por los algoritmos ACO ILS TODAS y ACO ILS ITER durante el tiempo de ejecución extendido. ACO ILS TODAS muestra un alto promedio de pacientes intervenidos, lo que indica una asignación eficiente y efectiva de los recursos quirúrgicos. El tiempo adicional de computación permite una optimización más precisa de la programación de las cirugías, resultando en un mayor número de pacientes atendidos. Aunque también muestra un promedio alto, ACO ILS ITER es ligeramente inferior al de ACO ILS TODAS. Esto sugiere que, aunque ACO ILS ITER es efectivo, puede no ser tan eficiente en la asignación adecuada de los recursos como ACO ILS TODAS en el tiempo extendido. 35 35 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas Figura 22. Promedio de pacientes intervenidos En conclusión, la ampliación del tiempo de ejecución a 15 minutos resulta en un mayor número de actualizaciones de la mejor solución para ambos algoritmos, demostrando que el tiempo adicional permite una exploración más profunda y detallada del espacio de soluciones, mejorando la calidad de las soluciones obtenidas. Ambos algoritmos utilizan efectivamente el tiempo adicional para realizar un gran número de iteraciones, lo que les permite mejorar continuamente las soluciones. El tiempo de computación extendido a 15 minutos resulta en una mejora significativa en la calidad de las soluciones para ambos algoritmos, reflejada en la reducción de los valores de ARPD, y subraya la importancia de un mayor tiempo de computación para mejorar la eficiencia en la asignación de quirófanos y distribuir mejor el número de pacientes atendidos por cada cirujano, equilibrando así la carga de trabajo. Anexos 42 42 indices_primer_dia = rg.choice(range(i), size=pacientes_primer_dia, replace=False) # Asignar las fechas de liberación para el 95% de los pacientes desde el primer día rd_i[indices_primer_dia] = 0 # Generar las fechas de liberación restantes como se calculaban anteriormente for x in range(i): if rd_i[x] == 0: # Si la fecha de liberación es 0, ya está establecida como el primer día continue rd_i[x] = rg.integers(low=0, high=j) # Generar aleatoriamente la fecha de liberación para los pacientes restantes for x in range(i): MTBT_i = rg.choice([45, 180, 360]) # Tiempo máximo antes de que la cirugía sea crítica para el paciente i dwl_i[x] = rg.uniform(low=0, high=MTBT_i - 1) d_i[x] = int(MTBT_i - dwl_i[x]) # Fecha de vencimiento para realizar la cirugía en el paciente i // antes de esta fecha se tiene que operar el paciente i lista_espera = [] for idx in range(i): cirujano = int(y_i_values[idx]) # Cirujano asignado al paciente tiempo_cirugia = int(t_i[idx]) # Tiempo esperado de la cirugía (en minutos) dia_minimo = int(rd_i[idx]) # Día a partir del cual se puede operar al paciente i dia_maximo = int(d_i[idx]) # Día antes del cual se debe operar al paciente i paciente_params = {'ID': idx, 'Cirujano': cirujano, 'Tiempo de Cirugia': tiempo_cirugia, 'Dia minimo operar': dia_minimo, 'Dia maximo operar': dia_maximo} lista_espera.append(paciente_params) # Añadir paciente a la lista de espera return i , lista_espera, y_i_values, rd_i, d_i, t_i, mu_i, sigma_i def GeneraOR_eligibility(num_pacientes, num_quirofanos, num_dias): # Porcentaje de cirugías que requieren un quirófano especializado porcentaje_especializado = 0.1 # Porcentaje de quirófanos que son especializados porcentaje_quirofanos_especializados = 0.3 # Array para almacenar la disponibilidad de los quirófanos OR_ELIG = np.zeros((num_pacientes, num_quirofanos, num_dias), dtype=int) # Generar la elegibilidad de los quirófanos para cada cirugía for i in range(num_pacientes): for h in range(num_dias): for j in range(num_quirofanos): if rg.random() < porcentaje_especializado: # Cirugía que requiere un quirófano especializado 43 43 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas if rg.random() < porcentaje_quirofanos_especializados: # Quirófano especializado OR_ELIG[i, j, h] = 1 else: # Quirófano multifuncional OR_ELIG[i, j, h] = 0 else: # Cirugía que puede realizarse en cualquier quirófano OR_ELIG[i, j, h] = 1 return OR_ELIG instancias = 10 # Número de instancias a generar h = 5 # días L = 1 # semanas r_jh = 8 * 60 # 8 horas al día de capacidad cada quirófano j en cada día h a = 8 * 60 # Generar datos para cirujanos j_values = [3, 9] beta_values = [1, 1.25] alfa_values = [1.5, 2] mds_values = [3, 4] for j in j_values: for beta in beta_values: for alfa in alfa_values: for mds in mds_values: for z in range(instancias): s=0 archivo_dato = f'C:/Users/luisa/OneDrive/Escritorio/TFG/Códigos funcionales/DATOS/PROBLEMA_{j}_{beta}_{alfa}_{mds}_{z}.txt' s = round(alfa * ((r_jh * j * h) / (L * a * mds))) print("El script se ejecutó correctamente.") # Generar asignación de cirujanos por día a_sh = np.zeros((s, h), dtype=int) # Array para almacenar la disponibilidad de los cirujanos cirujanos_operados = np.zeros((s), dtype=int) # Array para rastrear los días operados por cada cirujano cirujanos_elegidos = set() # Conjunto para almacenar los cirujanos ya elegidos for quirofano in range(j): cirujano_inicial = rg.choice(list(set(range(s)) - cirujanos_elegidos)) a_sh[cirujano_inicial][0] = a # Inicialmente, al menos un cirujano por día cirujanos_operados[cirujano_inicial] += 1 cirujanos_elegidos.add(cirujano_inicial) for dia in range(1,h): for cirujano in range(s): if a_sh[cirujano, dia] <= a and cirujanos_operados[cirujano] < mds: a_sh[cirujano, dia] = a # Capacidad regular de los cirujanos en el día h (en minutos) cirujanos_operados[cirujano] += 1 # Registrar que el cirujano ha operado este día print("El script se ejecutó correctamente.") Anexos 44 44 i, lista_espera, y_i_values, rd_i, d_i, t_i, mu_i, sigma_i = definir_lista_espera(beta, j, h, r_jh) OR_ELIG = GeneraOR_eligibility(i, j, h) u_s = rg.integers(2, j) # Número entero no negativo de quirófanos en los que los cirujanos pueden realizar cirugías en el mismo día with open(archivo_dato, 'w') as file: # Escribir en el archivo file.write(f'"Horizonte"={h}\n') file.write(f'"Quirófanos"={j}\n') file.write(f'"Pacientes en lista de espera"={i}\n') file.write(f'"Cirujanos"={s}\n') file.write(f'"Capacidad diaria de los quirófanos"={r_jh}\n') file.write('"Lista de espera"=' + json.dumps(lista_espera) + '\n') file.write('"Matriz de elegibilidad"=' + json.dumps(OR_ELIG.tolist()) + '\n') # Convertir la matriz NumPy a lista file.write(f'"Cirujanos asignados por día"={a_sh.tolist()}\n') file.write(f'"Número de quirófanos en los que los cirujanos pueden realizar cirugías en el mismo día"={u_s}\n') 45 45 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas ACO: Actualización de feromonas en todas las hormigas import numpy as np import pandas as pd import json import time import sys sys.path.append('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/FINALES') from decoding import firstfit # Importar la función # Inicialización del generador de números aleatorios rg = np.random.default_rng(2) # Función para convertir los datos de pacientes asignados en un DataFrame def convertir_pacientes_asignados_a_dataframe(pacientes_asignados): columnas = ['Paciente ID', 'Quirófano', 'Día', 'Cirujano', 'Duración', 'OR_ELIG', 'Inicio', 'Finalización'] data = [] for paciente in pacientes_asignados: data.append(list(paciente)) df_pacientes = pd.DataFrame(data, columns=columnas) return df_pacientes # Función para convertir los datos de cirujanos a un DataFrame def convertir_cirujanos_a_dataframe(cirujanos_operaciones): data = {'Cirujano': range(1, len(cirujanos_operaciones) + 1), 'Operaciones': cirujanos_operaciones} df_cirujanos = pd.DataFrame(data) return df_cirujanos # Exportar los datos a un archivo Excel def exportar_a_excel(mejor_solucion, cirujanos_operaciones, mejor_fo, mejor_PI, pacientes_operados): # Convertir los datos a DataFrames df_pacientes = convertir_pacientes_asignados_a_dataframe(mejor_solucion) df_cirujanos = convertir_cirujanos_a_dataframe(cirujanos_operaciones) # Crear un ExcelWriter para escribir en el archivo Excel with pd.ExcelWriter('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/Calibracion_fi nal/Resultados/resultados_ACO_todas.xlsx') as writer: df_pacientes.to_excel(writer, sheet_name='Pacientes Asignados', index=False) df_cirujanos.to_excel(writer, sheet_name='Cirujanos Operaciones', index=False) # Agregar los valores de la función objetivo y otros detalles detalles = { 'Valor de la Función Objetivo': [mejor_fo], 'Número de Pacientes Operados': [pacientes_operados] } df_detalles = pd.DataFrame(detalles) df_detalles.to_excel(writer, sheet_name='Detalles', index=False) # Crear un DataFrame para los valores de la función objetivo de cada instancia Anexos 46 46 df_instancias = pd.DataFrame(datos_instancias, columns=['JV', 'Beta', 'Alfa', 'MDS','Instancia', 'FO', 'Pacientes operados', 'Actualizaciones FO','Iteraciones realizadas del algoritmo']) # Agregar los valores de la función objetivo de las instancias a una nueva pestaña df_instancias.to_excel(writer, sheet_name='Valores FO', index=False) def leer_datos_desde_archivo(archivo): with open(archivo, 'r') as file: # Leer los datos desde el archivo data = file.readlines() h = int(data[0].split('=')[1]) j = int(data[1].split('=')[1]) i = int(data[2].split('=')[1]) s = int(data[3].split('=')[1]) r_jh = int(data[4].split('=')[1]) lista_espera = json.loads(data[5].split('=')[1]) OR_ELIG = json.loads(data[6].split('=')[1]) a_sh = json.loads(data[7].split('=')[1]) u_s = int(data[8].split('=')[1]) return h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s def equilibrar_carga2(cirujanos_operaciones): # Calcula la diferencia entre la media de operaciones y la cantidad de operaciones de cada cirujano media_operaciones = sum(cirujanos_operaciones) / len(cirujanos_operaciones) suma_diferencias = sum(abs(op - media_operaciones) for op in cirujanos_operaciones) return suma_diferencias def actualizar_probabilidades(lista_espera, pacientes_asignados, feromonas, probabilidades): # Inicialización de probabilidades con valores uniformes probabilidades = np.full((i, len(lista_espera)), 1 / len(lista_espera)) # Actualizar las probabilidades para cada paciente en función de las feromonas actualizadas for idx, paciente in enumerate(pacientes_asignados): paciente_id = paciente[0] # ID original del paciente posicion_asignada = idx feromonas_paciente = feromonas[paciente_id, posicion_asignada] # Feromonas asociadas con el paciente suma_feromonas_paciente = sum(feromonas[paciente_id, :]) # Suma de las feromonas del paciente en todas las posiciones # Verificar si hay feromonas asociadas con el paciente if suma_feromonas_paciente > 0: # Actualizar las probabilidades sumando el cálculo de las feromonas probabilidades[paciente_id, posicion_asignada] += feromonas_paciente / suma_feromonas_paciente return probabilidades 47 47 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas def actualizar_feromonas(feromonas, pacientes_asignados, calidad_solucion, deposito_factor, lista_espera): # Evaporación de feromonas feromonas *= (1 - evaporacion_factor) # Depósito de feromonas en las posiciones asignadas en la mejor solución encontrada for idx, paciente in enumerate(pacientes_asignados): paciente_id = paciente[0] # ID original del paciente posicion_asignada = idx if calidad_solucion == 0: feromonas[paciente_id, posicion_asignada] += deposito_factor else: feromonas[paciente_id, posicion_asignada] += deposito_factor / calidad_solucion return feromonas def actualizar_lista_espera(lista_espera, probabilidades): lista_espera_actualizada = [] for j in range(probabilidades.shape[1]): assigned_patient = False while not assigned_patient: # Normalizar las probabilidades para asegurarse de que sumen 1 normalized_probs = probabilidades[:, j] / np.sum(probabilidades[:, j]) # Escoger aleatoriamente un paciente en función de las probabilidades normalizadas idx_selected = np.random.choice(range(probabilidades.shape[0]), p=normalized_probs) # Verificar si el paciente ya está en la lista de espera actualizada if lista_espera[idx_selected] not in lista_espera_actualizada: lista_espera_actualizada.append(lista_espera[idx_selected]) assigned_patient = True return lista_espera_actualizada def algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor): print(z) iteraciones = 0 tiempo_maximo_iter = i * j * h * 0.0125 tiempo_inicio_iter = time.time() mejor_solucion_global = None mejor_fo_global = float('inf') mejor_PI_global = None pacientes_operados_global = None cirujanos_operaciones_global = None contador = 0 feromonas = np.ones((i, len(lista_espera))) # Inicialización de feromonas probabilidades = np.full((i, len(lista_espera)), 1 / len(lista_espera)) pacientes_asignados = [] primera = True while (time.time() - tiempo_inicio_iter) < tiempo_maximo_iter: Anexos 48 48 for hormiga in range(num_hormigas): if primera == True: probabilidades = probabilidades primera = False else: probabilidades = actualizar_probabilidades(lista_espera, pacientes_asignados, feromonas, probabilidades) # Actualizar lista de espera con las probabilidades calculadas lista_espera = actualizar_lista_espera(lista_espera, probabilidades) pacientes_asignados, cirujanos_operaciones, cirujanos_quirofanos_asignados, pacientes_operados = firstfit(lista_espera, OR_ELIG, j, h, r_jh, s, a_sh, u_s) fo = equilibrar_carga2(cirujanos_operaciones) # Actualización de las feromonas if fo < mejor_fo_global: mejor_solucion_global = pacientes_asignados mejor_fo_global = fo mejor_PI_global = lista_espera pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 # Actualizar feromonas con las mejores soluciones encontradas feromonas = actualizar_feromonas(feromonas, pacientes_asignados, fo, deposito_factor, lista_espera) iteraciones += 1 return iteraciones, mejor_solucion_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global, cirujanos_operaciones_global, contador # Medir tiempo de ejecución tiempo_inicio = time.time() # Datos del problema j_values = [3, 9] beta_values = [1, 1.25] alfa_values = [1.5, 2] mds_values = [3, 4] instancias = 10 mejor_solucion_global = None mejor_fo_global = float('inf') pacientes_operados_global = None cirujanos_operaciones_global = None mejor_PI_global = None num_pacientes_global = float('inf') num_quirof_global = float('inf') num_cirujanos_global = float('inf') # Almacenar los valores de la función objetivo de cada instancia datos_instancias = [] contador_glob = 0 for jv in j_values: for beta in beta_values: for alfa in alfa_values: 49 49 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas for mds in mds_values: for z in range(instancias): archivo = f'C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/DATOS/PROBLEMA_{jv}_{beta}_{ alfa}_{mds}_{z}.txt' h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s = leer_datos_desde_archivo(archivo) # Parámetros para el algoritmo de colonia de hormigas tiempo_maximo = i * j * h * 0.0125 num_hormigas = 4 #se puede aumentar para que haya mas actualizaciones en cada iteración evaporacion_factor = 0.1 # Factor de evaporación de feromonas deposito_factor = 1.0 # Factor de depósito de feromonas tamaño_vecindad = 10 # Tamaño de la vecindad para la búsqueda local iterada num_iteraciones_ILS = 1 # Número de iteraciones de la búsqueda local iterada contador_local = 0 iteraciones_instancia = 0 # Ejecutar algoritmo de colonia de hormigas con búsqueda local iterada iteraciones, mejor_solucion, mejor_fo, mejor_PI, pacientes_operados, cirujanos_operaciones, contador = algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor) contador_glob += contador contador_local += contador iteraciones_instancia += iteraciones # Almacenar el valor de la función objetivo de esta instancia datos_instancias.append((jv, beta, alfa, mds, z+1, round(mejor_fo,2), pacientes_operados, contador_local, iteraciones_instancia)) cambio = False # Actualizar la mejor solución global si encontramos una mejor if mejor_fo < mejor_fo_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if mejor_fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados Anexos 50 50 cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if cambio == True: tiempo_mejor = time.time() - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las instancias para los parámetros actuales print(f"\nSe ha actualizado la solución con los parámetros {jv}-{beta}-{alfa}-{mds} en la instancia {z}:") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones print("\nValor de la función objetivo de la nueva mejor solución global:", mejor_fo_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #print(f"\nInstancia: {z+1}, Parametros: {jv}-{beta}- {alfa}-{mds}") #print(f"Número de pacientes operados: {pacientes_operados}") #print(f"Número total de cirugías: {np.sum(cirujanos_operaciones)}") #print(f"Carga de trabajo equilibrada: {mejor_fo}\n") #print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones) # Medir tiempo de finalización tiempo_final = time.time() tiempo_ejecucion = tiempo_final - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las iteraciones print(f"\nMejor solución encontrada: Con los parámetros {jv_global}- {beta_global}-{alfa_global}-{mds_global}") print(f"\nEl número de pacientes en la lista de espera de esta solución es de {num_pacientes_global}\n") for idx, paciente in enumerate(mejor_solucion_global, start=1): i, j, h, cirujano, duracion, eligibilidad, inicio, finalizacion = paciente print(f"Paciente {i}: En el día {h+1}, operado por el cirujano {cirujano+1}, en el quirófano {j+1}, duración {duracion:.2f} minutos. Inicio: {inicio}, Finalización: {finalizacion}, OR_ELIG: {eligibilidad}") 51 51 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones y el tiempo de ejecución del código print("\nValor de la función objetivo de la mejor solución:", mejor_fo_global) print(f'Tiempo de ejecución: {tiempo_ejecucion:.2f} segundos') # Imprimir la lista de espera de la mejor solución encontrada entre todas las iteraciones print("\nLa lista de espera de la mejor solución:", mejor_PI_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #Eficiencia del algoritmo print(f"\nGracias al algoritmo se ha conseguido mejorar la solución {contador_glob} veces.") # Llamar a la función para exportar los datos exportar_a_excel(mejor_solucion_global, cirujanos_operaciones_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global) Anexos 58 58 algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor) contador_glob += contador contador_local += contador iteraciones_instancia += iteraciones # Almacenar el valor de la función objetivo de esta instancia datos_instancias.append((jv, beta, alfa, mds, z+1, round(mejor_fo,2), pacientes_operados, contador_local, iteraciones_instancia)) cambio = False # Actualizar la mejor solución global si encontramos una mejor if mejor_fo < mejor_fo_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if mejor_fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if cambio == True: tiempo_mejor = time.time() - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las instancias para los parámetros actuales print(f"\nSe ha actualizado la solución con los parámetros {jv}-{beta}-{alfa}-{mds} en la instancia {z}:") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones print("\nValor de la función objetivo de la nueva mejor solución global:", mejor_fo_global) 59 59 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #print(f"\nInstancia: {z+1}, Parametros: {jv}-{beta}- {alfa}-{mds}") #print(f"Número de pacientes operados: {pacientes_operados}") #print(f"Número total de cirugías: {np.sum(cirujanos_operaciones)}") #print(f"Carga de trabajo equilibrada: {mejor_fo}\n") #print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones) # Medir tiempo de finalización tiempo_final = time.time() tiempo_ejecucion = tiempo_final - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las iteraciones print(f"\nMejor solución encontrada: Con los parámetros {jv_global}- {beta_global}-{alfa_global}-{mds_global}") print(f"\nEl número de pacientes en la lista de espera de esta solución es de {num_pacientes_global}\n") for idx, paciente in enumerate(mejor_solucion_global, start=1): i, j, h, cirujano, duracion, eligibilidad, inicio, finalizacion = paciente print(f"Paciente {i}: En el día {h+1}, operado por el cirujano {cirujano+1}, en el quirófano {j+1}, duración {duracion:.2f} minutos. Inicio: {inicio}, Finalización: {finalizacion}, OR_ELIG: {eligibilidad}") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones y el tiempo de ejecución del código print("\nValor de la función objetivo de la mejor solución:", mejor_fo_global) print(f'Tiempo de ejecución: {tiempo_ejecucion:.2f} segundos') # Imprimir la lista de espera de la mejor solución encontrada entre todas las iteraciones print("\nLa lista de espera de la mejor solución:", mejor_PI_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #Eficiencia del algoritmo print(f"\nGracias al algoritmo se ha conseguido mejorar la solución {contador_glob} veces.") # Llamar a la función para exportar los datos exportar_a_excel(mejor_solucion_global, cirujanos_operaciones_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global) Anexos 60 60 ACO: Actualización de feromonas siempre con la mejor solución global import numpy as np import pandas as pd import json import time import sys sys.path.append('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/FINALES') from decoding import firstfit # Importar la función # Inicialización del generador de números aleatorios rg = np.random.default_rng(2) # Función para convertir los datos de pacientes asignados en un DataFrame def convertir_pacientes_asignados_a_dataframe(pacientes_asignados): columnas = ['Paciente ID', 'Quirófano', 'Día', 'Cirujano', 'Duración', 'OR_ELIG', 'Inicio', 'Finalización'] data = [] for paciente in pacientes_asignados: data.append(list(paciente)) df_pacientes = pd.DataFrame(data, columns=columnas) return df_pacientes # Función para convertir los datos de pacientes asignados en un DataFrame def convertir_pacientes_asignados_a_dataframe(pacientes_asignados): columnas = ['Paciente ID', 'Quirófano', 'Día', 'Cirujano', 'Duración', 'OR_ELIG', 'Inicio', 'Finalización'] data = [] for paciente in pacientes_asignados: data.append(list(paciente)) df_pacientes = pd.DataFrame(data, columns=columnas) return df_pacientes # Función para convertir los datos de cirujanos a un DataFrame def convertir_cirujanos_a_dataframe(cirujanos_operaciones): data = {'Cirujano': range(1, len(cirujanos_operaciones) + 1), 'Operaciones': cirujanos_operaciones} df_cirujanos = pd.DataFrame(data) return df_cirujanos # Exportar los datos a un archivo Excel def exportar_a_excel(mejor_solucion, cirujanos_operaciones, mejor_fo, mejor_PI, pacientes_operados): # Convertir los datos a DataFrames df_pacientes = convertir_pacientes_asignados_a_dataframe(mejor_solucion) df_cirujanos = convertir_cirujanos_a_dataframe(cirujanos_operaciones) # Crear un ExcelWriter para escribir en el archivo Excel with pd.ExcelWriter('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/Calibracion_fi nal/Resultados/resultados_ACO_siempreglob.xlsx') as writer: df_pacientes.to_excel(writer, sheet_name='Pacientes Asignados', index=False) df_cirujanos.to_excel(writer, sheet_name='Cirujanos Operaciones', index=False) 61 61 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Agregar los valores de la función objetivo y otros detalles detalles = { 'Valor de la Función Objetivo': [mejor_fo], 'Número de Pacientes Operados': [pacientes_operados] } df_detalles = pd.DataFrame(detalles) df_detalles.to_excel(writer, sheet_name='Detalles', index=False) # Crear un DataFrame para los valores de la función objetivo de cada instancia df_instancias = pd.DataFrame(datos_instancias, columns=['JV', 'Beta', 'Alfa', 'MDS','Instancia', 'FO', 'Pacientes operados', 'Actualizaciones FO','Iteraciones realizadas del algoritmo']) # Agregar los valores de la función objetivo de las instancias a una nueva pestaña df_instancias.to_excel(writer, sheet_name='Valores FO', index=False) def leer_datos_desde_archivo(archivo): with open(archivo, 'r') as file: # Leer los datos desde el archivo data = file.readlines() h = int(data[0].split('=')[1]) j = int(data[1].split('=')[1]) i = int(data[2].split('=')[1]) s = int(data[3].split('=')[1]) r_jh = int(data[4].split('=')[1]) lista_espera = json.loads(data[5].split('=')[1]) OR_ELIG = json.loads(data[6].split('=')[1]) a_sh = json.loads(data[7].split('=')[1]) u_s = int(data[8].split('=')[1]) return h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s def equilibrar_carga2(cirujanos_operaciones): # Calcula la diferencia entre la media de operaciones y la cantidad de operaciones de cada cirujano media_operaciones = sum(cirujanos_operaciones) / len(cirujanos_operaciones) suma_diferencias = sum(abs(op - media_operaciones) for op in cirujanos_operaciones) return suma_diferencias def actualizar_probabilidades(lista_espera, pacientes_asignados, feromonas, probabilidades): # Inicialización de probabilidades con valores uniformes probabilidades = np.full((i, len(lista_espera)), 1 / len(lista_espera)) # Actualizar las probabilidades para cada paciente en función de las feromonas actualizadas for idx, paciente in enumerate(pacientes_asignados): paciente_id = paciente[0] # ID original del paciente posicion_asignada = idx feromonas_paciente = feromonas[paciente_id, posicion_asignada] # Feromonas asociadas con el paciente suma_feromonas_paciente = sum(feromonas[paciente_id, :]) # Suma de las feromonas del paciente en todas las posiciones Anexos 62 62 # Verificar si hay feromonas asociadas con el paciente if suma_feromonas_paciente > 0: # Actualizar las probabilidades sumando el cálculo de las feromonas probabilidades[paciente_id, posicion_asignada] += feromonas_paciente / suma_feromonas_paciente return probabilidades def actualizar_feromonas(feromonas, pacientes_asignados, calidad_solucion, deposito_factor, lista_espera): # Evaporación de feromonas feromonas *= (1 - evaporacion_factor) # Depósito de feromonas en las posiciones asignadas en la mejor solución encontrada for idx, paciente in enumerate(pacientes_asignados): paciente_id = paciente[0] # ID original del paciente posicion_asignada = idx if calidad_solucion == 0: feromonas[paciente_id, posicion_asignada] += deposito_factor else: feromonas[paciente_id, posicion_asignada] += deposito_factor / calidad_solucion return feromonas def actualizar_lista_espera(lista_espera, probabilidades): lista_espera_actualizada = [] for j in range(probabilidades.shape[1]): assigned_patient = False while not assigned_patient: # Normalizar las probabilidades para asegurarse de que sumen 1 normalized_probs = probabilidades[:, j] / np.sum(probabilidades[:, j]) # Escoger aleatoriamente un paciente en función de las probabilidades normalizadas idx_selected = np.random.choice(range(probabilidades.shape[0]), p=normalized_probs) # Verificar si el paciente ya está en la lista de espera actualizada if lista_espera[idx_selected] not in lista_espera_actualizada: lista_espera_actualizada.append(lista_espera[idx_selected]) assigned_patient = True return lista_espera_actualizada def algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor): print(z) iteraciones = 0 tiempo_maximo_iter = i * j * h * 0.0125 tiempo_inicio_iter = time.time() mejor_solucion_global = None mejor_fo_global = float('inf') 63 63 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas mejor_PI_global = None pacientes_operados_global = None cirujanos_operaciones_global = None contador = 0 feromonas = np.ones((i, len(lista_espera))) # Inicialización de feromonas probabilidades = np.full((i, len(lista_espera)), 1 / len(lista_espera)) pacientes_asignados = [] primera = True while (time.time() - tiempo_inicio_iter) < tiempo_maximo_iter: for hormiga in range(num_hormigas): if primera == True: probabilidades = probabilidades primera = False else: probabilidades = actualizar_probabilidades(lista_espera, pacientes_asignados, feromonas, probabilidades) # Actualizar lista de espera con las probabilidades calculadas lista_espera = actualizar_lista_espera(lista_espera, probabilidades) pacientes_asignados, cirujanos_operaciones, cirujanos_quirofanos_asignados, pacientes_operados = firstfit(lista_espera, OR_ELIG, j, h, r_jh, s, a_sh, u_s) fo = equilibrar_carga2(cirujanos_operaciones) # Actualización de las feromonas if fo < mejor_fo_global: mejor_solucion_global = pacientes_asignados mejor_fo_global = fo mejor_PI_global = lista_espera pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 if fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = pacientes_asignados mejor_fo_global = fo mejor_PI_global = lista_espera pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 # Actualizar feromonas con las mejores soluciones encontradas feromonas = actualizar_feromonas(feromonas, pacientes_asignados, fo, deposito_factor, lista_espera) iteraciones += 1 return iteraciones, mejor_solucion_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global, cirujanos_operaciones_global, contador # Medir tiempo de ejecución tiempo_inicio = time.time() # Datos del problema j_values = [3, 9] Anexos 64 64 beta_values = [1, 1.25] alfa_values = [1.5, 2] mds_values = [3, 4] instancias = 10 mejor_solucion_global = None mejor_fo_global = float('inf') pacientes_operados_global = None cirujanos_operaciones_global = None mejor_PI_global = None num_pacientes_global = float('inf') num_quirof_global = float('inf') num_cirujanos_global = float('inf') # Almacenar los valores de la función objetivo de cada instancia datos_instancias = [] contador_glob = 0 for jv in j_values: for beta in beta_values: for alfa in alfa_values: for mds in mds_values: for z in range(instancias): archivo = f'C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/DATOS/PROBLEMA_{jv}_{beta}_{ alfa}_{mds}_{z}.txt' h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s = leer_datos_desde_archivo(archivo) # Parámetros para el algoritmo de colonia de hormigas tiempo_maximo = i * j * h * 0.0125 num_hormigas = 4 #se puede aumentar para que haya mas actualizaciones en cada iteración evaporacion_factor = 0.1 # Factor de evaporación de feromonas deposito_factor = 1.0 # Factor de depósito de feromonas tamaño_vecindad = 10 # Tamaño de la vecindad para la búsqueda local iterada num_iteraciones_ILS = 1 # Número de iteraciones de la búsqueda local iterada contador_local = 0 iteraciones_instancia = 0 # Ejecutar algoritmo de colonia de hormigas con búsqueda local iterada iteraciones, mejor_solucion, mejor_fo, mejor_PI, pacientes_operados, cirujanos_operaciones, contador = algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor) contador_glob += contador contador_local += contador iteraciones_instancia += iteraciones # Almacenar el valor de la función objetivo de esta instancia datos_instancias.append((jv, beta, alfa, mds, z+1, round(mejor_fo,2), pacientes_operados, contador_local, iteraciones_instancia)) cambio = False # Actualizar la mejor solución global si encontramos una mejor 65 65 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas if mejor_fo < mejor_fo_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if mejor_fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if cambio == True: tiempo_mejor = time.time() - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las instancias para los parámetros actuales print(f"\nSe ha actualizado la solución con los parámetros {jv}-{beta}-{alfa}-{mds} en la instancia {z}:") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones print("\nValor de la función objetivo de la nueva mejor solución global:", mejor_fo_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #print(f"\nInstancia: {z+1}, Parametros: {jv}-{beta}- {alfa}-{mds}") #print(f"Número de pacientes operados: {pacientes_operados}") #print(f"Número total de cirugías: {np.sum(cirujanos_operaciones)}") Anexos 66 66 #print(f"Carga de trabajo equilibrada: {mejor_fo}\n") #print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones) # Medir tiempo de finalización tiempo_final = time.time() tiempo_ejecucion = tiempo_final - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las iteraciones print(f"\nMejor solución encontrada: Con los parámetros {jv_global}- {beta_global}-{alfa_global}-{mds_global}") print(f"\nEl número de pacientes en la lista de espera de esta solución es de {num_pacientes_global}\n") for idx, paciente in enumerate(mejor_solucion_global, start=1): i, j, h, cirujano, duracion, eligibilidad, inicio, finalizacion = paciente print(f"Paciente {i}: En el día {h+1}, operado por el cirujano {cirujano+1}, en el quirófano {j+1}, duración {duracion:.2f} minutos. Inicio: {inicio}, Finalización: {finalizacion}, OR_ELIG: {eligibilidad}") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones y el tiempo de ejecución del código print("\nValor de la función objetivo de la mejor solución:", mejor_fo_global) print(f'Tiempo de ejecución: {tiempo_ejecucion:.2f} segundos') # Imprimir la lista de espera de la mejor solución encontrada entre todas las iteraciones print("\nLa lista de espera de la mejor solución:", mejor_PI_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #Eficiencia del algoritmo print(f"\nGracias al algoritmo se ha conseguido mejorar la solución {contador_glob} veces.") # Llamar a la función para exportar los datos exportar_a_excel(mejor_solucion_global, cirujanos_operaciones_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global) 67 67 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas ACO con ILS: Actualización de feromonas en todas las hormigas import numpy as np import json import pandas as pd import time import sys sys.path.append('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/FINALES') from decoding import firstfit # Importar la función # Inicialización del generador de números aleatorios rg = np.random.default_rng(2) # Función para convertir los datos de pacientes asignados en un DataFrame def convertir_pacientes_asignados_a_dataframe(pacientes_asignados): columnas = ['Paciente ID', 'Quirófano', 'Día', 'Cirujano', 'Duración', 'OR_ELIG', 'Inicio', 'Finalización'] data = [] for paciente in pacientes_asignados: data.append(list(paciente)) df_pacientes = pd.DataFrame(data, columns=columnas) return df_pacientes # Función para convertir los datos de cirujanos a un DataFrame def convertir_cirujanos_a_dataframe(cirujanos_operaciones): data = {'Cirujano': range(1, len(cirujanos_operaciones) + 1), 'Operaciones': cirujanos_operaciones} df_cirujanos = pd.DataFrame(data) return df_cirujanos # Exportar los datos a un archivo Excel def exportar_a_excel(mejor_solucion, cirujanos_operaciones, mejor_fo, mejor_PI, pacientes_operados): # Convertir los datos a DataFrames df_pacientes = convertir_pacientes_asignados_a_dataframe(mejor_solucion) df_cirujanos = convertir_cirujanos_a_dataframe(cirujanos_operaciones) # Crear un ExcelWriter para escribir en el archivo Excel with pd.ExcelWriter('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/Calibracion_fi nal/Resultados/resultados_ACO_ILS_todas.xlsx') as writer: df_pacientes.to_excel(writer, sheet_name='Pacientes Asignados', index=False) df_cirujanos.to_excel(writer, sheet_name='Cirujanos Operaciones', index=False) # Agregar los valores de la función objetivo y otros detalles detalles = { 'Valor de la Función Objetivo': [mejor_fo], 'Número de Pacientes Operados': [pacientes_operados] } df_detalles = pd.DataFrame(detalles) df_detalles.to_excel(writer, sheet_name='Detalles', index=False) # Crear un DataFrame para los valores de la función objetivo de cada instancia Anexos 74 74 print(f"\nSe ha actualizado la solución con los parámetros {jv}-{beta}-{alfa}-{mds} en la instancia {z}:") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones print("\nValor de la función objetivo de la nueva mejor solución global:", mejor_fo_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #print(f"\nInstancia: {z+1}, Parametros: {jv}-{beta}- {alfa}-{mds}") #print(f"Número de pacientes operados: {pacientes_operados}") #print(f"Número total de cirugías: {np.sum(cirujanos_operaciones)}") #print(f"Carga de trabajo equilibrada: {mejor_fo}\n") #print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones) # Medir tiempo de finalización tiempo_final = time.time() tiempo_ejecucion = tiempo_final - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las iteraciones print(f"\nMejor solución encontrada: Con los parámetros {jv_global}- {beta_global}-{alfa_global}-{mds_global}") print(f"\nEl número de pacientes en la lista de espera de esta solución es de {num_pacientes_global}\n") for idx, paciente in enumerate(mejor_solucion_global, start=1): i, j, h, cirujano, duracion, eligibilidad, inicio, finalizacion = paciente print(f"Paciente {i}: En el día {h+1}, operado por el cirujano {cirujano+1}, en el quirófano {j+1}, duración {duracion:.2f} minutos. Inicio: {inicio}, Finalización: {finalizacion}, OR_ELIG: {eligibilidad}") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones y el tiempo de ejecución del código print("\nValor de la función objetivo de la mejor solución:", mejor_fo_global) print(f'Tiempo de ejecución: {tiempo_ejecucion:.2f} segundos') # Imprimir la lista de espera de la mejor solución encontrada entre todas las iteraciones print("\nLa lista de espera de la mejor solución:", mejor_PI_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #Eficiencia del algoritmo 75 75 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas print(f"\nGracias al algoritmo se ha conseguido mejorar la solución {contador_glob} veces.") # Llamar a la función para exportar los datos exportar_a_excel(mejor_solucion_global, cirujanos_operaciones_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global) Anexos 76 76 ACO con ILS: Actualización de feromonas en la mejor hormiga de cada iteración import numpy as np import json import pandas as pd import time import sys sys.path.append('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/FINALES') from decoding import firstfit # Importar la función # Inicialización del generador de números aleatorios rg = np.random.default_rng(2) # Función para convertir los datos de pacientes asignados en un DataFrame def convertir_pacientes_asignados_a_dataframe(pacientes_asignados): columnas = ['Paciente ID', 'Quirófano', 'Día', 'Cirujano', 'Duración', 'OR_ELIG', 'Inicio', 'Finalización'] data = [] for paciente in pacientes_asignados: data.append(list(paciente)) df_pacientes = pd.DataFrame(data, columns=columnas) return df_pacientes # Función para convertir los datos de cirujanos a un DataFrame def convertir_cirujanos_a_dataframe(cirujanos_operaciones): data = {'Cirujano': range(1, len(cirujanos_operaciones) + 1), 'Operaciones': cirujanos_operaciones} df_cirujanos = pd.DataFrame(data) return df_cirujanos # Exportar los datos a un archivo Excel def exportar_a_excel(mejor_solucion, cirujanos_operaciones, mejor_fo, mejor_PI, pacientes_operados): # Convertir los datos a DataFrames df_pacientes = convertir_pacientes_asignados_a_dataframe(mejor_solucion) df_cirujanos = convertir_cirujanos_a_dataframe(cirujanos_operaciones) # Crear un ExcelWriter para escribir en el archivo Excel with pd.ExcelWriter('C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/Calibracion_fi nal/Resultados/resultados_ACO_ILS_iter.xlsx') as writer: df_pacientes.to_excel(writer, sheet_name='Pacientes Asignados', index=False) df_cirujanos.to_excel(writer, sheet_name='Cirujanos Operaciones', index=False) # Agregar los valores de la función objetivo y otros detalles detalles = { 'Valor de la Función Objetivo': [mejor_fo], 'Número de Pacientes Operados': [pacientes_operados] } df_detalles = pd.DataFrame(detalles) df_detalles.to_excel(writer, sheet_name='Detalles', index=False) 77 77 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Crear un DataFrame para los valores de la función objetivo de cada instancia df_instancias = pd.DataFrame(datos_instancias, columns=['JV', 'Beta', 'Alfa', 'MDS','Instancia', 'FO', 'Pacientes operados', 'Actualizaciones FO','Iteraciones realizadas del algoritmo']) # Agregar los valores de la función objetivo de las instancias a una nueva pestaña df_instancias.to_excel(writer, sheet_name='Valores FO', index=False) def leer_datos_desde_archivo(archivo): with open(archivo, 'r') as file: # Leer los datos desde el archivo data = file.readlines() h = int(data[0].split('=')[1]) j = int(data[1].split('=')[1]) i = int(data[2].split('=')[1]) s = int(data[3].split('=')[1]) r_jh = int(data[4].split('=')[1]) lista_espera = json.loads(data[5].split('=')[1]) OR_ELIG = json.loads(data[6].split('=')[1]) a_sh = json.loads(data[7].split('=')[1]) u_s = int(data[8].split('=')[1]) return h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s def equilibrar_carga2(cirujanos_operaciones): # Calcula la diferencia entre la media de operaciones y la cantidad de operaciones de cada cirujano media_operaciones = sum(cirujanos_operaciones) / len(cirujanos_operaciones) suma_diferencias = sum(abs(op - media_operaciones) for op in cirujanos_operaciones) return suma_diferencias def actualizar_probabilidades(lista_espera, pacientes_asignados, feromonas, probabilidades): # Inicialización de probabilidades con valores uniformes # Actualizar las probabilidades para cada paciente en función de las feromonas actualizadas for idx, paciente in enumerate(pacientes_asignados): paciente_id = paciente[0] # ID original del paciente posicion_asignada = idx feromonas_paciente = feromonas[paciente_id, posicion_asignada] # Feromonas asociadas con el paciente suma_feromonas_paciente = sum(feromonas[paciente_id, :]) # Suma de las feromonas del paciente en todas las posiciones # Verificar si hay feromonas asociadas con el paciente if suma_feromonas_paciente > 0: # Actualizar las probabilidades sumando el cálculo de las feromonas probabilidades[paciente_id, posicion_asignada] += feromonas_paciente / suma_feromonas_paciente return probabilidades Anexos 78 78 def actualizar_probabilidades1(lista_espera, feromonas, probabilidades): # Inicialización de probabilidades con valores uniformes probabilidades = np.full((i, len(lista_espera)), 1 / len(lista_espera)) # Actualizar las probabilidades para cada paciente en función de las feromonas actualizadas for idx in range(lista_espera): paciente_id = idx # ID original del paciente for pos in range(lista_espera): posicion_asignada = pos feromonas_paciente = feromonas[paciente_id, posicion_asignada] # Feromonas asociadas con el paciente suma_feromonas_paciente = sum(feromonas[paciente_id, :]) # Suma de las feromonas del paciente en todas las posiciones # Verificar si hay feromonas asociadas con el paciente if suma_feromonas_paciente > 0: # Actualizar las probabilidades sumando el cálculo de las feromonas probabilidades[paciente_id, posicion_asignada] += feromonas_paciente / suma_feromonas_paciente return probabilidades def actualizar_feromonas(feromonas, pacientes_asignados, calidad_solucion, deposito_factor, lista_espera): # Evaporación de feromonas feromonas *= (1 - evaporacion_factor) # Depósito de feromonas en las posiciones asignadas en la mejor solución encontrada for idx, paciente in enumerate(pacientes_asignados): paciente_id = paciente[0] # ID original del paciente posicion_asignada = idx if calidad_solucion == 0: feromonas[paciente_id, posicion_asignada] += deposito_factor else: feromonas[paciente_id, posicion_asignada] += deposito_factor / calidad_solucion return feromonas def actualizar_lista_espera(lista_espera, probabilidades): lista_espera_actualizada = [] for j in range(probabilidades.shape[1]): assigned_patient = False while not assigned_patient: # Normalizar las probabilidades para asegurarse de que sumen 1 normalized_probs = probabilidades[:, j] / np.sum(probabilidades[:, j]) # Escoger aleatoriamente un paciente en función de las probabilidades normalizadas idx_selected = np.random.choice(range(probabilidades.shape[0]), p=normalized_probs) # Verificar si el paciente ya está en la lista de espera actualizada if lista_espera[idx_selected] not in lista_espera_actualizada: lista_espera_actualizada.append(lista_espera[idx_selected]) assigned_patient = True return lista_espera_actualizada 79 79 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas def algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor, tamaño_vecindad, num_iteraciones_ILS): print(z) iteraciones = 0 tiempo_maximo_iter = i * j * h * 0.0125 tiempo_inicio_iter = time.time() mejor_solucion_global = None mejor_fo_global = float('inf') mejor_PI_global = None pacientes_operados_global = None cirujanos_operaciones_global = None contador = 0 feromonas = np.ones((i, len(lista_espera))) # Inicialización de feromonas probabilidades = np.full((i, len(lista_espera)), 1 / len(lista_espera)) pacientes_asignados = [] primera = True while (time.time() - tiempo_inicio_iter) < tiempo_maximo_iter: mejor_solucion_iter = None mejor_fo_iter = float('inf') pacientes_operados_iter = None for hormiga in range(num_hormigas): if primera == True: probabilidades = probabilidades primera = False else: probabilidades = actualizar_probabilidades(lista_espera, pacientes_asignados, feromonas, probabilidades) # Actualizar lista de espera con las probabilidades calculadas lista_espera = actualizar_lista_espera(lista_espera, probabilidades) pacientes_asignados, cirujanos_operaciones, cirujanos_quirofanos_asignados, pacientes_operados = firstfit(lista_espera, OR_ELIG, j, h, r_jh, s, a_sh, u_s) fo = equilibrar_carga2(cirujanos_operaciones) #Actualizar mejor solución local if fo < mejor_fo_iter: mejor_solucion_iter = pacientes_asignados mejor_fo_iter = fo pacientes_operados_iter = pacientes_operados if fo == mejor_fo_iter: if pacientes_operados > pacientes_operados_iter: mejor_solucion_iter = pacientes_asignados mejor_fo_iter = fo pacientes_operados_iter = pacientes_operados # Actualización la mejor solución global si encontramos una mejor if fo < mejor_fo_global: mejor_solucion_global = pacientes_asignados mejor_fo_global = fo mejor_PI_global = lista_espera pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 Anexos 80 80 if fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = pacientes_asignados mejor_fo_global = fo mejor_PI_global = lista_espera pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 for _ in range(num_iteraciones_ILS): # Aplicar búsqueda local iterada (ILS) a la mejor solución encontrada por la colonia de hormigas en esta iteración mejor_solucion, mejor_fo, mejor_PI, pacientes_operados, cirujanos_operaciones, feromonas = ILS(OR_ELIG, mejor_solucion_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global, cirujanos_operaciones_global, tamaño_vecindad, feromonas) if fo < mejor_fo_iter: mejor_solucion_iter = pacientes_asignados mejor_fo_iter = fo # Actualizar la mejor solución global si encontramos una mejor if mejor_fo < mejor_fo_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo mejor_PI_global = mejor_PI pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 if mejor_fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo mejor_PI_global = mejor_PI pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones contador += 1 # Actualizar feromonas con las mejores soluciones encontradas en cada iteración feromonas = actualizar_feromonas(feromonas, mejor_solucion_iter, mejor_fo_iter, deposito_factor, lista_espera) iteraciones +=1 return iteraciones, mejor_solucion_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global, cirujanos_operaciones_global, contador def ILS(OR_ELIG, mejor_solucion, mejor_fo, mejor_PI, pacientes_operados, cirujanos_operaciones, tamaño_vecindad, feromonas): # Inicializar la mejor solución local mejor_PI_local = mejor_PI mejor_fo_local = mejor_fo mejor_solucion_local = mejor_solucion pacientes_operados_local = pacientes_operados cirujanos_operaciones_local = cirujanos_operaciones 81 81 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Realizar la búsqueda local iterada (ILS) for _ in range(tamaño_vecindad): # Perturbar la lista de espera PI_pert = perturbar_lista_espera(mejor_PI, tamaño_vecindad) # Evaluar la lista de espera perturbada pacientes_asignados_pert, cirujanos_operaciones_pert, cirujanos_quirofanos_asignados_pert, pacientes_operados_pert = firstfit(PI_pert, OR_ELIG, j, h, r_jh, s, a_sh, u_s) fo_perturbada = equilibrar_carga2(cirujanos_operaciones_pert) # Actualizar la mejor solución local si encontramos una mejor if fo_perturbada < mejor_fo_local: mejor_PI_local = PI_pert mejor_fo_local = fo_perturbada mejor_solucion_local = pacientes_asignados_pert pacientes_operados_local = pacientes_operados_pert cirujanos_operaciones_local = cirujanos_operaciones_pert if fo_perturbada == mejor_fo_local: if pacientes_operados_pert > pacientes_operados_local: mejor_PI_local = PI_pert mejor_fo_local = fo_perturbada mejor_solucion_local = pacientes_asignados_pert pacientes_operados_local = pacientes_operados_pert cirujanos_operaciones_local = cirujanos_operaciones_pert return mejor_solucion_local, mejor_fo_local, mejor_PI_local, pacientes_operados_local, cirujanos_operaciones_local, feromonas def perturbar_lista_espera(lista_espera, tamaño_vecindad): # Crear una copia de la lista de espera original lista_espera_perturbada = lista_espera.copy() # Seleccionar un paciente aleatorio de la lista de espera idx = rg.integers(0, len(lista_espera)) # Seleccionar un índice aleatorio # Generar una lista de vecinos para el paciente seleccionado vecindad = [i for i in range(len(lista_espera)) if i != idx] # Elegir aleatoriamente un tamaño de vecindad dentro del límite establecido tamaño_vecindad = min(tamaño_vecindad, len(vecindad)) # Seleccionar aleatoriamente un subconjunto de la vecindad vecindad_seleccionada = rg.choice(vecindad, tamaño_vecindad, replace=False) # Seleccionar aleatoriamente un vecino dentro de la vecindad seleccionada vecino = rg.choice(vecindad_seleccionada) # Intercambiar el paciente seleccionado con el vecino seleccionado lista_espera_perturbada[idx], lista_espera_perturbada[vecino] = lista_espera_perturbada[vecino], lista_espera_perturbada[idx] return lista_espera_perturbada # Medir tiempo de ejecución Anexos 82 82 tiempo_inicio = time.time() # Datos del problema j_values = [3, 9] beta_values = [1, 1.25] alfa_values = [1.5, 2] mds_values = [3, 4] instancias = 10 mejor_solucion_global = None mejor_fo_global = float('inf') pacientes_operados_global = None cirujanos_operaciones_global = None mejor_PI_global = None num_pacientes_global = float('inf') num_quirof_global = float('inf') num_cirujanos_global = float('inf') # Almacenar los valores de la función objetivo de cada instancia datos_instancias = [] contador_glob = 0 for jv in j_values: for beta in beta_values: for alfa in alfa_values: for mds in mds_values: for z in range(instancias): archivo = f'C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/DATOS/PROBLEMA_{jv}_{beta}_{ alfa}_{mds}_{z}.txt' h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s = leer_datos_desde_archivo(archivo) # Parámetros para el algoritmo de colonia de hormigas num_hormigas = 500 #se puede aumentar para que haya mas actualizaciones en cada iteración evaporacion_factor = 0.1 # Factor de evaporación de feromonas deposito_factor = 1.0 # Factor de depósito de feromonas tamaño_vecindad = 10 # Tamaño de la vecindad para la búsqueda local iterada num_iteraciones_ILS = 1 # Número de iteraciones de la búsqueda local iterada contador_local = 0 iteraciones_instancia = 0 # Ejecutar algoritmo de colonia de hormigas con búsqueda local iterada iteraciones, mejor_solucion, mejor_fo, mejor_PI, pacientes_operados, cirujanos_operaciones, contador = algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor, tamaño_vecindad, num_iteraciones_ILS) contador_glob += contador contador_local += contador iteraciones_instancia += iteraciones # Almacenar el valor de la función objetivo de esta instancia 83 83 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas datos_instancias.append((jv, beta, alfa, mds, z+1, round(mejor_fo,2), pacientes_operados, contador_local, iteraciones_instancia)) cambio = False # Actualizar la mejor solución global si encontramos una mejor if mejor_fo < mejor_fo_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if mejor_fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if cambio == True: tiempo_mejor = time.time() - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las instancias para los parámetros actuales print(f"\nSe ha actualizado la solución con los parámetros {jv}-{beta}-{alfa}-{mds} en la instancia {z}:") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones print("\nValor de la función objetivo de la nueva mejor solución global:", mejor_fo_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) Anexos 90 90 cirujanos_operaciones_local = cirujanos_operaciones_pert return mejor_solucion_local, mejor_fo_local, mejor_PI_local, pacientes_operados_local, cirujanos_operaciones_local, feromonas def perturbar_lista_espera(lista_espera, tamaño_vecindad): # Crear una copia de la lista de espera original lista_espera_perturbada = lista_espera.copy() # Seleccionar un paciente aleatorio de la lista de espera idx = rg.integers(0, len(lista_espera)) # Seleccionar un índice aleatorio # Generar una lista de vecinos para el paciente seleccionado vecindad = [i for i in range(len(lista_espera)) if i != idx] # Elegir aleatoriamente un tamaño de vecindad dentro del límite establecido tamaño_vecindad = min(tamaño_vecindad, len(vecindad)) # Seleccionar aleatoriamente un subconjunto de la vecindad vecindad_seleccionada = rg.choice(vecindad, tamaño_vecindad, replace=False) # Seleccionar aleatoriamente un vecino dentro de la vecindad seleccionada vecino = rg.choice(vecindad_seleccionada) # Intercambiar el paciente seleccionado con el vecino seleccionado lista_espera_perturbada[idx], lista_espera_perturbada[vecino] = lista_espera_perturbada[vecino], lista_espera_perturbada[idx] return lista_espera_perturbada # Medir tiempo de ejecución tiempo_inicio = time.time() # Datos del problema j_values = [3, 9] beta_values = [1, 1.25] alfa_values = [1.5, 2] mds_values = [3, 4] instancias = 10 mejor_solucion_global = None mejor_fo_global = float('inf') pacientes_operados_global = None cirujanos_operaciones_global = None mejor_PI_global = None num_pacientes_global = float('inf') num_quirof_global = float('inf') num_cirujanos_global = float('inf') # Almacenar los valores de la función objetivo de cada instancia datos_instancias = [] contador_glob = 0 for jv in j_values: 91 91 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas for beta in beta_values: for alfa in alfa_values: for mds in mds_values: for z in range(instancias): archivo = f'C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/DATOS/PROBLEMA_{jv}_{beta}_{ alfa}_{mds}_{z}.txt' h, j, i, s, r_jh, lista_espera, OR_ELIG, a_sh, u_s = leer_datos_desde_archivo(archivo) # Parámetros para el algoritmo de colonia de hormigas num_hormigas = 500 #se puede aumentar para que haya mas actualizaciones en cada iteración evaporacion_factor = 0.1 # Factor de evaporación de feromonas deposito_factor = 1.0 # Factor de depósito de feromonas tamaño_vecindad = 10 # Tamaño de la vecindad para la búsqueda local iterada num_iteraciones_ILS = 1 # Número de iteraciones de la búsqueda local iterada contador_local = 0 iteraciones_instancia = 0 # Ejecutar algoritmo de colonia de hormigas con búsqueda local iterada iteraciones, mejor_solucion, mejor_fo, mejor_PI, pacientes_operados, cirujanos_operaciones, contador = algoritmo_colonia_hormigas(OR_ELIG, lista_espera, i, j, h, r_jh, s, a_sh, u_s, num_hormigas, evaporacion_factor, deposito_factor, tamaño_vecindad, num_iteraciones_ILS) contador_glob += contador contador_local += contador iteraciones_instancia += iteraciones # Almacenar el valor de la función objetivo de esta instancia datos_instancias.append((jv, beta, alfa, mds, z+1, round(mejor_fo,2), pacientes_operados, contador_local, iteraciones_instancia)) cambio = False # Actualizar la mejor solución global si encontramos una mejor if mejor_fo < mejor_fo_global: mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if mejor_fo == mejor_fo_global: if pacientes_operados > pacientes_operados_global: Anexos 92 92 mejor_solucion_global = mejor_solucion mejor_fo_global = mejor_fo pacientes_operados_global = pacientes_operados cirujanos_operaciones_global = cirujanos_operaciones mejor_PI_global = mejor_PI num_pacientes_global = len(lista_espera) num_quirof_global = j num_cirujanos_global = s jv_global = jv beta_global = beta alfa_global = alfa mds_global = mds cambio = True if cambio == True: tiempo_mejor = time.time() - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las instancias para los parámetros actuales print(f"\nSe ha actualizado la solución con los parámetros {jv}-{beta}-{alfa}-{mds} en la instancia {z}:") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones print("\nValor de la función objetivo de la nueva mejor solución global:", mejor_fo_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #print(f"\nInstancia: {z+1}, Parametros: {jv}-{beta}- {alfa}-{mds}") #print(f"Número de pacientes operados: {pacientes_operados}") #print(f"Número total de cirugías: {np.sum(cirujanos_operaciones)}") #print(f"Carga de trabajo equilibrada: {mejor_fo}\n") #print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones) # Medir tiempo de finalización tiempo_final = time.time() tiempo_ejecucion = tiempo_final - tiempo_inicio # Imprimir la mejor solución encontrada entre todas las iteraciones print(f"\nMejor solución encontrada: Con los parámetros {jv_global}- {beta_global}-{alfa_global}-{mds_global}") print(f"\nEl número de pacientes en la lista de espera de esta solución es de {num_pacientes_global}\n") for idx, paciente in enumerate(mejor_solucion_global, start=1): i, j, h, cirujano, duracion, eligibilidad, inicio, finalizacion = paciente 93 93 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas print(f"Paciente {i}: En el día {h+1}, operado por el cirujano {cirujano+1}, en el quirófano {j+1}, duración {duracion:.2f} minutos. Inicio: {inicio}, Finalización: {finalizacion}, OR_ELIG: {eligibilidad}") # Imprimir el valor de la función objetivo de la mejor solución encontrada entre todas las iteraciones y el tiempo de ejecución del código print("\nValor de la función objetivo de la mejor solución:", mejor_fo_global) print(f'Tiempo de ejecución: {tiempo_ejecucion:.2f} segundos') # Imprimir la lista de espera de la mejor solución encontrada entre todas las iteraciones print("\nLa lista de espera de la mejor solución:", mejor_PI_global) # Imprimir resultados adicionales para la mejor solución global print("\nNúmero de pacientes operados en la mejor solución:", pacientes_operados_global) print("\nCantidad de pacientes operados por cada cirujano en la mejor solución:", cirujanos_operaciones_global) #Eficiencia del algoritmo print(f"\nGracias al algoritmo se ha conseguido mejorar la solución {contador_glob} veces.") # Llamar a la función para exportar los datos exportar_a_excel(mejor_solucion_global, cirujanos_operaciones_global, mejor_fo_global, mejor_PI_global, pacientes_operados_global) Anexos 94 94 Decoding import numpy as np def bestfit(lista_espera, OR_ELIG, j_set, h_set, r_jh, s_set, a_sh, u_s): pacientes_asignados = [] cirujanos_operaciones = [0] * s_set tiempo_cirugia = np.zeros((s_set, h_set), dtype=int) tiempo_acumulado = np.zeros((j_set, h_set), dtype=int) cirujanos_quirofanos_asignados = np.zeros((s_set, j_set, h_set), dtype=int) pacientes_ya_asignados = set() pacientes_operados = 0 for paciente_params in lista_espera: paciente_id = paciente_params['ID'] cirujano = paciente_params['Cirujano'] t_i = paciente_params['Tiempo de Cirugia'] dia_minimo = int(paciente_params['Dia minimo operar']) dia_maximo = int(paciente_params['Dia maximo operar']) # Diccionario para almacenar la cantidad de tiempo disponible en cada quirófano tiempo_disponible_quirofano = {} for dia_h in range(dia_minimo, min(dia_maximo + 1, h_set)): for quir_j in range(j_set): # Verificar si el quirófano está disponible para la cirugía if np.sum([p[2] == dia_h and p[1] == quir_j for p in pacientes_asignados]) * t_i < r_jh and cirujanos_quirofanos_asignados[cirujano, :, dia_h].sum() < u_s: if OR_ELIG[paciente_id][quir_j][dia_h] == 1 and paciente_id not in pacientes_ya_asignados: inicio = max([p[6] for p in pacientes_asignados if p[1] == quir_j and p[2] == dia_h], default=0) inicio = max(inicio, tiempo_acumulado[quir_j, dia_h]) finalizacion = inicio + t_i # Verificar si el cirujano está ocupado en otro quirófano en el mismo día if any([p[3] == cirujano and p[2] == dia_h and ((p[6] <= inicio and p[7] >= inicio) or (p[6] >= inicio and p[6] < finalizacion)) for p in pacientes_asignados]): continue if finalizacion <= r_jh: # Calcula el tiempo disponible en este quirófano y día tiempo_disponible = r_jh - tiempo_cirugia[cirujano][dia_h] # Si este quirófano aún no está en el diccionario o si el tiempo disponible es menor que el registrado anteriormente, actualiza el valor if (quir_j, dia_h) not in tiempo_disponible_quirofano or tiempo_disponible < tiempo_disponible_quirofano[(quir_j, dia_h)]: tiempo_disponible_quirofano[(quir_j, dia_h)] = tiempo_disponible 95 95 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Si se encontró algún quirófano disponible, asigna la cirugía al que tenga el menor tiempo disponible if tiempo_disponible_quirofano: mejor_quirofano, mejor_dia = min(tiempo_disponible_quirofano, key=tiempo_disponible_quirofano.get) inicio = max([p[6] for p in pacientes_asignados if p[1] == mejor_quirofano and p[2] == mejor_dia], default=0) inicio = max(inicio, tiempo_acumulado[mejor_quirofano, mejor_dia]) finalizacion = inicio + t_i # Verificar si el cirujano está ocupado en otro quirófano en el mismo día if any([p[3] == cirujano and p[2] == dia_h and ((p[6] <= inicio and p[7] >= inicio) or (p[6] >= inicio and p[6] < finalizacion)) for p in pacientes_asignados]): continue # Asignar la cirugía pacientes_asignados.append((paciente_id, mejor_quirofano, mejor_dia, cirujano, t_i, OR_ELIG[paciente_id][mejor_quirofano][mejor_dia], inicio, finalizacion)) cirujanos_operaciones[cirujano] += 1 tiempo_cirugia[cirujano][mejor_dia] += t_i tiempo_acumulado[mejor_quirofano, mejor_dia] = finalizacion cirujanos_quirofanos_asignados[cirujano, mejor_quirofano, mejor_dia] = 1 pacientes_ya_asignados.add(paciente_id) pacientes_operados += 1 # Ordenar la lista de pacientes asignados pacientes_asignados.sort(key=lambda x: (x[2], x[1], x[6])) # Retornar los resultados return pacientes_asignados, cirujanos_operaciones, cirujanos_quirofanos_asignados, pacientes_operados def firstfit(lista_espera, OR_ELIG, j_set, h_set, r_jh, s_set, a_sh, u_s): pacientes_asignados = [] cirujanos_operaciones = [0] * s_set tiempo_cirugia = np.zeros((s_set, h_set), dtype=int) tiempo_acumulado = np.zeros((j_set, h_set), dtype=int) cirujanos_quirofanos_asignados = np.zeros((s_set, j_set, h_set), dtype=int) pacientes_ya_asignados = set() pacientes_operados = 0 for paciente_params in lista_espera: paciente_id = paciente_params['ID'] cirujano = paciente_params['Cirujano'] t_i = paciente_params['Tiempo de Cirugia'] dia_minimo = int(paciente_params['Dia minimo operar']) dia_maximo = int(paciente_params['Dia maximo operar']) for dia_h in range(dia_minimo, min(dia_maximo + 1, h_set)): cirujanos_disponibles = [s for s in range(s_set) if a_sh[s][dia_h] >= t_i and tiempo_cirugia[s][dia_h] <= a_sh[s][dia_h]] if cirujanos_disponibles: Anexos 96 96 for quir_j in range(j_set): if np.sum([p[2] == dia_h and p[1] == quir_j for p in pacientes_asignados]) * t_i < r_jh and cirujanos_quirofanos_asignados[cirujano, :, dia_h].sum() < u_s: if OR_ELIG[paciente_id][quir_j][dia_h] == 1 and paciente_id not in pacientes_ya_asignados: inicio = max([p[6] for p in pacientes_asignados if p[1] == quir_j and p[2] == dia_h], default=0) inicio = max(inicio, tiempo_acumulado[quir_j, dia_h]) # Verifica si el cirujano está ocupado en otro quirófano en el mismo día if any([p[3] == cirujano and p[2] == dia_h and p[6] < inicio for p in pacientes_asignados]): inicio = max([p[7] for p in pacientes_asignados if p[3] == cirujano and p[2] == dia_h and p[6] < inicio], default=inicio) finalizacion = inicio + t_i if finalizacion <= r_jh: pacientes_asignados.append((paciente_id, quir_j, dia_h, cirujano, t_i, OR_ELIG[paciente_id][quir_j][dia_h], inicio, finalizacion)) cirujanos_operaciones[cirujano] += 1 tiempo_cirugia[cirujano][dia_h] += t_i tiempo_acumulado[quir_j, dia_h] = finalizacion cirujanos_quirofanos_asignados[cirujano, quir_j, dia_h] = 1 pacientes_ya_asignados.add(paciente_id) pacientes_operados += 1 break pacientes_asignados.sort(key=lambda x: (x[2], x[1], x[6])) return pacientes_asignados, cirujanos_operaciones, cirujanos_quirofanos_asignados, pacientes_operados def nextfit(lista_espera, OR_ELIG, j_set, h_set, r_jh, s_set, a_sh, u_s): #the surgery is planned in the last OR-day occupied, if possible.Otherwise,the surgery is planned into the next availableOR-day. # Inicialización de variables pacientes_asignados = [] cirujanos_operaciones = [0] * s_set tiempo_cirugia = np.zeros((s_set, h_set), dtype=int) tiempo_acumulado = np.zeros((j_set, h_set), dtype=int) cirujanos_quirofanos_asignados = np.zeros((s_set, j_set, h_set), dtype=int) pacientes_ya_asignados = set() pacientes_operados = 0 # Iterar sobre los pacientes en lista de espera for paciente_params in lista_espera: paciente_id = paciente_params['ID'] cirujano = paciente_params['Cirujano'] t_i = paciente_params['Tiempo de Cirugia'] dia_minimo = int(paciente_params['Dia minimo operar']) dia_maximo = int(paciente_params['Dia maximo operar']) 97 97 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas # Iterar sobre los días disponibles para programar la cirugía for dia_h in range(dia_minimo, min(dia_maximo + 1, h_set)): # Iterar sobre los quirófanos disponibles for quir_j in range(j_set): # Verificar si es posible asignar la cirugía en este quirófano y día if (np.sum([p[2] == dia_h and p[1] == quir_j for p in pacientes_asignados]) * t_i < r_jh and a_sh[cirujano][dia_h] >= tiempo_cirugia[cirujano][dia_h] + t_i and cirujanos_quirofanos_asignados[cirujano, :, dia_h].sum() < u_s): if OR_ELIG[paciente_id][quir_j][dia_h] == 1 and paciente_id not in pacientes_ya_asignados: quir_dias_ocupados = [p[2] for p in pacientes_asignados if p[1] == quir_j] # Si hay días ocupados en este quirófano if quir_dias_ocupados: ultimo_dia_ocupado = max(quir_dias_ocupados) # Si el día actual es el último día ocupado, asignar aquí if dia_h == ultimo_dia_ocupado: inicio = max([p[6] for p in pacientes_asignados if p[1] == quir_j and p[2] == dia_h], default=0) inicio = max(inicio, tiempo_acumulado[quir_j, dia_h]) finalizacion = inicio + t_i if finalizacion <= r_jh: # Asignar la cirugía pacientes_asignados.append((paciente_id, quir_j, dia_h, cirujano, t_i, OR_ELIG[paciente_id][quir_j][dia_h], inicio, finalizacion)) cirujanos_operaciones[cirujano] += 1 tiempo_cirugia[cirujano][dia_h] += t_i tiempo_acumulado[quir_j, dia_h] = finalizacion cirujanos_quirofanos_asignados[cirujano, quir_j, dia_h] = 1 pacientes_ya_asignados.add(paciente_id) pacientes_operados += 1 break # Si no hay días ocupados en este quirófano, asignar aquí else: inicio = max([p[6] for p in pacientes_asignados if p[1] == quir_j and p[2] == dia_h], default=0) inicio = max(inicio, tiempo_acumulado[quir_j, dia_h]) finalizacion = inicio + t_i if finalizacion <= r_jh: # Asignar la cirugía pacientes_asignados.append((paciente_id, quir_j, dia_h, cirujano, t_i, OR_ELIG[paciente_id][quir_j][dia_h], inicio, finalizacion)) cirujanos_operaciones[cirujano] += 1 tiempo_cirugia[cirujano][dia_h] += t_i tiempo_acumulado[quir_j, dia_h] = finalizacion Anexos 98 98 cirujanos_quirofanos_asignados[cirujano, quir_j, dia_h] = 1 pacientes_ya_asignados.add(paciente_id) pacientes_operados += 1 break # Ordenar la lista de pacientes asignados pacientes_asignados.sort(key=lambda x: (x[2], x[1], x[6])) # Retornar los resultados return pacientes_asignados, cirujanos_operaciones, cirujanos_quirofanos_asignados, pacientes_operados 99 99 Optimización quirúrgica para equilibrar la carga de trabajo de los cirujanos mediante algoritmos de colonia de hormigas ARPD import pandas as pd # Cargar el archivo file_path = 'C:/Users/luisa/OneDrive/Escritorio/TFG/Codigos/Calibracion_final/Resultados/ ARPD.xlsx' df = pd.read_excel(file_path) # Preparar la nueva tabla resultados = [] for index, row in df.iterrows(): instancia = row['Instancia'] df_instancia = df[df['Instancia'] == instancia] # Calcular las mejores y peores soluciones para esta fila best_sol = min(row['ACO TODAS FO'], row['ACO ITER FO'], row['ACO GLOBAL FO'], row['ACO ILS TODAS FO'],row['ACO ILS ITER FO'], row['ACO ILS GLOBAL FO']) worst_sol = max(row['ACO TODAS FO'], row['ACO ITER FO'], row['ACO GLOBAL FO'], row['ACO ILS TODAS FO'],row['ACO ILS ITER FO'], row['ACO ILS GLOBAL FO']) if worst_sol == best_sol: rpd_ACO_todas = 0 rpd_ACO_iter = 0 rpd_ACO_global = 0 rpd_ACO_ILS_todas = 0 rpd_ACO_ILS_iter = 0 rpd_ACO_ILS_global = 0 else: # Calcular el RPD para cada solución rpd_ACO_todas = ((row['ACO TODAS FO'] - best_sol) / (worst_sol - best_sol)) * 100 rpd_ACO_iter = ((row['ACO ITER FO'] - best_sol) / (worst_sol - best_sol)) * 100 rpd_ACO_global = ((row['ACO GLOBAL FO'] - best_sol) / (worst_sol - best_sol)) * 100 rpd_ACO_ILS_todas = ((row['ACO ILS TODAS FO'] - best_sol) / (worst_sol - best_sol)) * 100 rpd_ACO_ILS_iter = ((row['ACO ILS ITER FO'] - best_sol) / (worst_sol - best_sol)) * 100 rpd_ACO_ILS_global = ((row['ACO ILS GLOBAL FO'] - best_sol) / (worst_sol - best_sol)) * 100 # Añadir los resultados a la nueva tabla resultados.append({ 'JV': row['JV'], 'Beta': row['Beta'], 'Alfa': row['Alfa'], 'MDS': row['MDS'], 'Instancia': row['Instancia'], 'ACO TODAS FO': row['ACO TODAS FO'], 'ACO ITER FO': row['ACO ITER FO'], 'ACO GLOBAL FO': row['ACO GLOBAL FO'], 'ACO ILS TODAS FO': row['ACO ILS TODAS FO'], 'ACO ILS ITER FO': row['ACO ILS ITER FO'],