Better medical efficiency by means of hospital bed management optimization - a comparison of artificial intelligence techniques

1 Better Medical Efficiency by means of Hospital Bed Management Optimization – a Comparison of Artificial Intelligence Techniques Afonso Lobo1, Agostinho Barbosa2, Tiago Guimarães1, João Lopes1, Hugo Peixoto1, Manuel Filipe Santos1 1 Centro ALGORITMI, University of Minho, 4800-058 Guimarães, Portugal 2 Centro Hospitalar do Tâmega e Sousa, 4564-007, Penafiel, Portugal [email protected], [email protected] saude.pt, [email protected], [email protected], [email protected], [email protected] Abstract. The combination of the phenomenon of overcrowding with inefficient management of resources is a major obstacle to the good performance of hospital units and consequently the degradation of the medical service provided. This paper provides an analysis to understand the correlation between poor bed allocation and hospital performance. The lack of an efficient resource planning among the various medical specialties can negatively impact the quality of service. Four different techniques were compared to realize which is better suited for optimizing the allocation of beds in Hospital units. Hill Climbing and the Genetic Algorithm stood out the others, the latter presenting greater consistency and a shorter computation time. When tested with real data from Centro Hospitalar do Tâmega e Sousa, attained a total of 0 wrongly allocated patients against 92 when compared with former methods. This translates into better patient service, reduced waiting time and staff workload, which means increased performance in all adjacent medical issues. Keywords: Artificial Intelligence, Modern Optimization, Hospital Bed Management, Medical Efficiency. 1 INTRODUCTION Nowadays, more and more data regarding hospitals and all the surrounding area in the health sector are becoming available to us. This means an increasingly facilitated use of artificial intelligence techniques to seek a significant improvement in the efficiency of these services, from component optimization to efficient management of resources in the hospital units, contributing in a significant way to monetary cost reduction[1] The approach performed in this type of problem is called prescriptive analysis. It is an analysis with the purpose of responding to real decisions regarding the planning of resources in the hospital units as well as the allocation of certain medications depending on the context, always aiming to reach the best possible solution [2]. This study is centered on the development and comparison of Machine Learning Optimization Algorithms (MLOA), for intelligent and efficient management of beds in the different specialties of a hospital, corresponding in the best possible way to the needs of the hospital as a whole. The application of these algorithms is becoming more and more relevant as we are witnessing a global aging of the population which causes the flow of patients to be greater and the pressure on health services to increase. The result of this pressure, without proper planning, is an inefficient management and organization of hospital units, falling short of their needs and an increase in operating costs [3]. Adopting optimization algorithms to answer these questions and obtain the best possible planning has been one of the best answers to this type of problem, representing an increase in 2 performance in service delivery and operation of hospital units [4]. In the realization of this project as followed the approaches of Design Science Research. 2 BACKGROUND 2.1 Resources Planning in Hospital Settings A good planning of resources in health care units to guarantee an adequate response and performance to their needs is becoming increasingly difficult and therefore it becomes more pertinent to find ways to obtain a better use and optimization of resources through successful planning and management. The main obstacle to a good organization and management of resources in a hospital is due to the current phenomenon of overcrowding coupled with an inefficient management of resources, increasingly accentuating the underutilization of them, i.e. the flow of patients is too high for the response that hospitals can give, reducing the response capacity and consequent overcrowding [5]. According to a study conducted at the University of California, the main reasons for this Overcrowding are concentrated in the high volume of patients, the complexity of related medical issues, delays in the provision of services and mainly in the poor management and allocation of beds in hospitals being this factor considered as the one that represents more weight for the problem in question [6]. The inadequate allocation of beds is due, besides the lack of available beds, to an inefficient management of resources which causes a negative differential between the needs presented and the response capacity. This means that even in scenarios where the resources can meet the needs, occurs a suboptimal use of them resulting in loss of performance, causing delays and cancellation of admissions and surgeries, early transfers of patients and accumulation of costs[7]. To this end, it is important to find a form or model of organization based on two main variables: the occupancy of beds and the forecasting of patient flow, in order to obtain an efficient management of resources that allows the proper functioning of hospital institutions being able to provide adequate care to their patients to ensure a response capacity appropriate to the needs [5, 6]. 2.2 Related Work The planning and management of resources in hospital units represent a need and a pertinent concern in our days. We are therefore witnessing a systematic attempt to find the best possible solution that allows us to respond effectively to the problem of overcrowding using more efficient management of means. There are several studies proposing solutions and showing important characteristics to be considered to achieve the desired success. One way to promote efficient resource management in hospitals is the use of the Markov model. The Markov model, or strategy, is a mathematical queuing model intending to predict and improve the waiting time of patients for service. This approach was the target of a study published in Healthcare Engineering, where the focus was optimizing a model in order to obtain greater efficiency in bed allocation. This model was based on several indicators such as the average number of patients, bed utilization rate, patient stop rate, and patient average waiting time. Simulations and several experiments conducted with this model showed a significant improvement in resource allocation and overall patient satisfaction [8]. It was made in 2022 a study with the intent of predicting patient Length Of Stay (LOS) through machine learning models and input data regarding medical records and demographic information of patients in the internal medicine specialty of a hospital in Portugal. The authors followed two scenarios: one that predicts the LOS at the time of admission; and another that updates the prediction during the hospitalization process. They compared four machine learning algorithms: decision tree, random forest, k-nearest neighbors and gradient boosting. They found that gradient boosting performs the best, achieving an accuracy of about 96%. They also found that including data about the patient's health electronic record, such as exams, lab results, 3 medications and surgeries, improves the predictive capacity of the model. They concluded that their model can help health professionals plan and manage hospital resources more efficiently and improve the quality of care for patients [9] In 2020, In Brazil in Minas Gerais the use of optimization algorithms, more specifically a genetic algorithm, was also the target of study to improve the allocation of beds in hospitals in the region, proving, despite an increase of 13% in operating costs, a reduction up to 1/30 of the refusal patient rate [10]. Following the application of MLOA, more specifically the genetic algorithm, a study was conducted at Tous Hospital in Tehra based on patient flow data, a study aimed at optimizing the use of human resources in the hospital in question. The objective was to find a solution that represented the minimum optimal number of staff required to meet the needs of the hospital, thus leading to a reduction in waste, operating costs and an increase in the efficiency and effectiveness of the service provided, through a better distribution of staff hours. In the application of this algorithm, the fitness function, a constituent function of the algorithm, whose purpose is to attribute a certain score to a certain solution to the problem, took into consideration parameters such as the employee's salary, the number of patients seen on average per employee and the available work shifts. It was then, after 500 generations, found a solution for staff hourly allocation in which only 69 employees were needed compared to the 108 actives in function daily in the hospital, to give the same or better response to the needs presented [11]. When it comes to comparing optimization algorithms with each other, a study was conducted at the Fukuoka Institute in Japan, to evaluate the performance of algorithms such as Hill Climbing, Simulated Annealing and Genetic Algorithm for optimal allocation of routers in order to promote better coverage and connection conditions to Local Area Networks. From this study resulted an advantage of Hill Climbing and Simulated Annealing, showing to reach the desired results faster [12]. Following the performance comparison between the algorithms, a study was conducted in order to understand the behavior of the Hill Climbing and Genetic algorithms for digital predistortion model sizing. From this study it was concluded that the genetic algorithm is dependent on the input parameters, and that the larger the population size, the better the results, which also means a proportional increase in execution time. The Hill Climbing algorithm, on the other hand, does not depend on the input parameters and can present itself with a shorter execution time due to the increase in the population size of the genetic algorithm. As for the performance comparison regarding the quality of the solution obtained, the genetic algorithm reached the optimal solution more often, while the hill climbing also presented local optimal solutions, i.e., solutions close to the best possible solution, but not being so [13]. In the big picture we can observe several different ways to try to achieve a more efficient management of resources in hospitals. In most of the studies regarding the allocation of beds and resources in hospital units, factors such as the Length Of Stay (LOS) and the Occupation Rate are highlighted. The application of MLOA to solve this type of problems has been studied and its behavior is also observed, not only in allocation problems related to the Hospital industry but also in the application of several types of contexts. In this study the focus will be on the application of four different machine learning optimization algorithms with the objective of obtaining an optimal solution for the distribution of beds by the different specialties of the hospital, avoiding overcrowding. They will then be compared and concluded which one presents the greatest impact and significant improvement in the matter of medical issues. 3 MATERIALS AND METHODS 3.1 Methodologies The document was developed according to the Design Science Research methodology, a methodology with the objective of creating a framework to help solve and investigate problems. In this framework artifacts that generate new knowledge are generated and analyzed. This methodology is composed of six distinct phases: Problem Identification and Motivation(1), Defining the Objectives for the solution(2), Design and Development(3), Demonstration(4), Evaluation(5) and Communication(6) [14]. 4 3.2 Tools and Algorithms The development of this project was all based on the Python language and its respective libraries (NumPy, Pandas, Matplotlib, Math, DateTime). The development platform was Google's Colab. The algorithms used are Machine Learning Optimization Algorithms, highlighting, Random Search, Hill Climbing, Simulated Annealing, and Genetic/Evolutionary Algorithm. 3.3 Data Sets The datasets used are related to patient flow at the Centro Hospitalar do Tâmega e Sousa (CHTS) and its respective specialties, for a period corresponding to 4 years. This dataset contained information such as, admissions, discharges, respective days and times, number of specialty beds, which patients were allocated to each specialty and which patients were the responsible of each specialty, and also contained information about which days the patient was hospitalized in service, in a particular specialty 4 Experiments The following section describes the experiments in all their phases. 4.1 Problem Formulation The aim is to improve the misallocation of patients in different specialties due to poor management and planning of resources, specifically beds. The inefficiency on management leads to an underutilization of resources and a consequent increase in overcrowding. The proposed challenge was to obtain an optimal solution for planning and distributing beds in the different specialties of the hospital, considering: Max_bed - The total number of beds in a hospital; Specialties – All the 36 specialties in the Hospital; Beds_needed – Number of beds needed on a certain day for each specialty; Bed_available – Number of beds available/empty in each specialty; It is important to mention that the model solution for this problem would always have to comply with two restrictions: i) The sum of beds to be allocated in each specialty on a given day, by the applied algorithm, should never exceed the maximum limit of available beds to be used; ii) The maximum number of beds to be allocated to a given specialty should never exceed the number of needs presented, thus avoiding the underuse of resources. 4.2 Data Provided The dataset provided for the study corresponded to the flow of patients in the CHTS over a period of 4 years (2019-2022) and it had the initial dimension of 708492 rows x 15 columns. Table 1 shows the various sources provided and a brief description of them. Table 1. Data Sources Data Sources Description Admissions Inpatients Data regarding the admission of patients to the Hospital, their specialties, dates, and times. 5 Discharges Inpatitents Data identical to those of patient’s admission to the hospital, but referring to the discharges. Patitents Allocation Data regarding the specialty where a certain patient was allocated. Specialties A data set that contained all the information regarding the hospital's specialties. Beds Real data regarding the number of beds existing in the hospital, in each specialty, and about the type of bed in question. It was possible to obtain daily information about admissions, discharges, patient transfers and the days on which they were under admission for each specialty. It was also possible to determine that the maximum number of beds available in the hospital was 551 beds. 4.3 Data Preparation In the data preparation phase for later use in the optimization models, all data with construction errors or Null or NaN values were first identified. Next, relevant data for the analysis of bed allocation, repeated or redundant attributes were identified. To a better impact understanding and problem solving, an important transformation was performed distinguishing two classes of inpatients: • physical patients - patients physically admitted to the service responsible for their treatment; • responsible patients - patients who are physically hospitalized in services other than those that treat them. These two classes correspond to correct and incorrect bed distribution, respectively. A correct bed allocation matching the daily needs of each specialty would maximize physical patients and minimize responsible ones. After these changes the dataset was transformed into a time series, moving the date attribute to index and divided into 36 different sub-datasets each corresponding to a specific specialty. Is then possible, for a given day, to know the flow of patients, what the status of the occupation of beds is and how many supplementary beds are necessary to supply the real needs of the specialty. 4.4 Domain and Fitness Function Before applying MLOA algorithms, it is necessary to define: i) the solution space of the problem; ii) how solutions will be represented; iii) how to define the constraints; and iv) how to evaluate the efficiency of the presented solutions. It is therefore imperative to define the problem domain and the objective function. The problem domain defines how the solution set will be represented given the problem constraints. The domain corresponds to the minimum and maximum number of beds available in each specialty so that the solution is always possible in the space of the problem since it doesn't exceed the maximum number of beds needed for the day. In order to optimize the algorithms' performance and decrease the probability of underutilization of resources, a "dynamic domain" was created depending on the day in question. Contrary to what is usually understood as a fixed variable in the problem, in this problem the domain may vary according to the daily needs of the different specialties of the hospital. In other words, for each day, the domain could vary between 0 and the number of patients under the responsibility of each specialty. The solution was represented in an array of 1 dimension, with 36 elements, each 6 corresponding to an integer number of beds to allocate in a given specialty for the day in question. The fitness function or objective function has as its main objective to evaluate a set of solutions. This function assigns a certain score to the solution to be evaluated taking into a account a set of conditions specific to the context of the problem. The goal is to minimize or maximize the score. Presented in Pseudocode 1, the fitness function tries to maximize the number of correct bed assignments knowing the daily Speciality while minimizing the number of empty on unused beds. This leads to maximizing the number of patients correctly assigned to a bed, i.e. maximizing physical patients to rather than responsible patients. 1. Fitness Function Pseudo Code satisfaction = 0 solution = solution input max_bed = 551 If sum(solution) > max beds then satisfaction = -100 For each specialty in solution do If beds_needed == beds in solution and beds available == 0 then satisfaction += 2 Else if beds_needed == beds in solution and beds available > 0 then satisfaction += 1 Else if beds_needed not equal to beds in solution: satisfaction -= |beds_in_solution – beds_needed| * 0.1 End If End For Return satisfaction 4.5 Optimization Techniques For optimizing the allocation of beds to patients, four different Optimization Algorithms were compared in order to understand which one would represent a better performance. The configuration of the algorithms was adapted to take the date in one of the parameters, since it is an input variable in the fitness function and essential to define the daily domain of the problem. The algorithms that were considered in this study are presented below. • Random Search (RS) A method based on the random search for solutions during a certain number of rounds. Note that the greater the number of rounds the more likely it is that a better solution will emerge, increasing in the same way the computation time [15]. 2. RS Pseudo Code round = 0 best_satisfaction = 0 best solution TO NULL 7 While round < rounds solution = random solution between the domain values satisfaction = fitness function(date, solution) If satisfaction > best_satisfaction then best_satisfaction = satisfaction best solution = solution End If round ++ End While Return best solution • Hill Climbing (HC) Hill Climbing is a local search algorithm, based on increments and decrements of the generated solutions, called "neighbors", starting with an initial random or previously provided solution within the domain. In its execution, each generated neighbor is analyzed and evaluated through the fitness function as to its quality, and if one of the neighbors generated in the iteration presents a better result, it becomes the current solution. The algorithm continues until there is no possibility of improvement in the solutions. This algorithm tends to find local optimal solutions. 3. HC Pseudo Code Generate an initial solution s0, s = s0 satisfaction = fitness(date, s) While termination criteria not met do neighbor_solution = Generate_Neighbor(s, domain) neighbor_satisfaction = fitness(date, neighbor_solution) If neighbor_satisfaction > satisfaction then s = neighbor_solution satisfaction = neighbor_satisfaction End If End While Return s • Simulated Annealing (SA) Simulated Annealing is a thermodynamic analogous method inspired by the metal cooling process. This algorithm consists in a sequence of iterations where a progressive decrease of temperature occurs, initializing it in a high value where each change is accepted, being this acceptance probability smaller and smaller as the temperature decreases according to a cooling rate. The search method is identical to the HC algorithm based on the transformation of solutions through increments to the previous solution, the big difference is that through the acceptance or not of the solutions this approach avoids getting stuck with local min or max. 4. SA Pseudo Code Generate an initial solution s0, s = s0 8 satisfaction0 = fitness(date, s) While temperature > 0.1 do s1 = Generate(s0, domain) satisfaction1 = fitness(date, s1) If Accept(satisfaction0, satisfaction1, temperature) then satisfaction0 = satisfaction1 s0 = s1 End If temperature = temperature * cooling End While Return s0 • Genetic Algorithm (GA) The Genetic Algorithm is based on Charles Darwin's theory of evolution. It acts on a set of possible solutions called individuals of a population. The algorithm starts with an initial population and transformations are performed on each of the individuals through mutation or crossover, whose decision is based on a previously defined probability. The best individuals are chosen according to an elitism number to generate the new population. The algorithm ends when the desired number of populations/generations is reached and the best individual from the last population is reached. It should be noted that, according to several studies such as the one carried out at the University of Neuchâtel in Switzerland, it was found that these algorithms show better results with larger populations than with increasing the max number of generations [16]. 5. GA Pseudo Code Initialize population elite = elistism * Population-Size For i in range number_generations fitness(date, individual) for each individual in population Select the elite with the best result Insert elite into new_population While new population-size < Population-Size IF probability of mutation Mutate elite individual - > new individual ELSE Crossover elite indivduals -> new individual Insert individual into new population End While End For 9 Return last generation best indvidual 4.6 Evaluation In order to evaluate the performance of each model, 10 runs of each one were performed. For each were saved the score obtained and the computation time required. For the experiment all the models were executed with data based on the date of May 5, 2021, taking into account that the domain corresponds to a variable that would change day after day, depending on real needs of the hospital. No difference was perceived in the success rate whether considering 1 or 50 days. Table 2 presents the metrics used for evaluating the techniques as well as a brief description. Table 2. Metrics Metric Description Average Fitness_Function Score Mean of all the scores obtained in the 10 Executions Average Run Time Mean of the execution times Model Score Standard Deviation (STD) STD of the scores obtained In a perfect scenario, the allocation of beds corresponds to the daily needs of these specialties and the number of unused beds tends to 0. The maximum score obtained would be 2 points for each one of the 36 specialties, i.e. 2x36, meaning a maximum score of 72 points. It is necessary to take into account that for this score to be reached the hospital is not in a state of over/under capacity. All the beds would be occupied and allocated to the specialties correctly, which is not observed in about 99% of the occurrences. The STD of the run time was not recorded since it was insignificant differences among runs for the same algorithm, what could be the result of the computational conditions in the development environment. 5 RESULTS AND DISCUSSION 5.1 Algorithm Settings To run the algorithms considered in this study it was necessary to define their initial input parameters except for HC. In the table 3 are presented the values used for the implementation of each technique. Table 3. Algorithms’ Parameters Model Parameters Random Search Rounds ->10000 Hill Climbing None Simulated Annealing Cooling Rate -> 0.95 Temperature -> 10000000000 Genetic Algorithm Population-size -> 400 Number_Generations -> 25 Probability of Mutation -> 0.2 Elitism -> 0.2