Dynamic Layout Design Optimization to Improve Patient Flow in Outpatient Clinics Using Genetic Algorithms

Abstract

Evolutionary algorithms, such as genetic algorithms have been used in various optimization problems. In this paper, we propose to apply this algorithm to obtain the layout design/redesign in order to improve the patient flow in an outpatient clinic. Layout designs are planned considering long-term requirements whereas the layout keeps modifying as per short-term demands. Over a period of time, the layout often does not remain efficient. Therefore, there is a need for such a model that helps in decision making on layout redesigns, and it must also optimize workflow by incorporating the flow constraints. In this study, we propose to minimize the waiting times by obtaining optimal and sub-optimal layout designs. A genetic algorithm is implemented to redesign the layouts based on the changing dynamics of patient demand, clinical pathways and services offered. The workflow is simulated with current layout and optimized layouts, and the results in terms of waiting time and cycle time are compared. The study shows that when layout design or redesign incorporate the workflow and pathways along with associated constraints, improves waiting time and cycle time of patients in the outpatient clinic. The distance between the departments/locations is translated to travelling time and overall travel distance/time is minimized by rearranging the allocations of departments to the location through genetic algorithms.

1. Introduction

Evolutionary algorithms (EAs) are used to yield better approximate solutions to complex problems. Finding exact solutions is often difficult, and sub-optimal solutions may be proven better. EAs are applied in evacuation planning, disaster management, decision making, etc. Genetic algorithms (GA) is the most popular among EAs and is greatly used in optimization problems. It is a search algorithm that is based on natural selection where the fittest solution would survive. Such algorithms are robust, simple and powerful. It is observed from literature that these algorithms are extensively used in layout optimization problems.

Outpatient clinics (OPCs) are systems that require a lot of continuous optimizations. To improve the OPC’s performance, parameters such as waiting times, cycle times and resource utilization need to be optimized. For this, OPCs should plan, schedule and control patients and resources effectively [1,2,3]. Generally, an OPC is a collection of different service-providing departments (physical locations) that are put together. The way the rooms are allocated to the departments (referred as OPC layouts) affects the patient workflows and also the operations management/workflow management, either positively or negatively. It is observed from literature and practice that layout optimization is a complex problem and has been addressed in settings such as facility layouts, chemical plants, nuclear reactors and manufacturing plants [4]. When these kinds of layouts are compared with OPC layouts, OPCs stand apart as there are several constraints (like variability and uncertainty in patient demand and workflow pathways) involved in the design of OPC layouts.

Outpatient clinics have many processes/services that are interconnected and interrelated, making an OPC a complex network. The locations of the services are based on functional structure (organized depending on the type of work and not on the care pathway or disease) as patients are required to move from one location to another in order to complete their treatment processes. This travelling of patients increases their waiting time and the cycle time. Generally, layout designs are strategic decisions that are, or should be, evaluated every 7–10 years. The layout problem can also be viewed as a capacity planning problem [5]. Over a period of time, demand increases, its mix changes and offered services change. With the addition of multiple specialties, the resources get shared between them. Also, there could be a few changes that are based on short-term requirements. However, the buildings remain in use even after these changes, and this may result in congestion and chaos in workflows, eventually leading to compromise in efficiency and experience quality. There is a relationship between operations management and OPC design [6].

It is at the operational level that the layout influences workflow management and the quality of healthcare services [7]. Therefore, the OPC layout should be designed carefully so that it can adapt to the future changes in the workflows. As the layout design is a strategic decision with a long-term impact, it cannot be very easily adapted to the changing scenarios because it involves high cost. It is a challenging task to design or redesign the OPC layout when it is associated with uncertainties about future patient demand and related technologies. The goal of this study is to redesign a layout of an OPC that is adaptable in future to the changing patient demand and their mixes and aide in decision making. In this study, the layout redesigns are obtained with the use of a genetic algorithm, and layouts obtained are compared based on waiting times.

This paper is organized as follows: Section 2 presents the background of the study, Section 3 presents the materials and methods—data collection and analysis, model development and validation, and experimental designs followed by the problem formulation. Section 4 compares the results and discussion of both the algorithms. Section 5 presents the conclusion.

2. Background

Layout optimization is commonly seen and addressed in manufacturing industries, VLSI chip designs and chemical plants. Facility layout problems (FLP) relate to allocation problems with constraints and to solve these, heuristic and meta-heuristic algorithms are used. The layout optimization has been commonly modelled as a quadratic assignment problem (QAP) [8,9]. The distance correlations between the facilities and locations are analyzed and to achieve this, branch and bound techniques are used. The optimization of the new layout differs from that of the existing layouts. The existing layouts have more constraints compared to that of the new layouts.

Over a period of time, patient demand increases and also the specialties offered change. In such scenarios, OPCs should review their layouts for possible changes. Designing optimal layout can easily be implemented in the new OPC, in which the workflow dependencies and complexities can be addressed during design. As any change in layout results in additional costs, simulation is an important tool to identify and analyze the optimal layout. Simulation aids the study and analysis of different scenarios, also with the purpose cost and or quality of work and service in altering the layout [10,11]. Efficient and effective planning during layout design is most important to achieve better performance [12]. Hospital/OPC buildings were shaped to fit as many patients as possible [13]. Evidence-based practices are used to cut down the travel time of staff and patients [14]. For example: centralized nurse stations surrounded by patient rooms will increase the efficiency. The authors in [15] show the effect of the changes in layout and process improvement on the performance of emergency room operations. Based on before and after implementation it is observed that combining both structure-oriented and process-oriented strategies is beneficial in maximizing the performance. A parametric model of layout optimization is developed as a geometric approach that helps in handling the complexities that arise because of predefined rules and parameters and precedencies [16]. A clinical pathway mining approach was used in [17] where current pathways were collected. Based on this data, the future clinical pathways were predicted using a machine learning algorithm. A mathematical model and expert knowledge were used in hospital layout planning decisions.

It is observed that layout problems are solved using methodologies such as exact procedure, heuristics and meta heuristics. Currently, meta-heuristics such as simulated annealing and genetic algorithm are extensively used. These solve large scale facility layout problems. Other approaches for layout optimization are neural network, fuzzy logic, ant colony optimization (ACO) and expert systems [9,11,18]. ACO is a combinatorial algorithm and it is good for discrete problems whereas genetic algorithm is good for continuous and discrete. Ant agent algorithm has been used in OPC layout optimization. The authors in [19] have modified the ant agent algorithm to incorporate the sequential flow constraints associated with the OPC. It provided an optimal layout design (single best solution) that considered the workflow constraints and improved the waiting time and cycle time. But, having only one solution to redesign the existing layout makes it difficult for implementing the changes suggested in the optimal solution. The layout provided by ant agent algorithm, however, was the best layout that improved the performance of the OPC, and it is suitable for new-buildings as the changes/modifications can be easily accommodated. The OPCs that already have constraints cannot adapt this solution/design. Therefore, for such situations multiple layout redesigns are needed in relation to whichever layout design suits the OPC that could be used.

Evolutionary algorithms generate multiple solutions, optimal (best) and sub-optimal solutions (next/close to best, but not best) to the problems using the techniques that are inspired by natural evolution. These algorithms have often been used in the facility layout optimization in manufacturing and routing problems [20,21,22,23,24,25,26]. The genetic algorithm (GA) is a search heuristic that depicts the process of natural selection. According to literature, as GAs do not employ analytical properties of the function to be optimized, they have attracted the attention of researchers. GA along with adaptive local search is applied to solve multi-floor hospital layout problems [27]. The study minimized the total movement distance of patients and maximized total closeness rating scores. It improved both the parameters by 83.91% (best solution) and 60.16% (best solution).

In this study, a genetic algorithm has been implemented to obtain the optimal and sub-optimal layout redesigns. The layout optimization model is developed, and it is solved using the algorithm. The resulting layout redesigns are analyzed based on the performance parameters. This is used in decision-making during OPC layout planning.

3. Materials and Methods

This study was conducted in Aravind Eye Hospital (AEH), Madurai, Tamil Nadu, India. The OPC in AEH gets around 2300 patients per day. As all the patient arrivals are walk-in, it creates a lot of variability and uncertainty, making the workflow management complex. The performance parameters, such as waiting times and cycle times get most affected by varying patient volume and patient arrivals. It is observed in [19] that the performance parameters depend on the processing times, patient arrival patterns, scheduling rules as well as on the OPC layout. Data about the locations of the departments, waiting room capacities, distance between the departments and the sequential dependence/precedence constraints within departments were collected. The study developed a simulation model based on the collected data and validated the model. The OPC layout design was considered as an optimization problem with flow constraints. The locations to the departments were optimally assigned by genetic algorithm which is one of the evolutionary algorithms. This algorithm provided the optimal and sub-optimal layouts. The patient workflow was re-simulated with optimal and sub-optimal layouts and the performance parameters like waiting time and cycle time were compared.

3.1. Data Collection and Analysis

To understand the workflow, interviews were carried out with OPC staff. In addition, patient and department data were obtained from the inhouse software. To simulate the OPC workflow that depicts real-time scenario data such as patient demand, arrival times, patient in-time and patient out-time, resources in-time and out-time, and resource schedule were collected. The waiting times, cycle times, processing times and utilization were extracted from the collected data [2]. The Easy-Fit tool was used to determine the probability distributions of service times and patient arrival times. A bimodal Poisson distribution [28,29] was used to generate patient arrival times. The workflow in the OPC is as shown in Figure 1. There are two types of patients, new and review. The new patients are serviced through registration, vision, preliminary test, refraction, tension, dilatation and final examination. The processing time differs from patient to patient. Review patients follow the same clinical pathway, except the initial vision test. A few sequences in the pathway can be realigned.

The OPC is situated on the ground floor. The floor layout of the OPC under study has one location/room for new registration, one for review registration, one for vision, five for refraction, one for tension and three for preliminary and final examinations. The physical dimensions of the OPC were collected, and the distances between locations were measured through the number of human steps (walking) which was later translated to time during the simulation. The time taken to walk a particular distance varied, and the number of steps also varied based on the age and height of the patient, respectively. Therefore, average numbers of steps was considered for simulation. The walking style or the pattern of the disabled patients was excluded as they contributed less than 1% of the patient volume.

The in-house software provided the information about wait time, patient mix and service time. Process data of around 20,000 patients were obtained, and 2700 patient data among them were excluded as the recorded cycle time of these patients was less than 15 min. Either the patient left the workflow in-between or the patient visited only preliminary examinations. The remaining 17,300 patient data were used in building the model. The service time was considered as variable, and it was derived from the empirical distribution. Service times were uniformly distributed between the minimum and maximum processing times from empirical data for each department and were randomly generated. As this study considers only layout optimization, the scheduling methods used by the OPC were not modified.

3.2. Problem Formulation for Layout Optimization

OPCs have a greater number of constraints like space, workflow, patient flow, resources and logistic flows in the existing layouts and optimizing such layouts is difficult. The objective of this study is to minimize the cycle time by redesigning the existing layout. Cycle time consists of processing time, waiting time and walking time of the patients. The walking time is also applicable to staff and doctors. The problem formulation is based on process flow and dependencies, distance between locations and adjacency between the locations and is presented in Equation (1).

$$\mathrm{Min}{{\displaystyle \sum }}_{i=1}^N{{\displaystyle \sum }}_{j=1}^{M}C{T}_{i,j}{D}_{i,j}{N}_{i,j}{X}_{i,j}$$

(1)

where $C_{i,j}$ is the cycle time that constitutes waiting time, processing time and travel time/walking distance; $D_{i,j}$ is the distance matrix between the locations (here the distance is represented in number of footsteps); $N_{i,j}$ is the neighborhood matrix of locations; $X_{i,j}$ = 1; M is the number of departments; N is the number of locations; M ≤ N.

Genetic algorithm is used to solve the facility redesign problems. Later, the resultant layouts, the optimal and suboptimal layouts are compared in order to find the appropriate layout.

3.3. Genetic Algorithm

First, we explain the basics of the genetic algorithm. GA starts with an initial set of random solutions for the problem under consideration. This set of solutions is known as the population. The individuals of the population are called chromosomes, and its representation is called encoding. The chromosomes of the population are evaluated according to a pre-defined fitness function. The chromosomes evolve through successive iterations called ’generations’. During each generation, through merging and modifying chromosomes of a given population, a new population is created. Merging chromosomes is known as ‘crossover’, while modifying an existing one is known as ‘mutation’. Crossover is the process in which the chromosomes are combined in a random fashion to produce a pair of new chromosomes (offspring). A mutation operator is used to expose unexpected changes in the values of genes. The selection of chromosomes to crossover and mutate is based on their fitness function. At each generation, a new population is created by applying the crossover and mutation operators. The process is repeated until a specific stopping criterion is reached [30]. The steps of genetic algorithm implemented to the OPC layout optimization is presented below:

• Encoding: An encoding scheme maps feasible solutions of the problem to the strings [31]. Encoding should be such that the minor changes in the chromosomes (individuals) translate into minor changes in corresponding solution. In this layout optimization permutation encoding is used to represent the department order. First row indicates the room numbers and the second row indicates the departments like registration, vision, refraction etc. Together, it is called chromosome, as the entries are referred as genes and we use integers 1, 2, …, 12 (to avoid confusion they are referred as locations L1, L2, …, L12 in explanation) for departments D1—D12. New registration—D1, Review Registration—D2, Vision—D3, Refraction—D4, D5, D6, D7, D8, Tension—D9 and Preliminary test and final examination—D10, D11, D12. This is implemented as a vector and is shown in Figure 2.
• Initial population generation: The initial population is selected between 1.5 to 2 times the number of genes. As the number of genes is n =12, we use population size = 2 × 12 = 24.
• Selection: Five individual parents (design) are generated randomly. A fitness function is calculated, and its value with associated parent is stored. The individual is arranged in descending order of fitness value. The first two individuals are selected as parents to apply cross over operator to generate offsprings.
• Fitness function: The cycle time of the patient in the OPC also depends on the travel time between locations. Thus, the fitness function depends on the distance between the locations. When distance gets converted to the time, it contributes to the cycle time. In this study, optimization function is the same as fitness function, and it minimizes the cycle time. But we measure the Fitness value as the ratio of waiting time to the cycle time. The population is evaluated with this fitness function and the best two chromosomes are selected. These form parent1 and parent2.
• Crossover and mutation: The first two rooms are at the entrance of the building, and they are currently allocated to new registration and review registration. These are left untouched. Room numbers remain same; only department numbers are exchanged. A sample vector shown in Figure 2 is repeated in Figure 3a for explaining algorithmic steps. First, the parent genes (3–12) are shuffled, and then single point swapped crossover is applied to get the offspring (Figure 3b). The colored part shows the change in the genes or department numbers. Crossover rates between 0.3 to 0.6 were used. We use swap mutation for next generation and the objective function is evaluated again. The swap mutation is shown in Figure 3c. Mutation rate was 0.08(1/n = 1/12). When the number of generations got completed, the algorithm was stopped.

A database of all the solutions and its fitness values were maintained. Although evolutionary algorithms find the best solution, sub-optimal solutions were also stored because the sub-optimal layouts are based on the existing constraints.

3.4. Model Development

Microsoft’s .NET (dotnet) Framework was used for simulation of OPC workflow and genetic algorithm. The model developed is combination of GA module and OPC simulation module as shown in Figure 4. The GA is implemented using parameters, such as population, parent/chromosome selection, fitness function, number of genes/rooms and locations, distance matrix and crossover and mutation. The offspring generated are the layout redesigns and are stored in database. These redesigns are used by OPC simulation module. This module has parameters, such as patient demand and arrival times, precedence constraints, clinical pathways, processing times and distance matrix. The resulting walking distance in terms of steps and, waiting times and cycle times for that particular layout redesign is stored in the database. Further, the fitness function is calculated. A hundred generations are considered.

The simulation model was run with the empirical data, and the performance measures, namely waiting times and cycle times were collected. The travel distance was measured in terms of steps and then converted to time. This time was added to cycle time of the departments. Cycle time is sum of processing time, waiting time and travel time. The results of the simulation model were compared with the empirical data of the OPC for validation as shown in

Table 1. Simulation model validation in terms of waiting time and cycle time.

	Empirical Data		Simulation Results		p-Value
	Mean	SD	Mean	SD
Waiting time in minutes	59.5	43.92	58.2	40.15	0.4
Cycle time in minutes	113.26	44.2	115.32	39.6	0.29

SD: Standard Deviation.

and there was no statistical difference between the two. The clinical pathways, number of departments and locations are considered as variables. So, they can be added or deleted from the simulation model. This is for future changes in the OPC services offered. Also, the precedence constraints are not fixed but can be varied in simulation model.

3.5. Experimental Design

The layout redesigns were obtained using a genetic algorithm. The seed in random variate was varied to generate different arrival times for the same mean patient arrivals [2]. The same randomizer input was used for simulation with the different layout design. For each layout redesign (offspring), the OPC simulation was run for three different patient demands: one with current patient demand, a second with 20% more than current patient demand and a third with 40% more than current patient demand. For statistical comparisons, ANOVA tests were performed with p < 0.05.

4. Results and Discussion

This study is a simulation study, and the genetic algorithm used was aimed to find the optimal as well as sub-optimal layouts. Depending on the fitness function, different layout redesigns are considered, and for these layout redesigns, the patient demand is varied and the performance parameters are calculated. The number of solutions provided by the algorithms differ (See

Table 2. Distances travelled in the layouts obtained by genetic algorithm.

Algorithm	Number of Solutions/ Layouts	Distance (in Steps) According to the Solutions
Genetic Algorithm	12	305, 211, 251, 260, 296, 228, 237, 235, 677, 675, 1101,1099

).

The layout redesigns/solutions obtained are as shown in Figure 5 as per the walking steps. Lesser the number of steps in the layout, more is the flexibility required to accommodate the changes in the OPC.

The performance or the efficiency of the OPC depends on processing times, waiting times, cycle times, throughput, resource utilization and operational costs. The waiting times and the cycle times also depend on the resource utilization (in this research, it is the space utilization). The current layout with existing pathways and patient demand was evaluated. The current layout requires patients to walk for 295 steps to complete their care and the current patient demand is 2300 patients/day. The approximate layout is depicted (not to the scale) in Figure 6.

All the layout redesigns obtained from GA were evaluated for the current scenario. The waiting times and cycle times for different layouts were recorded by varying patient demand by +20% and +40% of the current demand. The solutions and their performance parameters are as shown in

Table 3. Comparison of waiting time and cycle times with increase in demand for different layout redesigns.

Layout Redesign Number	No. of Steps	Waiting Time in Minutes			Cycle Time in Minutes
		Current Demand (2300 Patients/Day)	20% Increase (2760 Patients/Day)	40% Increase (3220 Patients/Day)	Current Demand (2300 Patients/Day)	20% Increase (2760 Patients/Day)	40% Increase (3220 Patients/Day)
1	211	37.9	40.2	46.2	90.9	91.2	95.2
2	228	44.0	46.7	50.2	91	92.7	95.2
3	235	45.4	46.9	51.9	95.4	101.9	100.9
4	237	45.4	49.4	52	99.4	95.4	104
5	251	48.0	52.0	57.5	97	93	111.5
6	260	50.8	53.2	57.9	94.8	108.2	98.9
7	296	58.2	63.3	69.5	102.2	116.3	115.5
8	305	60.0	65.4	72.5	107	112.4	117.5
9	675	66.8	71.2	79.8	106.8	114.2	119.8
10	677	66.8	71.2	79.8	118.8	111.2	131.8
11	1099	76.4	84.5	89.1	125.4	133.5	140.1
12	1101	76.4	84.5	89	131.4	125.5	140

.

The GA provided 12 solutions and all the redesigns were used in simulating the waiting times and cycle times for different patient demand. It is observed that out of twelve solutions/layout redesigns, six layouts have a greater number of walking steps compared to the existing one (295 steps), and this will ultimately result in more travel time. It is observed that the other solutions have a smaller number of walking steps, and also the changes required while implementing the redesigns is less. There is a tradeoff between the number of walking steps and the flexibility of the OPC to change the layout accordingly. The waiting time and the cycle times for the OPC layout with minimum distance layouts are compared with the same parameters in the existing layout in

Table 4. Comparison of wait time and cycle time in existing layout and optimized layout.

	With Existing Layout	Best Layout with GA
Wait time in minutes	59.5	37.9
Cycle time in minutes	113.26	97.2

. The ANOVA test (p < 0.05) was used for statistical significance analysis.

The results show that the physical layout of the outpatient clinic has impact on the workflow management: patient flow, waiting time and cycle time. The waiting time has reduced by 36.3.28% (21.6 min) and the cycle time has reduced by 14.17% (16.06 min) The staff scheduling and the patient scheduling was retained as per current scenario. The optimal solution obtained resulted in reduction in walking distance from 295 to 211.

From literature, the Ant algorithm in [19] provided the single best optimal solution for the layout with the objective of minimizing the walking distances. The proposed model in [19] provided one best solution. The optimized layout obtained from that algorithm is suitable for new OPC buildings as these buildings can adapt easily, whereas for existing OPCs there are multiple constraints. Having only one optimal layout and changing the existing layout to optimize workflow is challenging and difficult. In such situations, OPCs need sub-optimal solutions/layout redesigns. The changes suggested as per sub-optimal solutions can be adapted in the existing layout and also optimize the workflow. There are various solution layouts which reduce the walking distances compared to the existing layout and require few changes/modifications in the layout. The layout redesign that has a greater number of walking steps/distance requires less alteration to the layout, and with a smaller number of steps, requires more alteration to the existing layout. This is because the farther locations are reallocated to the same departments as before and this does not require any alteration. Only if the locations are allotted with different departments does OPC require a greater number of alterations. With this size of layout problem, the execution time for genetic algorithm is 34 s. With the increase in number of locations, the search space becomes wider and the execution time will increase. The complexity depends on mutations, crossovers, population size and number of generations for GA.

Unlike other facility layouts, OPCs/hospitals have a lot of variabilities and uncertainties in services offered. The OPC may add or stop providing certain services. The long-term requirements are considered for 1–5 years. But the short-term requirements are considered for 3–6 months. The OPC building lasts for a long time, so their reuse is necessary. For this, the OPCs should be flexible to restructure or design its layout based on operations management. With time, the dynamics in OPCs keep changing. At times, implementing the optimal solution will not be possible because of cost and other constraints. This study helps in hospital layout planning and aids in decision-making. The decisions about layouts need to be made based on system-status/real-time need of the OPC. The cost associated with making the changes in the existing layout by moving equipment is not incorporated in this model. Also, the change is services offered and change in pathway is not implemented. Waiting hall capacity also needs to be incorporated with increase in patient demand. With increase in demand, the number of departments will also increase. The OPC can have demand based resource allocation that minimizes patient waiting time [1]. To optimize in this way, OPCs should be flexible to adapt accordingly to the changes.

5. Conclusions

Generally, the current OPC layout design does not suffice to the future requirements and changes. To improve the performance parameters like waiting time and cycle time, the layout needs to be redesigned based on the changing dynamics of the OPC. This study proposed the use of the genetic algorithm to identify the optimal and sub-optimal layout redesigns based on precedence constraints and walking distance. The implementation of these redesigns depends on the flexibility of the OPCs to adapt to the changes with less hazzles. The results show that meta heuristic algorithms are suited for OPC layout optimization in which the performance parameters like waiting times and cycle times are improved. The model helps the OPCs in strategic decision-making by changing inputs like clinical pathways, patient demand, additional departments and also locations. This model can further be extended to any type of hospital layouts, and the solutions can be chosen depending on the practical feasibility analysis.